Maps and Sets

Map

A Map is an immutable dictionary: keys mapped to values, kept sorted by key.

let capitals =
    Map.ofList
        [ "France", "Paris"
          "Japan", "Tokyo"
          "Kenya", "Nairobi" ]

printfn "%s" capitals["Japan"]
printfn "%A" (capitals |> Map.tryFind "Peru")
printfn "%b" (capitals |> Map.containsKey "Kenya")
printfn "%d" capitals.Count

let updated =
    capitals
    |> Map.add "Peru" "Lima"
    |> Map.remove "France"

printfn "%A" updated
printfn "%d" capitals.Count

Tokyo
None
true
3
map [("Japan", "Tokyo"); ("Kenya", "Nairobi"); ("Peru", "Lima")]
3

• Map.add returns a new map (replacing the value if the key exists); the original is unchanged.
• map[key] throws if the key is missing; Map.tryFind returns an option.

Iterating and transforming

let stock = Map.ofList [ "apples", 12; "pears", 0; "plums", 7 ]

for KeyValue (fruit, count) in stock do
    printfn "%-7s %2d" fruit count

printfn "%A" (stock |> Map.filter (fun _ count -> count > 0))
printfn "%A" (stock |> Map.map (fun _ count -> count * 2))
printfn "%d" (stock |> Map.fold (fun total _ count -> total + count) 0)
printfn "%A" (stock |> Map.toList)
printfn "%A" (stock.Keys |> List.ofSeq)

apples  12
pears    0
plums    7
map [("apples", 12); ("plums", 7)]
map [("apples", 24); ("pears", 0); ("plums", 14)]
19
[("apples", 12); ("pears", 0); ("plums", 7)]
["apples"; "pears"; "plums"]

Updating counts

Map.change updates a value that may or may not exist yet — ideal for counters:

let addWord counts word =
    counts
    |> Map.change word (fun existing ->
        match existing with
        | Some n -> Some (n + 1)
        | None -> Some 1)

let counts =
    "to be or not to be".Split ' '
    |> Array.fold addWord Map.empty

printfn "%A" counts

map [("be", 2); ("not", 1); ("or", 1); ("to", 2)]

(Array.countBy id does the same in one call — but Map.change shows the general technique.)

Set

A Set is an immutable collection of unique values, kept sorted:

let a = Set.ofList [1; 2; 3; 4]
let b = Set.ofList [3; 4; 5]

printfn "%A" (Set.union a b)
printfn "%A" (Set.intersect a b)
printfn "%A" (Set.difference a b)
printfn "%b" (a |> Set.contains 2)
printfn "%A" (a |> Set.add 10 |> Set.remove 1)
printfn "%b" (Set.isSubset (Set.ofList [1; 2]) a)
printfn "%A" (Set.ofList ["b"; "a"; "b"])

set [1; 2; 3; 4; 5]
set [3; 4]
set [1; 2]
true
set [2; 3; 4; 10]
true
set ["a"; "b"]

Keys can be anything comparable

Tuples, records, and unions work as keys because F# gives them comparison automatically:

type Position = { Row: int; Col: int }

let board = Map.ofList [ { Row = 0; Col = 0 }, 'X'; { Row = 1; Col = 1 }, 'O' ]
printfn "%A" (board |> Map.tryFind { Row = 1; Col = 1 })
printfn "%A" (board |> Map.tryFind { Row = 2; Col = 2 })

Some 'O'
None

Practice

Given a list of (student, course) pairs, build a Map<string, Set<string>> from each course to the set of students taking it, and print it.

let enrollments =
    [ "Ada", "Math"; "Bob", "Art"; "Chen", "Math"; "Ada", "Art"; "Ada", "Math" ]

let byCourse =
    enrollments
    |> List.fold
        (fun courses (student, course) ->
            let current = courses |> Map.tryFind course |> Option.defaultValue Set.empty
            courses |> Map.add course (current |> Set.add student))
        Map.empty

for KeyValue (course, students) in byCourse do
    printfn "%s: %s" course (String.concat ", " students)

Art: Ada, Bob
Math: Ada, Chen