UoL CS Notes
Menu

Lecture 18-2

COMP105 Lectures

First Past the Post Example

This example covers a first past the post election. This means whoever gets the most votes wins. We are aiming to make a function that performs this task:

> winner ["red", "blue", "red", "red", "green"]
> "red"

Getting the Candidates

First we need to figure out who the candidates are:

uniq [] = []
uniq (x:xs) = x : uniq (filter (/=x) xs )

This function will remove duplicates from a list of strings. For every new element found the filter will remove all further occurrences from the rest of the list before recursing on the list.

Counting the Votes

This function counts the number of votes for a particular candidate:

count x list = length (filter (==x) list)

Vote Totals

This function will count all the votes for each candidate and put the number of votes and then the candidate in a list of tuples.

total votes = 
	let
		candidates = uniq votes
		f = (\ c -> (count c votes, c))
	in
		map f candidates

Comparing Candidates

Tuples are compared lexicographically. This means that each element is compared in turn to find which satisfies the function.

> max (3, "red") (2, "blue")
> (3,"red")

This means that if two candidates have the same number then the string is compared.

maximum

The function maximum takes a list and returns the largest item in the list:

> maximum [(3, "red"), (2, "blue"), (4, "green")
> (4, "green")

Finding the Winner

snd returns the second value in a tuple:

winner votes = snd . maximum . totals $ votes

Applying this satisfies the requirement:

> winner ["red", "blue", "red", "red", "green"]
> "red"

Alternative Vote Example

In the alternative vote system, voters rank the candidates:

  • In each round, the candidate with the least number of first preference votes is eliminated.
  • The winner is the last candidate left once all other have been eliminated.
> let votes = [["red", "blue", "green"],
				["blue", "green"],
				["green", "red"],
				["blue", "red"],
				["red"]]
> av_winner votes
> "red"

You don’t need many preferences and each list is a single person’s preferences.

See the slides for full examples.

Ranking the Candidates

sort sorts all of the items in a list and orders them from smallest to biggest.

Getting the First Choice Votes

head doesn’t accept empty lists as input. This should be taken into account when removing items from lists unevenly.

Final Function

All of the components give this function:

av_winner votes =
	let
		ranked = rank_candidates votes
		first = head ranked
	in
		if length ranked == 1
		then first
		else av_winner (remove_cand first votes)