Records, sets and maps as abstract data types

ITT8060 Advanced Programming · Autumn 2026

Tallinn University of Technology

Full prose version with runnable examples: notes.html

ITT8060

Overview

Last week: a set as a list without duplicates, and the invariant was yours to keep. This week the library keeps it — and records get the rest of their story.

A type is a promise
Abstract data types hide the representation
One vocabulary for all collections
Records complete the modelling toolkit
Changing the representation changes the program

The complete programs — map colouring, the cash register three ways, the exercises — are in the notes under Worked examples.

ITT8060

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.

ITT8060

Four promises

A record names the parts of one thing: a name and an age — the AND-type beside lecture 4's OR-type unions.

A set promises membership only: order and repetition are 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.

ITT8060

Choose the representation

The tags on a blog post?

A set — a tag is present or absent; "fsharp, fsharp" is not two tags.

Student number → name?

A map — a number identifies one student; the lookup is the program.

A shopping basket?

A map from article code to count — 3 herrings + cheese + 2 herrings is cheese + 5 herrings.

The neighbours of a country?

A set of pairs, or a map from country to its set of neighbours — say which lookup you need. (Concept 5 faces exactly this choice.)

ITT8060

2 · Abstract data types hide the representation

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

ITT8060

The set concept

A set is a collection of elements: \(\{\text{Jüri}, \text{Mall}, \text{Mari}\}\), \(\{1, 3, 5, 7, 9\}\), \(\mathbb{N}\), \(\mathbb{R}\). Order and repetition are of no concern.

Membership is decidable: \(\text{Mart} \notin \{\text{Jüri}, \text{Mall}, \text{Mari}\}\) and \(7 \in \{1, 3, 5, 7, 9\}\). The empty set: \(\{\}\) or \(\emptyset\).

\(A \subseteq B\) if every element of \(A\) is in \(B\); \(A = B\) if and only if \(A \subseteq B\) and \(B \subseteq A\).

Set-builder: \(\{ 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 \}\).

ITT8060

Union, intersection, difference

\(A \cup B = \{ x \mid x \in A \text{ or } x \in B \}\) · \(A \cap B = \{ x \mid x \in A \text{ and } x \in B \}\) · \(A \setminus B = \{ x \in A \mid x \notin B \}\)

Set.union, Set.intersect and Set.difference compute exactly these. With names1 = set ["Jüri"; "Mall"; "Mari"] and names2 = set ["Mari"; "Mart"; "Tõnu"], Set.difference names1 names2 is set ["Jüri"; "Mall"].

ITT8060

Abstract data types

A type together with operations, where the representation of the values is hidden.

For sets: operations to generate a set from elements, to extract them again, and the standard operations. Why the first two?

Last week insert had to keep the list duplicate-free. Set.add does it for you — and you cannot break it.

Inside set [1; 3; 5; 7; 9]: a balanced tree you never see.

ITT8060

Predict: sets in F#

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

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

Duplicates go; the elements come out ordered.

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

true

Equality ignores order and repetition — as the mathematics says.

ITT8060

> 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

Spot the constraint

Why does set [sin; cos] not compile?

A set keeps its elements ordered, so the element type needs comparison — and functions have none.

The same constraint lecture 3 met in ordText sin cos.

Every Set and Map signature carries when 'a: comparison: on the elements of a set, on the keys of a map.

ITT8060

The map concept

A map from \(A\) to \(B\): a finite subset \(A'\) of \(A\) with a function \(m : A' \rightarrow B\). Its domain: \(\mathrm{dom}\,m = A'\).

key        value
a0         b0
a1         b1
...
a(n-1)     b(n-1)

\(a_i\) is a key, \((a_i, b_i)\) an entry, \(b_i\) the value for \(a_i\).

A map is a finite function: a key has exactly one value.

ITT8060

Predict: maps in F#

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

What does Map.add "a1" ("brie", 30) reg1 contain?

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

A present key is overridden: a key has one value.

What are Map.tryFind "a9" reg1 and Map.find "a9" reg1?

None
KeyNotFoundException: The given key was not present in the dictionary.

tryFind lets the caller decide; find and reg1["a2"] raise on a missing key.

ITT8060

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.

ITT8060

The same names, three libraries (1)

               List                    Set                 Map
from a list    the list itself         Set.ofList xs       Map.ofList kvs
to a list      the list itself         Set.toList s        Map.toList m
add one        x :: xs                 Set.add x s         Map.add k v m
remove one     List.filter ((<>) x) xs Set.remove x s      Map.remove k m
membership     List.contains x xs      Set.contains x s    Map.containsKey k m
exists         List.exists p xs        Set.exists p s      Map.exists p m
forall         List.forall p xs        Set.forall p s      Map.forall p m
filter, map    List.filter p xs        Set.filter p s      Map.filter p m

The Map versions pass the key and the value separately: fun k v -> ....

ITT8060

The same names, three libraries (2)

               List                    Set                 Map
fold           List.fold f e xs        Set.fold f e s      Map.fold f e m
foldBack       List.foldBack f xs e    Set.foldBack f s e  Map.foldBack f m e
size           List.length xs          Set.count s         Map.count m
smallest       List.min xs             Set.minElement s    Map.minKeyValue m
lookup         List.tryFind p xs       —                   Map.tryFind k m
set algebra    —                       Set.union, intersect, difference

Map lookup, three ways: Map.tryFind k m, Map.find k m, m[k].

The complete lists: the Set module and the Map module documentation.

ITT8060

Predict: folds follow the ordering

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

-6

\(((0 - 1) - 2) - 3\): lecture 4's left-nesting fold, with the set's ordering in place of the list's positions.

With small = Map.ofList ["b", 2; "a", 1], what is

Map.foldBack (fun k v l -> (k, v) :: l) small [] — a fold that visits the keys from the largest down and conses each?

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

Key order, whatever order the entries went in.

ITT8060

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.

ITT8060

AND-types and OR-types

Last week: a record is a tuple with named fields — { name = "Tõnu"; age = 12 }, p.age, { p with age = 13 }, record patterns. Today: what records are for.

A discriminated union says a value is one case or another. A record says a value has this part and that part.

Wlaschin: OR-types and AND-types. A domain model is built from both — and most data needs nothing else.

ITT8060

An annotation states the model

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

let areNb' c1 c2 m =
  Set.contains (c1, c2) m
  || Set.contains (c2, c1) m

val areNb: c1: Country -> c2: Country
           -> m: GMap -> bool
val areNb': c1: 'a -> c2: 'a -> m: Set<'a * 'a>
            -> bool when 'a: comparison

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

Labels drive inference the same way: with two record types sharing name, let f p = p.name picks the latest type — annotate to say which you mean.

ITT8060

Predict: records compare

type Person = { name: string; age: int }
let mari = { name = "Mari"; age = 12 }
let jüri = { name = "Jüri"; age = 40 }

What is compare mari jüri?

Field by field, in declaration order: name decides first.

So records satisfy comparison and can be set elements or map keys. What is set [mari; jüri; mari]?

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

Two elements, ordered by name.

ITT8060

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 ]

Records and maps in a model

A student is a record: an id and a name. StudentId is a one-case union — lecture 4's wrapper type — so an id is not an int.

Students is a map because the id identifies the student: the lookup is the program (concept 1).

What is students[StudentId 2].name?

"Rein"

The types say what the domain is — the style of Domain Modeling Made Functional.

ITT8060

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.

ITT8060

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] ]

Courses and who takes them

Which students take a course? A course code identifies the course; the students taking it are a set — nobody takes a course twice, and their order means nothing.

So Enrolments maps a course to a set: one lookup gives the whole class.

(kati, rein, liis: the students of the previous slide.)

ITT8060

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

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

let e2 = enrol "ITI0210" kati.id enrolments

Workflows are functions on the model

enrolled answers who takes this course? A course nobody has taken yet is the empty set — no exception, no 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.

What is enrolled "ITI0210" e2?

set [StudentId 1; StudentId 2; StudentId 3]

ITT8060

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

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

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

let katiMates = classmateNames "ITT8060" kati.id

Composition builds the workflow

f >> g 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, turn ids into names: a pipeline of small functions.

katiMates waits for the model. What is katiMates enrolments?

set ["Liis"; "Rein"]

ITT8060

The same workflow on another representation

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

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 (e: Enrolments2) =
  Set.filter (fun (c', _) -> c' = c) e
  |> Set.map (fun (_, s) -> s)
let enrol2 c s (e: Enrolments2) = Set.add (c, s) e

Concept 1's fourth scenario: a map to sets, or a set of pairs. Same questions on the other type — what is enrolled2 "ITI0210" enrolments2?

set [StudentId 2; StudentId 3]

Same answer — but enrol2 is one call and enrolled2 a scan over every pair: the type decided which operation is a lookup and which is a search.

ITT8060

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

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

Map colouring, in one slide

A map is a set of neighbouring pairs; a colouring a set of sets of countries — no country coloured twice, by type.

Recursion over a set as over a list: Set.minElement cols is the head, Set.remove col cols the tail, the empty set the base case.

colMap exampleMap?

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

The whole program: notes, Worked examples, A.

ITT8060

Summary

A type is a promise — record, set, map or list states what the program guarantees and what it rules out.
Abstract data types hide the representation — use the operations, reason with the specification, let the library keep the invariant.
One vocabulary for all collections — the list operations mean the same for sets and maps; folds follow the ordering.
Records complete the modelling toolkit — AND-types beside OR-types, compared field by field, usable as elements and keys.
Changing the representation changes the program — decide the type first.

ITT8060

Next week: recursive data types.

Reading: Hansen & Rischel, chapter 3 (records) and chapter 5 (sets and maps); as a companion, Wlaschin, Domain Modeling Made Functional, chapters 4 and 5.

The complete programs — map colouring, the cash register three ways, the practice task and the exercises — are in the notes under Worked examples: notes.html.

ITT8060