jonnifyfsharp

Dive C1.07.3

Map & Set

Two immutable trees: one for lookup by key, one for membership and set algebra.

Lists, arrays, and sequences are ordered — they answer "the elements, in turn". Two more containers answer different questions. A Map is an immutable key→value collection, a balanced tree: Map.tryFind looks a value up by its key and returns an option — Some v when the key is present, None when it is not. A Set is an immutable collection of distinct values: Set.ofList drops duplicates, and Set.union, Set.intersect, and Set.count give the algebra of sets. Reach for a Map over an association list when you look up by key, and for a Set when you ask about membership.

Look up and combine Module hub
C1.07.3 · part 1

Map: lookup by key

Map.ofList builds a map from a list of key–value pairs. Map.tryFind looks a key up and returns an option, so a missing key is an ordinary value — None — not an exception. Map.add returns a new map with the extra binding; the original is unchanged, like every immutable container in this module.

let m = Map.ofList [("a", 1); ("b", 2)]   // val m : Map<string,int> = map [("a", 1); ("b", 2)]

m |> Map.tryFind "a"           // val it : int option = Some 1
m |> Map.tryFind "z"           // val it : int option = None
m |> Map.add "c" 3              // a new map; m itself is unchanged
Map<'K,'V>
an immutable key→value collection, kept as a balanced tree.
Map.ofList
build a map from a list of (key, value) pairs.
Map.tryFind
look up a key, returning Some v or None — never an exception.
Map.add
returns a new map with the binding added; the input map is unchanged.

Because Map.tryFind returns an option, the next module — Option & Result — picks the result up directly: an absent key and an absent value are the same None, handled the same way.

C1.07.3 · part 2

Set: membership and algebra

A set holds distinct values. Set.ofList builds one from a list and drops any duplicates as it goes — so [1; 2; 2; 3] becomes a set of three. The set operations return new sets: Set.union for everything in either, Set.intersect for what is in both, and Set.count for how many.

Set.ofList [1; 2; 2; 3] |> Set.count     // val it : int = 3   (the duplicate dropped)

let s1 = Set.ofList [1; 2; 3; 4]
let s2 = Set.ofList [3; 4; 5; 6]
Set.union s1 s2                       // val it : Set<int> = set [1; 2; 3; 4; 5; 6]
Set.intersect s1 s2                   // val it : Set<int> = set [3; 4]
Set<'T>
an immutable collection of distinct values, kept as a balanced tree.
Set.ofList
build a set from a list, dropping duplicates.
Set.union
a new set with every element in either set.
Set.intersect
a new set with only the elements in both sets.

Look up a key, combine two sets

The map below is [("a",1); ("b",2); ("c",3)]. Pick a key to look it up: a present key returns Some v, the absent "x" returns None. The two sets are {1;2;3;4} and {3;4;5;6}; choose an operation to see its result. Every value here matches dotnet fsi.

Map.tryFind · pick a key

"a" → 1 "b" → 2 "c" → 3 Map.tryFind "a" Some 1
m |> Map.tryFind "a" = Some 1 · the key is present, so its value comes back wrapped in Some

Set algebra · {1;2;3;4} and {3;4;5;6}

s1 s2 1 2 3 4 5 6
Set.union s1 s2 = set [1; 2; 3; 4; 5; 6] · every element in either set, with no duplicates

Two questions, two containers: "what is stored here" is a Map and an option; "is this in the set" is a Set and its algebra. Both immutable, both returning new values.

Lookup & membership

A Map answers by key and returns an option; a Set answers by membership and combines with union and intersect.

F# today

Map.tryFind hands back Some v or None — the option type the next module is built on.

Where this leads

That closes the collections module: the list, array, and seq for ordered values; the module functions to transform them; and Map and Set for lookup and membership. One result keeps recurring — Map.tryFind returns an option. The next module makes that type its subject: Option for a value that may be absent, and Result for an operation that may fail, both handled as ordinary values rather than as exceptions.

↑ C1.07 · Collections C1.07.1 · List, array & seq C1.07.2 · Transforming collections

References

Sources

Related in this course