I had some requests to publish the code for the AV Voting System that I presented at the start of my last talk at F#unctional Londoners. This is the code I wrote when I got bored writing slides for the talk. It is representative of the kind of code I write when I am exploring a problem for the first time using F#. Note that the model is used more for me to think about the shape of the data involved; it is not used explicitly by the code itself. This low-ceremony, low committment approach to modelling is ideal for exploratory programming. It allows me to cut-to-the-chase and explore the algorithm without delay. Combine this with the REPL (F# interative) and I have a very productive enviroment in which to play.
This code has bugs but has served its purpose by revealing a rather nice recursive approach to implementing voting systems. Hopefully more illuminating than the rather disappointing level of debate we had on the same subject leading up to the recent referendum in the UK.
1: // The Model
2:
3: type Candidate = string
4: type Preference = int
5: type Vote = (Candidate * Preference) list
6: type Election = Vote list
7:
8: // The Code
9:
10: let partitionCandidates result =
11: let _,losingPercentage = List.minBy (fun (c,p) -> p) result
12: List.partition (fun (c,p) -> p = losingPercentage) result
13: |> (fun (ls, ws) -> List.unzip ls |> fst, List.unzip ws |> fst)
14:
15: let remove losers election =
16: let isLosing candidate = List.exists (fun loser -> candidate = loser) losers
17: List.map (List.filter (fun (c,_) -> not <| isLosing c)) election
18:
19: let firstPreference vote =
20: let min cp1 cp2 = if (snd cp2) < (snd cp1) then cp2 else cp1
21: List.fold min ("", System.Int32.MaxValue) vote
22: |> fst
23:
24: let add candidate candidateTotals =
25: let incr ct = if candidate = fst ct then candidate, snd ct + 1 else ct
26: List.map incr candidateTotals
27:
28: let isThereAWinner result =
29: List.exists (fun (_, percentage) -> percentage >= 50.) result
30:
31: let firstPreferenceResult candidates election =
32: let totalNumberOfVotes = float <| List.length election
33: let initialTotals = List.map (fun c -> c,0) candidates
34: let toPercentage (candidate,total) =
35: candidate,(float total)/totalNumberOfVotes*100.0
36: let addVote candidateTotals vote = add (firstPreference vote) candidateTotals
37: List.fold addVote initialTotals election
38: |> List.map toPercentage
39:
40: let rec electionResult candidates election =
41: let result = firstPreferenceResult candidates election
42:
43: if isThereAWinner result then
44: printfn "final %A" result
45: else
46: let losers, winners = partitionCandidates result
47: printfn "-- %A\n winners %A losers %A" result winners losers
48: electionResult winners (remove losers election)
49:
50: // The Election Results
51:
52: let castVote candidates preferences =
53: List.zip candidates preferences
54:
55: let candidates = ["a"; "b"; "c"; "d"]
56: let election = [
57: castVote candidates [1;2;3;4]
58: castVote candidates [1;2;3;4]
59: castVote candidates [1;2;3;4]
60: castVote candidates [1;2;3;4]
61: castVote candidates [4;3;2;1]
62: castVote candidates [4;3;2;1]
63: castVote candidates [3;4;1;2]
64: castVote candidates [3;4;1;2]
65: castVote candidates [4;1;3;2]
66: castVote candidates [3;4;2;1]
67: ]
68:
69: electionResult candidates election
Multiple items
val string : 'T -> string
Full name: Microsoft.FSharp.Core.Operators.string
--------------------
type string = System.String
Full name: Microsoft.FSharp.Core.string
type: string
implements: System.IComparable
implements: System.ICloneable
implements: System.IConvertible
implements: System.IComparable<string>
implements: seq<char>
implements: System.Collections.IEnumerable
implements: System.IEquatable<string>
type Preference = int
Full name: Snippet.Preference
type: Preference
implements: System.IComparable
implements: System.IFormattable
implements: System.IConvertible
implements: System.IComparable<int>
implements: System.IEquatable<int>
inherits: System.ValueType
Multiple items
val int : 'T -> int (requires member op_Explicit)
Full name: Microsoft.FSharp.Core.Operators.int
--------------------
type int<'Measure> = int
Full name: Microsoft.FSharp.Core.int<_>
type: int<'Measure>
implements: System.IComparable
implements: System.IConvertible
implements: System.IFormattable
implements: System.IComparable<int<'Measure>>
implements: System.IEquatable<int<'Measure>>
inherits: System.ValueType
--------------------
type int = int32
Full name: Microsoft.FSharp.Core.int
type: int
implements: System.IComparable
implements: System.IFormattable
implements: System.IConvertible
implements: System.IComparable<int>
implements: System.IEquatable<int>
inherits: System.ValueType
type Vote = (Candidate * Preference) list
Full name: Snippet.Vote
type: Vote
implements: System.Collections.IStructuralEquatable
implements: System.IComparable<List<Candidate * Preference>>
implements: System.IComparable
implements: System.Collections.IStructuralComparable
implements: System.Collections.Generic.IEnumerable<Candidate * Preference>
implements: System.Collections.IEnumerable
type Candidate = string
Full name: Snippet.Candidate
type: Candidate
implements: System.IComparable
implements: System.ICloneable
implements: System.IConvertible
implements: System.IComparable<string>
implements: seq<char>
implements: System.Collections.IEnumerable
implements: System.IEquatable<string>
type 'T list = List<'T>
Full name: Microsoft.FSharp.Collections.list<_>
type: 'T list
implements: System.Collections.IStructuralEquatable
implements: System.IComparable<List<'T>>
implements: System.IComparable
implements: System.Collections.IStructuralComparable
implements: System.Collections.Generic.IEnumerable<'T>
implements: System.Collections.IEnumerable
type Election = Vote list
Full name: Snippet.Election
type: Election
implements: System.Collections.IStructuralEquatable
implements: System.IComparable<List<Vote>>
implements: System.IComparable
implements: System.Collections.IStructuralComparable
implements: System.Collections.Generic.IEnumerable<Vote>
implements: System.Collections.IEnumerable
val partitionCandidates : ('a * 'b) list -> 'a list * 'a list (requires comparison)
Full name: Snippet.partitionCandidates
val result : ('a * 'b) list (requires comparison)
type: ('a * 'b) list
implements: System.Collections.IStructuralEquatable
implements: System.IComparable<List<'a * 'b>>
implements: System.IComparable
implements: System.Collections.IStructuralComparable
implements: System.Collections.Generic.IEnumerable<'a * 'b>
implements: System.Collections.IEnumerable
val losingPercentage : 'b (requires comparison)
Multiple items
module List
from Microsoft.FSharp.Collections
--------------------
type List<'T> =
| ( [] )
| ( :: ) of 'T * 'T list
with
interface System.Collections.IEnumerable
interface System.Collections.Generic.IEnumerable<'T>
member Head : 'T
member IsEmpty : bool
member Item : index:int -> 'T with get
member Length : int
member Tail : 'T list
static member Cons : head:'T * tail:'T list -> 'T list
static member Empty : 'T list
end
Full name: Microsoft.FSharp.Collections.List<_>
type: List<'T>
implements: System.Collections.IStructuralEquatable
implements: System.IComparable<List<'T>>
implements: System.IComparable
implements: System.Collections.IStructuralComparable
implements: System.Collections.Generic.IEnumerable<'T>
implements: System.Collections.IEnumerable
val minBy : ('T -> 'U) -> 'T list -> 'T (requires comparison)
Full name: Microsoft.FSharp.Collections.List.minBy
val c : 'a
val p : 'b (requires comparison)
val partition : ('T -> bool) -> 'T list -> 'T list * 'T list
Full name: Microsoft.FSharp.Collections.List.partition
val ls : ('a * 'b) list (requires comparison)
type: ('a * 'b) list
implements: System.Collections.IStructuralEquatable
implements: System.IComparable<List<'a * 'b>>
implements: System.IComparable
implements: System.Collections.IStructuralComparable
implements: System.Collections.Generic.IEnumerable<'a * 'b>
implements: System.Collections.IEnumerable
val ws : ('a * 'b) list (requires comparison)
type: ('a * 'b) list
implements: System.Collections.IStructuralEquatable
implements: System.IComparable<List<'a * 'b>>
implements: System.IComparable
implements: System.Collections.IStructuralComparable
implements: System.Collections.Generic.IEnumerable<'a * 'b>
implements: System.Collections.IEnumerable
val unzip : ('T1 * 'T2) list -> 'T1 list * 'T2 list
Full name: Microsoft.FSharp.Collections.List.unzip
val fst : ('T1 * 'T2) -> 'T1
Full name: Microsoft.FSharp.Core.Operators.fst
val remove : 'a list -> ('a * 'b) list list -> ('a * 'b) list list (requires equality)
Full name: Snippet.remove
val losers : 'a list (requires equality)
type: 'a list
implements: System.Collections.IStructuralEquatable
implements: System.IComparable<List<'a>>
implements: System.IComparable
implements: System.Collections.IStructuralComparable
implements: System.Collections.Generic.IEnumerable<'a>
implements: System.Collections.IEnumerable
val election : ('a * 'b) list list (requires equality)
type: ('a * 'b) list list
implements: System.Collections.IStructuralEquatable
implements: System.IComparable<List<('a * 'b) list>>
implements: System.IComparable
implements: System.Collections.IStructuralComparable
implements: System.Collections.Generic.IEnumerable<('a * 'b) list>
implements: System.Collections.IEnumerable
val isLosing : ('a -> bool) (requires equality)
val candidate : 'a (requires equality)
val exists : ('T -> bool) -> 'T list -> bool
Full name: Microsoft.FSharp.Collections.List.exists
val loser : 'a (requires equality)
val map : ('T -> 'U) -> 'T list -> 'U list
Full name: Microsoft.FSharp.Collections.List.map
val filter : ('T -> bool) -> 'T list -> 'T list
Full name: Microsoft.FSharp.Collections.List.filter
val c : 'a (requires equality)
val not : bool -> bool
Full name: Microsoft.FSharp.Core.Operators.not
val firstPreference : (string * int) list -> string
Full name: Snippet.firstPreference
val vote : (string * int) list
type: (string * int) list
implements: System.Collections.IStructuralEquatable
implements: System.IComparable<List<string * int>>
implements: System.IComparable
implements: System.Collections.IStructuralComparable
implements: System.Collections.Generic.IEnumerable<string * int>
implements: System.Collections.IEnumerable
val min : ('a * 'b -> 'a * 'b -> 'a * 'b) (requires comparison)
val cp1 : 'a * 'b (requires comparison)
val cp2 : 'a * 'b (requires comparison)
val snd : ('T1 * 'T2) -> 'T2
Full name: Microsoft.FSharp.Core.Operators.snd
val fold : ('State -> 'T -> 'State) -> 'State -> 'T list -> 'State
Full name: Microsoft.FSharp.Collections.List.fold
namespace System
type Int32 =
struct
member CompareTo : obj -> int
member CompareTo : int -> int
member Equals : obj -> bool
member Equals : int -> bool
member GetHashCode : unit -> int
member GetTypeCode : unit -> System.TypeCode
member ToString : unit -> string
member ToString : string -> string
member ToString : System.IFormatProvider -> string
member ToString : string * System.IFormatProvider -> string
static val MaxValue : int
static val MinValue : int
static member Parse : string -> int
static member Parse : string * System.Globalization.NumberStyles -> int
static member Parse : string * System.IFormatProvider -> int
static member Parse : string * System.Globalization.NumberStyles * System.IFormatProvider -> int
static member TryParse : string * int -> bool
static member TryParse : string * System.Globalization.NumberStyles * System.IFormatProvider * int -> bool
end
Full name: System.Int32
type: System.Int32
implements: System.IComparable
implements: System.IFormattable
implements: System.IConvertible
implements: System.IComparable<int>
implements: System.IEquatable<int>
inherits: System.ValueType
field System.Int32.MaxValue = 2147483647
val add : 'a -> ('a * int) list -> ('a * int) list (requires equality)
Full name: Snippet.add
val candidateTotals : ('a * int) list (requires equality)
type: ('a * int) list
implements: System.Collections.IStructuralEquatable
implements: System.IComparable<List<'a * int>>
implements: System.IComparable
implements: System.Collections.IStructuralComparable
implements: System.Collections.Generic.IEnumerable<'a * int>
implements: System.Collections.IEnumerable
val incr : ('a * int -> 'a * int) (requires equality)
val ct : 'a * int (requires equality)
val isThereAWinner : ('a * float) list -> bool
Full name: Snippet.isThereAWinner
val result : ('a * float) list
type: ('a * float) list
implements: System.Collections.IStructuralEquatable
implements: System.IComparable<List<'a * float>>
implements: System.IComparable
implements: System.Collections.IStructuralComparable
implements: System.Collections.Generic.IEnumerable<'a * float>
implements: System.Collections.IEnumerable
val percentage : float
type: float
implements: System.IComparable
implements: System.IFormattable
implements: System.IConvertible
implements: System.IComparable<float>
implements: System.IEquatable<float>
inherits: System.ValueType
val firstPreferenceResult : string list -> (string * int) list list -> (string * float) list
Full name: Snippet.firstPreferenceResult
val candidates : string list
type: string list
implements: System.Collections.IStructuralEquatable
implements: System.IComparable<List<string>>
implements: System.IComparable
implements: System.Collections.IStructuralComparable
implements: System.Collections.Generic.IEnumerable<string>
implements: System.Collections.IEnumerable
val election : (string * int) list list
type: (string * int) list list
implements: System.Collections.IStructuralEquatable
implements: System.IComparable<List<(string * int) list>>
implements: System.IComparable
implements: System.Collections.IStructuralComparable
implements: System.Collections.Generic.IEnumerable<(string * int) list>
implements: System.Collections.IEnumerable
val totalNumberOfVotes : float
type: float
implements: System.IComparable
implements: System.IFormattable
implements: System.IConvertible
implements: System.IComparable<float>
implements: System.IEquatable<float>
inherits: System.ValueType
Multiple items
val float : 'T -> float (requires member op_Explicit)
Full name: Microsoft.FSharp.Core.Operators.float
--------------------
type float<'Measure> = float
Full name: Microsoft.FSharp.Core.float<_>
type: float<'Measure>
implements: System.IComparable
implements: System.IConvertible
implements: System.IFormattable
implements: System.IComparable<float<'Measure>>
implements: System.IEquatable<float<'Measure>>
inherits: System.ValueType
--------------------
type float = System.Double
Full name: Microsoft.FSharp.Core.float
type: float
implements: System.IComparable
implements: System.IFormattable
implements: System.IConvertible
implements: System.IComparable<float>
implements: System.IEquatable<float>
inherits: System.ValueType
val length : 'T list -> int
Full name: Microsoft.FSharp.Collections.List.length
val initialTotals : (string * int) list
type: (string * int) list
implements: System.Collections.IStructuralEquatable
implements: System.IComparable<List<string * int>>
implements: System.IComparable
implements: System.Collections.IStructuralComparable
implements: System.Collections.Generic.IEnumerable<string * int>
implements: System.Collections.IEnumerable
val c : string
type: string
implements: System.IComparable
implements: System.ICloneable
implements: System.IConvertible
implements: System.IComparable<string>
implements: seq<char>
implements: System.Collections.IEnumerable
implements: System.IEquatable<string>
val toPercentage : ('a * int -> 'a * float)
val candidate : 'a
val total : int
type: int
implements: System.IComparable
implements: System.IFormattable
implements: System.IConvertible
implements: System.IComparable<int>
implements: System.IEquatable<int>
inherits: System.ValueType
val addVote : ((string * int) list -> (string * int) list -> (string * int) list)
val candidateTotals : (string * int) list
type: (string * int) list
implements: System.Collections.IStructuralEquatable
implements: System.IComparable<List<string * int>>
implements: System.IComparable
implements: System.Collections.IStructuralComparable
implements: System.Collections.Generic.IEnumerable<string * int>
implements: System.Collections.IEnumerable
val electionResult : string list -> (string * int) list list -> unit
Full name: Snippet.electionResult
val result : (string * float) list
type: (string * float) list
implements: System.Collections.IStructuralEquatable
implements: System.IComparable<List<string * float>>
implements: System.IComparable
implements: System.Collections.IStructuralComparable
implements: System.Collections.Generic.IEnumerable<string * float>
implements: System.Collections.IEnumerable
val printfn : Printf.TextWriterFormat<'T> -> 'T
Full name: Microsoft.FSharp.Core.ExtraTopLevelOperators.printfn
val losers : string list
type: string list
implements: System.Collections.IStructuralEquatable
implements: System.IComparable<List<string>>
implements: System.IComparable
implements: System.Collections.IStructuralComparable
implements: System.Collections.Generic.IEnumerable<string>
implements: System.Collections.IEnumerable
val winners : string list
type: string list
implements: System.Collections.IStructuralEquatable
implements: System.IComparable<List<string>>
implements: System.IComparable
implements: System.Collections.IStructuralComparable
implements: System.Collections.Generic.IEnumerable<string>
implements: System.Collections.IEnumerable
val castVote : 'a list -> 'b list -> ('a * 'b) list
Full name: Snippet.castVote
val candidates : 'a list
type: 'a list
implements: System.Collections.IStructuralEquatable
implements: System.IComparable<List<'a>>
implements: System.IComparable
implements: System.Collections.IStructuralComparable
implements: System.Collections.Generic.IEnumerable<'a>
implements: System.Collections.IEnumerable
val preferences : 'b list
type: 'b list
implements: System.Collections.IStructuralEquatable
implements: System.IComparable<List<'b>>
implements: System.IComparable
implements: System.Collections.IStructuralComparable
implements: System.Collections.Generic.IEnumerable<'b>
implements: System.Collections.IEnumerable
val zip : 'T1 list -> 'T2 list -> ('T1 * 'T2) list
Full name: Microsoft.FSharp.Collections.List.zip
val candidates : string list
Full name: Snippet.candidates
type: string list
implements: System.Collections.IStructuralEquatable
implements: System.IComparable<List<string>>
implements: System.IComparable
implements: System.Collections.IStructuralComparable
implements: System.Collections.Generic.IEnumerable<string>
implements: System.Collections.IEnumerable
val election : (string * int) list list
Full name: Snippet.election
type: (string * int) list list
implements: System.Collections.IStructuralEquatable
implements: System.IComparable<List<(string * int) list>>
implements: System.IComparable
implements: System.Collections.IStructuralComparable
implements: System.Collections.Generic.IEnumerable<(string * int) list>
implements: System.Collections.IEnumerable
Thanks to Tomas P for the awesome F# web snippet generator over at fssnip.net