Deciding an election



next up previous
Up: Example Sheet Previous: Generating numerals

Deciding an election

The problem is to write a function that given a list of candidates and a list of votes, returns a list of the candidates who received the most number of votes. We represent both candidates and votes as strings.

    type cand = string
    type vote = string
    val cs: cand list = ["A","B","C","D","E"]
    val vs: vote list = ["D","D","A","B","C","A","C","D","A"]

Given candidates cs and votes vs the answer should be ["A","D"], since these candidates tie with three votes each.

Here is one simple way to solve the problem.

  1. Write a function count: cand * vote list -> int such that count (c, vs) evaluates to the number of occurrences of c in vs.

  2. Make the following type definition.
        type count = cand * int
    Write a function countall: cand list * vote list -> count list, that given lists of candidates and votes, returns a list pairing each candidate with the number of votes received.

    In our example election, countall (cs, vs) should return [("A", 3), ("B", 1), ("C", 2), ("D", 3), ("E", 0)].

  3. Write a function maxl: int list -> int that returns the maximum element of its argument list.

    In what way is this an incomplete specification of maxl?

  4. Write a function match: int * count list -> count list that returns those counts in its input list that match its integer argument.

  5. Using these functions, or otherwise, define a function winners: cand list * vote list -> count list * cand list, that given a list of candidates and votes, computes the list of counts for each candidate, and returns it paired with a list of the winning candidates.

    Hint: you may find function split (from lists.ML) helpful.

We complete the exercise by writing functions to generate test data. We can exploit the random number generator used in the sorting case study. In lists.ML you can find the definition of the following two functions:

    val randlist: int * real * real list -> real * real list
    val truncto: int -> real -> int

Given an integer seed i (1.0 is a good choice; we represent integers as reals for the sake of accuracy in some implementations), application randlist (n, i, []) returns a list of n random numbers together with a new seed (that can be used again). If r is one of these random numbers than truncto k r is a random int in the range 1..k. That's all we need to know about these functions. (But you can find details of the underlying series in Park and Miller's article in Communications of the ACM 31:1192-1201 (1988).)

  1. Write a function nth: int * 'a list -> 'a list such that nth (i, [x0,x1,...,xn]) returns element xi. NB If a list has n elements they are numbered 0,1,2,...n-1. (Hint: use drop.)
  2. Write a function mk_votes: cand list * real list -> cand list such that if cs is a list of candidates and rs is a list of n random numbers, that mk_votes(cs,rs) returns n randomly chosen votes. (Hint: use length and truncto.)

Now using the following definitions

  fun mk_n_votes (cs, n) =
    let val (_,rs) = randlist (n, 1.0, [])
    in  mk_votes (cs, rs)
    end;

  fun test n = winners (cs, mk_n_votes (cs, n));
you can test out your solution on any number of random votes.

next up previous
Up: Example Sheet Previous: Generating numerals



Andy Gordon
Tue Jan 31 14:41:57 GMT 1995