Lecture 5 — Records, sets and maps as abstract data types

Last week's closing exercise represented a set as a list without duplicates and made you preserve that invariant by hand in insert and union; this week the library does it for you. Lecture 4 also opened records and promised the rest: it is here, in concept 4. The complete programs (map colouring, the cash register in three versions, the exercises) are in the worked examples at the end of these notes.

1. A type is a promise

Choosing a type is a modelling decision: the type states what the program promises and what it rules out.

• A record names the parts of one thing — a person has a name and an age. It is the AND-type that complements lecture 4's discriminated unions, whose value is one case or another.
• A set promises membership only: the order in which elements were added, and how many times, is meaningless.
• A map is a finite function: every key has exactly one value, and a key is looked up, not searched for.
• A list promises order and allows repetition: use it when the position matters.

Choose the representation

Why it matters: a wrong promise is a bug you must fix in every function. A list standing for a set needs every operation to remove duplicates (last week's insert); a set standing for a basket loses the counts.

2. Abstract data types hide the representation

A set or a map is used through its operations and reasoned about through its mathematical specification, never through the tree inside.

The set concept

A set is a collection of elements such as \(\{\text{Jüri}, \text{Mall}, \text{Mari}\}\), \(\{1, 3, 5, 7, 9\}\), \(\mathbb{N}\) and \(\mathbb{R}\), where

• the sequence in which the elements are enumerated is of no concern, and
• repetitions among the elements are of no concern either.

It is possible to decide whether a value is in the set: \(\text{Mart} \notin \{\text{Jüri}, \text{Mall}, \text{Mari}\}\) and \(7 \in \{1, 3, 5, 7, 9\}\). The empty set is written \(\{\}\) or \(\emptyset\).

\(A\) is a subset of \(B\), \(A \subseteq B\), if every element of \(A\) is an element of \(B\); two sets are equal when they are subsets of each other: \(A = B\) if and only if \(A \subseteq B\) and \(B \subseteq A\). The elements of \(A\) that satisfy a predicate \(p\) form the set \(\{ x \in A \mid p(x) \}\), for example \(\{1, 3, 5, 7, 9\} = \{ x \in \mathbb{N} \mid \text{odd}(x) \text{ and } x < 11 \}\).

The standard operations, with the result shaded:

\[\begin{array}{lcll} A \cup B & = & \{ x \mid x \in A \text{ or } x \in B \} & \text{union} \\ A \cap B & = & \{ x \mid x \in A \text{ and } x \in B \} & \text{intersection} \\ A \setminus B & = & \{ x \in A \mid x \notin B \} & \text{difference} \end{array}\]

In F# the Set library provides the operations under their mathematical names, and the specification is what they compute: \(\verb!union! \ A \ B = A \cup B\), \(\verb!intersect! \ A \ B = A \cap B\), \(\verb!difference! \ A \ B = A \setminus B\), \(\verb!contains! \ a \ A = a \in A\).

let names1 = set ["Jüri"; "Mall"; "Mari"]
let names2 = set ["Mari"; "Mart"; "Tõnu"]

let namesUnion = Set.union names1 names2
let namesInter = Set.intersect names1 names2
let namesDiff = Set.difference names1 names2

set ["Jüri"; "Mall"; "Mari"; "Mart"; "Tõnu"]

set ["Mari"]

set ["Jüri"; "Mall"]

Abstract data types

An abstract data type is a type together with a collection of operations, where the representation of the values is hidden. One for sets must have operations to generate a set from elements and to extract them again — else you could neither build nor use one — and the standard operations.

Last week insert had to keep the list duplicate-free; Set.add does it for you, and because the representation is hidden you cannot break it. Inside set [1; 3; 5; 7; 9] the library keeps a balanced binary tree — this one, on the course toolchain — but no operation lets you see it, and you never need to:

Sets in F#: predict, then check

What is set [3; 1; 9; 5; 7; 9; 1]?

let odds = set [3; 1; 9; 5; 7; 9; 1]

set [1; 3; 5; 7; 9]

Duplicates go and the elements come out ordered: the library keeps them sorted.

Is set ["Jüri"; "Mall"; "Mari"] = set ["Mari"; "Jüri"; "Mari"; "Mall"]?

let sameNames =
  set ["Jüri"; "Mall"; "Mari"] = set ["Mari"; "Jüri"; "Mari"; "Mall"]

true

Equality is structural and ignores order and repetition, exactly as the mathematics says. Sets are also ordered, lexicographically by their sorted elements: what is compare (set ["Andres"; "Piret"]) names1?

let compareSets = compare (set ["Andres"; "Piret"]) names1

-9

The sorted first elements decide, as they would for two strings.

Spot the constraint

Why does set [sin; cos] not compile?

> set [sin; cos];;

  set [sin; cos];;
  -----^^^

stdin(1,6): error FS0001: The type ''a -> 'a' does not support the 'comparison' constraint. For example, it does not support the 'System.IComparable' interface

The same constraint lecture 3 met in ordText sin cos (lecture 3 notes): a set keeps its elements ordered, so the element type needs comparison, and functions have none. Every Set and Map signature carries when 'a: comparison — on the elements of a set, on the keys of a map.

The map concept

A map from a set \(A\) to a set \(B\) is a finite subset \(A'\) of \(A\) together with a function \(m\) defined on \(A'\): \(m : A' \rightarrow B\). The set \(A'\) is the domain of \(m\), \(\mathrm{dom}\,m = A'\). A map can be described in tabular form:

Each \(a_i\) is a key, each pair \((a_i, b_i)\) an entry, and \(b_i\) is the value for the key \(a_i\). A map is a finite function: a key has exactly one value.

Maps in F#

Map.ofList builds a map from its entries; a register of articles, adapted from Michael R. Hansen's slides, maps an article code to a name and a price:

let reg1 =
  Map.ofList [ ("a1", ("cheese", 25)); ("a2", ("herring", 4))
               ("a3", ("soft drink", 5)) ]

map [("a1", ("cheese", 25)); ("a2", ("herring", 4)); ("a3", ("soft drink", 5))]

Map.add adds an entry (\(\verb!add! \ a \ b \ m\) is \(m\) overridden with the entry \((a, b)\)). What does Map.add "a1" ("brie", 30) reg1 contain?

let reg1Brie = Map.add "a1" ("brie", 30) reg1

map [("a1", ("brie", 30)); ("a2", ("herring", 4)); ("a3", ("soft drink", 5))]

Adding a present key overrides its value: a key has one value, so there is nothing else add could do.

A lookup has three forms. What are Map.tryFind "a9" reg1 and Map.find "a9" reg1?

let tryA2 = Map.tryFind "a2" reg1
let tryA9 = Map.tryFind "a9" reg1
let idxA2 = reg1["a2"]

Some ("herring", 4)

None

("herring", 4)

> Map.find "a9" reg1;;
System.Collections.Generic.KeyNotFoundException: The given key was not present in the dictionary.
   at Microsoft.FSharp.Collections.MapModule.Find[TKey,T](TKey key, FSharpMap`2 table)
Stopped due to error

\(\verb!tryFind! \ a \ m = \mathtt{Some}\ (m(a))\) if \(a \in \mathrm{dom}\,m\) and \(\mathtt{None}\) otherwise: an option (lecture 4) that lets the caller decide. \(\verb!find! \ a \ m = m(a)\) if \(a \in \mathrm{dom}\,m\), otherwise an exception; the indexer m[key] is the same lookup in the notation of every other .NET collection. Use tryFind where a lookup may fail and you can act on it, find where the program has no answer for a missing key.

Why it matters: the specification is the whole contract — equality, the comparison constraint, overriding add — and none of it depends on the tree.

3. One vocabulary for all collections

The list operations you know mean the same for sets and maps; learn the pattern once and look up the rest.

The Map versions of exists, forall, filter, map and fold pass the key and the value separately (fun k v -> ...). Each has a specification in the style of concept 2: \(\verb!ofList!\ [a_0; \ldots; a_{n-1}] = \{a_0, \ldots, a_{n-1}\}\) and \(\verb!toList!\ \{a_0, \ldots, a_{n-1}\} = [a_0; \ldots; a_{n-1}]\) in the ordering; \(\verb!add!\ a\ A = \{a\} \cup A\), \(\verb!remove!\ a\ A = A \setminus \{a\}\), \(\verb!minElement!\ \{a_0, \ldots, a_{n-1}\} = a_0\) for \(n > 0\); \(\verb!exists!\ p\ A = \exists x \in A.\ p(x)\), \(\verb!forall!\ p\ A = \forall x \in A.\ p(x)\), \(\verb!filter!\ p\ A = \{ x \in A \mid p(x) \}\); \(\verb!fold!\ f\ e\ \{b_0, \ldots, b_{n-1}\} = f(\cdots f(f(e, b_0), b_1) \cdots, b_{n-1})\) and, for a map with keys \(a_0 < \cdots < a_{n-1}\), \(\verb!foldBack!\ f\ m\ c = f\ a_0\ b_0\ (f\ a_1\ b_1\ (\cdots (f\ a_{n-1}\ b_{n-1}\ c)))\); the map lookups and add were specified in concept 2. The complete lists are the Set module and the Map module documentation. The types, as F# Interactive prints them:

> Set.union;;
val it: (Set<'a> -> Set<'a> -> Set<'a>) when 'a: comparison
> Set.fold;;
val it: (('a -> 'b -> 'a) -> 'a -> Set<'b> -> 'a) when 'b: comparison
> Map.tryFind;;
val it: ('a -> Map<'a,'b> -> 'b option) when 'a: comparison
> Map.foldBack;;
val it: (('a -> 'b -> 'c -> 'c) -> Map<'a,'b> -> 'c -> 'c) when 'a: comparison

The one twist: folds follow the ordering

What is Set.fold (-) 0 (set [1; 2; 3])?

let foldMinus = Set.fold (-) 0 (set [1; 2; 3])

-6

Set.fold combines from the smallest element up, so this is \(((0 - 1) - 2) - 3\): lecture 4's left-nesting fold, with the set's ordering in place of positions.

With small = Map.ofList ["b", 2; "a", 1], the fold Map.foldBack (fun k v l -> (k, v) :: l) small [] visits the keys from the largest down and conses each, so the entries come out in key order whatever order they went in:

let small = Map.ofList ["b", 2; "a", 1]
let keyOrder = Map.foldBack (fun k v l -> (k, v) :: l) small []

[("a", 1); ("b", 2)]

Hansen's version lists the codes and prices of the register:

let codesAndPrices =
  Map.foldBack (fun ac (_, p) cps -> (ac, p) :: cps) reg1 []

[("a1", 25); ("a2", 4); ("a3", 5)]

For the same reason Set.minElement is well defined:

let firstName = Set.minElement (set ["Mari"; "Jüri"; "Mall"])

"Jüri"

Why it matters: you can already read Set.forall or Map.foldBack — the shape is lecture 4's — and the one thing to remember is that a fold sees the elements or keys in their ordering.

4. Records complete the modelling toolkit

A record is the AND-type that names the parts of one thing; with unions it completes the toolkit for modelling data.

Last week: records are tuples with named fields, constructed with { ... }, read with a dot, copied with with and usable as patterns (lecture 4 notes).

AND-types and OR-types

A discriminated union says a value is one case or another; a record says a value has this part and that part. Scott Wlaschin calls them OR-types and AND-types: a domain model is built from both, and most data needs nothing else.

Labels drive inference; an annotation states the model

The compiler infers a record type from the labels you use, and the latest type with that label wins:

> type A = { name: string; age: int };;
> type B = { name: string; email: string };;
> let f p = p.name;;
val f: p: B -> string

> let g (p: A) = p.name;;
val g: p: A -> string

An annotation is not there to help the compiler; it says which type you mean. The map-colouring program of worked example A annotates its neighbour test for the same reason:

> type Country = string;;
> type GMap = Set<Country * Country>;;
> let areNb (c1: Country) (c2: Country) (m: GMap) =
-   Set.contains (c1, c2) m || Set.contains (c2, c1) m;;
val areNb: c1: Country -> c2: Country -> m: GMap -> bool

> let areNb' c1 c2 m = Set.contains (c1, c2) m || Set.contains (c2, c1) m;;
val areNb': c1: 'a -> c2: 'a -> m: Set<'a * 'a> -> bool when 'a: comparison

Both compile and both work on the example map; the first says what a GMap is, the second says the code does not care. When the types are the model, state them.

Structural equality and ordering

Records compare structurally, field by field in declaration order. With mari = { name = "Mari"; age = 12 } and jüri = { name = "Jüri"; age = 40 }, what is compare mari jüri?

type Person = { name: string; age: int }

let mari = { name = "Mari"; age = 12 }
let jüri = { name = "Jüri"; age = 40 }

let personOrder = compare mari jüri

3

name decides before age is looked at (compare "Mari" "Jüri" is 3). So records satisfy comparison, and a record can be a set element or a map key. What is set [mari; jüri; mari]?

let people = set [mari; jüri; mari]

set [{ name = "Jüri"
       age = 40 }; { name = "Mari"
                     age = 12 }]

Two elements — the duplicate is gone — ordered by name, the first field.

Records and maps in a model

A student has an id and a name, and students are found by id. In the style of Domain Modeling Made Functional, the types say so:

type StudentId = StudentId of int
type Student = { id: StudentId; name: string }
type Students = Map<StudentId, Student>

let kati = { id = StudentId 1; name = "Kati" }
let rein = { id = StudentId 2; name = "Rein" }
let liis = { id = StudentId 3; name = "Liis" }

let students: Students =
  Map.ofList [ kati.id, kati; rein.id, rein; liis.id, liis ]

StudentId is a one-case union — lecture 4's wrapper type — so an id is not an int and cannot be confused with an age or a count. Student is the AND-type. Students is a map because the id identifies the student: the lookup is the program (concept 1). What is students[StudentId 2].name?

let reinName = students[StudentId 2].name

"Rein"

Why it matters: reach for a record when a thing has parts you want named; with unions for the alternatives and maps for the lookups, that is the whole toolkit.

5. Changing the representation changes the program

Change the type of the data and the shape of the program changes with it; that is why the choice of type comes first.

Courses and who takes them

Which students take a course? A course code identifies the course, and the students taking it are a set: nobody takes a course twice, and their order means nothing. So the model is a map from course to set — one lookup gives the whole class:

type Course = string
type Enrolments = Map<Course, Set<StudentId>>

let enrolments: Enrolments =
  Map.ofList
    [ "ITT8060", set [kati.id; rein.id; liis.id]
      "ITI0210", set [rein.id; liis.id] ]

Workflows are functions on the model

enrolled answers who takes this course? — a course nobody has taken yet is the empty set, not an exception and not a None to carry around. enrol records a student: look up, add to the set, put back; the map is immutable, so the result is a new Enrolments.

let enrolled (c: Course) (e: Enrolments) : Set<StudentId> =
  match Map.tryFind c e with
  | Some ss -> ss
  | None -> Set.empty

let enrol (c: Course) (s: StudentId) (e: Enrolments) : Enrolments =
  Map.add c (Set.add s (enrolled c e)) e

let e2 = enrol "ITI0210" kati.id enrolments

What is enrolled "ITI0210" e2?

let afterEnrol = enrolled "ITI0210" e2

set [StudentId 1; StudentId 2; StudentId 3]

Composition builds the workflow from its parts

f >> g is the function that applies f, then g: (f >> g) x = g (f x). Who shares a course with a student? Take the course's set, remove the student, then turn the ids into names through students:

let classmates (c: Course) (s: StudentId) : Enrolments -> Set<StudentId> =
  enrolled c >> Set.remove s

let names (st: Students) : Set<StudentId> -> Set<string> =
  Set.map (fun s -> st[s].name)

let classmateNames c s = classmates c s >> names students

let katiMates = classmateNames "ITT8060" kati.id

No intermediate variables and no loop: the workflow is a pipeline of small functions, which is how Domain Modeling Made Functional builds every workflow (lecture 7 adds error handling to the pipeline). katiMates is still a function — it waits for the model. What is katiMates enrolments?

let katiClassmates = katiMates enrolments

set ["Liis"; "Rein"]

The same workflow on another representation

Concept 1's fourth scenario offered two types for a relation: a map to sets, or a set of pairs. Take the other one and ask the same questions:

type Enrolments2 = Set<Course * StudentId>

let enrolments2: Enrolments2 =
  set [ "ITT8060", kati.id; "ITT8060", rein.id; "ITT8060", liis.id
        "ITI0210", rein.id; "ITI0210", liis.id ]

let enrolled2 (c: Course) (e: Enrolments2) : Set<StudentId> =
  Set.filter (fun (c', _) -> c' = c) e |> Set.map (fun (_, s) -> s)

let enrol2 (c: Course) (s: StudentId) (e: Enrolments2) : Enrolments2 =
  Set.add (c, s) e

What is enrolled2 "ITI0210" enrolments2?

let inAI = enrolled2 "ITI0210" enrolments2

set [StudentId 2; StudentId 3]

The same answer as enrolled "ITI0210" enrolments — but enrol2 is one call and enrolled2 a scan over every pair, where before enrol did the work and enrolled was a lookup. The type decided which operation is a lookup and which is a search, and it said so before a line of code was written.

The other worked examples

Map colouring (worked example A) models a map as a set of neighbouring pairs and a colouring as a set of sets:

type Country = string
type GMap = Set<Country * Country>
type Color = Set<Country>
type Coloring = Set<Color>

Set<Set<Country>> says a colour is a group of countries with no order and no repetition, and a colouring a group of such groups — the types already rule out colouring a country twice. The program recurses over a set as it would over a list: Set.minElement is the head, Set.remove gives the tail and the empty set is the base case. The cash register (worked example B) makes the same point as the enrolments: a purchase as a list and as a map give the same bill from two differently shaped programs.

Why it matters: when a program feels awkward, question the type before the code. A set of pairs turned a lookup into a scan; a colouring as a set of sets made "no country twice" a fact of the type.

Summary

1. A type is a promise: the type states what the program guarantees and rules out.
2. Abstract data types hide the representation: use the operations, reason with the specification.
3. One vocabulary for all collections: list operations mean the same for sets and maps; folds follow the ordering.
4. Records complete the modelling toolkit: AND-types beside OR-types, usable as elements and keys.
5. Changing the representation changes the program: decide the type first.

Next

Next week: recursive data types. Reading: Hansen & Rischel, chapter 3 (records) and chapter 5 (sets and maps); as a companion, the type-modelling chapters of Scott Wlaschin's Domain Modeling Made Functional (chapters 4 and 5).

Worked examples

Complete programs for self-study; every result is computed by the build.

A. Map colouring

(An example adapted from Michael R. Hansen's slides.) The types are declared in concept 5. Two countries are neighbours if either pair is in the map; a colour can be extended by a country with no neighbour in it:

let areNb (c1: Country) (c2: Country) (m: GMap) : bool =
  Set.contains (c1, c2) m || Set.contains (c2, c1) m

let canBeExtBy (m: GMap) (col: Color) (c: Country) : bool =
  Set.forall (fun c' -> not (areNb c' c m)) col

extColoring adds a country to the first colour that accepts it, or as a new colour. It is recursive rather than a fold because it stops as soon as a colour accepts the country; base case the empty set, head Set.minElement cols, tail Set.remove col cols.

let rec extColoring (m: GMap) (cols: Coloring) (c: Country) : Coloring =
  if Set.isEmpty cols then Set.singleton (Set.singleton c)
  else
    let col = Set.minElement cols
    let cols' = Set.remove col cols
    if canBeExtBy m col c then Set.add (Set.add c col) cols'
    else Set.add col (extColoring m cols' c)

The countries of a map are collected by folding over its pairs, a colouring of a set of countries by folding extColoring over them, and colMap composes the two.

let countries (m: GMap) : Set<Country> =
  Set.fold (fun cs (c1, c2) -> Set.add c1 (Set.add c2 cs)) Set.empty m

let colCntrs (m: GMap) (cs: Set<Country>) : Coloring =
  Set.fold (extColoring m) Set.empty cs

let colMap (m: GMap) : Coloring = colCntrs m (countries m)

let exampleMap: GMap =
  Set.ofList [("a", "b"); ("c", "d"); ("d", "a")]

let colouring1 = colMap exampleMap

set [set ["a"; "c"]; set ["b"; "d"]]

B. The cash register, three ways

An example adapted from Michael R. Hansen's slides. A register maps article codes to articles, because a code identifies an article uniquely; an article is a record (concept 4); a purchase is first a list of (pieces, code) in the order scanned; a bill lists each item with its total, and the sum.

type ArticleCode = string
type ArticleName = string
type Price = int
type NoPieces = int

type Article = { name: ArticleName; price: Price }
type Register = Map<ArticleCode, Article>
type Info = NoPieces * ArticleName * Price
type Bill = Info list * Price
type Purchase = (NoPieces * ArticleCode) list

let register1: Register =
  Map.ofList
    [ "a1", { name = "cheese"; price = 25 }
      "a2", { name = "herring"; price = 4 }
      "a3", { name = "soft drink"; price = 5 } ]

let purchase1: Purchase = [(3, "a2"); (1, "a1")]

Version 1 is explicit recursion over the purchase list, with tryFind and an exception of our own for an unknown code. Version 2 names the recursion: it is List.foldBack (lecture 4), with find because a fold cannot stop early, so there is no bill for an unknown code (lecture 7 is about handling that).

exception UnknownArticle of ArticleCode

let rec makeBillRec (reg: Register) (pur: Purchase) : Bill =
  match pur with
  | [] -> ([], 0)
  | (np, ac) :: rest ->
    match Map.tryFind ac reg with
    | None -> raise (UnknownArticle ac)
    | Some art ->
      let tprice = np * art.price
      let (infos, total) = makeBillRec reg rest
      ((np, art.name, tprice) :: infos, tprice + total)

let makeBillFold (reg: Register) (pur: Purchase) : Bill =
  let f (np, ac) (infos, total) =
    let art = Map.find ac reg
    let tprice = np * art.price
    ((np, art.name, tprice) :: infos, tprice + total)
  List.foldBack f pur ([], 0)

Version 3 changes the representation. The purchase 3 herrings, one cheese, 2 herrings is the purchase one cheese, 5 herrings: what a purchase promises is a count per article — a map from code to pieces — and the fold changes with the type:

type PurchaseMap = Map<ArticleCode, NoPieces>

let purchaseMap1: PurchaseMap = Map.ofList [("a2", 3); ("a1", 1)]

map [("a1", 1); ("a2", 3)]

let makeBillMap (reg: Register) (pur: PurchaseMap) : Bill =
  let f ac np (infos, total) =
    let art = Map.find ac reg
    let tprice = np * art.price
    ((np, art.name, tprice) :: infos, tprice + total)
  Map.foldBack f pur ([], 0)

The three, on the same purchase:

let billRec = makeBillRec register1 purchase1
let billFold = makeBillFold register1 purchase1
let billMap = makeBillMap register1 purchaseMap1

([(3, "herring", 12); (1, "cheese", 25)], 37)

([(3, "herring", 12); (1, "cheese", 25)], 37)

([(1, "cheese", 25); (3, "herring", 12)], 37)

Same total; the items come in purchase order from the list and in key order (a1 before a2) from the map, because a map has no order but its keys'. Only the type of pur, the arguments of f and the fold changed. With an unknown article, version 1 raises its own exception and versions 2 and 3 the library's:

> makeBillRec register1 [(1, "a9")];;
FSI_0008+UnknownArticle: UnknownArticle "a9"
Stopped due to error

> makeBillFold register1 [(1, "a9")];;
System.Collections.Generic.KeyNotFoundException: The given key was not present in the dictionary.
Stopped due to error

C. A practice task

Rewrite the listing of codes and prices, Map.foldBack (fun ac (_, p) cps -> (ac, p) :: cps) reg1 [], with Map.fold. What needs to change?

let codesAndPricesFold =
  Map.fold (fun cps ac (_, p) -> (ac, p) :: cps) [] reg1

[("a3", 5); ("a2", 4); ("a1", 25)]

The accumulator comes first, both in f and in the call, and because fold visits the keys upward while consing, the list comes out reversed.

D. Exercises

Holidays. The script built this map with a chain of .Add method calls; Map.ofList says the same in one expression. Add a holiday, and look one up with tryFind.

let holidays =
  Map.ofList [ ("Christmas", "Dec. 25"); ("Halloween", "Oct. 31")
               ("Darwin Day", "Feb. 12"); ("World Vegan Day", "Nov. 1") ]

let christmas = holidays["Christmas"]

"Dec. 25"

Subsets. State isSubset and isSuperset as specification equations, as concept 2 does for union, and check them:

let a = set [1 .. 10]
let b = set [5 .. 15]
let c = set [2; 4; 5; 9]

let cInA = Set.isSubset c a
let cInB = Set.isSubset c b
let aOverC = Set.isSuperset a c

true

false

true

Lecture 4's set functions, on Set. Write disjoint, subset and inter for Set<'a>; each is one library call or a one-line Set.forall. Which invariant did the list versions have to preserve that these get for free?

Enrolments, continued. Write drop : Course -> StudentId -> Enrolments -> Enrolments for both representations, and coursesOf : StudentId -> Enrolments -> Set<Course> — which representation makes the second one a scan?

Efficiency. A list-based extColoring is more efficient than the set-based one. Why? Compare what Set.minElement and Set.remove cost on a balanced tree with matching x :: xs, and what the set version buys.