F# · Lesson 8
Maps and Sets
Immutable Map and Set, grouping and counting, building lookup indexes, and when a mutable Dictionary or HashSet is the right call.
In short
MapandSetare immutable: changes return new collectionsMap.tryFindreturns an option;Map.changeupdates from the old value- Sets give union, intersect, difference and subset checks
groupByandcountBywithMap.ofListbuild indexes- Use
DictionaryandHashSetfor hot paths, kept local
Map: an immutable dictionary
F#'s Map<'Key, 'Value> plays the role of a JS Map or a Record<string, T>, with one big difference: it is
immutable. "Adding" a key returns a new map, and the old one is untouched. Under the hood it's a balanced tree
that shares most of its structure with the old map, so this is cheap (O(log n)), not a full copy.
const prices = new Map<string, number>([["apple", 0.5], ["pear", 0.75]]);
prices.set("kiwi", 0.3); // mutates prices
const apple = prices.get("apple"); // number | undefined
let prices = Map.ofList [ "apple", 0.5; "pear", 0.75 ]
let withKiwi = prices |> Map.add "kiwi" 0.3 // new map; `prices` still has 2 entries
let apple = prices |> Map.tryFind "apple" // Some 0.5 (a float option)
Line by line:
Map.ofListbuilds a map from a list of(key, value)tuples."apple", 0.5is a tuple; the parentheses are optional inside a list.Map.add key value mapreturns a new map. If the key exists, its value is replaced.Map.tryFindreturns an option instead ofundefined, so a missing key can't be ignored.
Keys must support comparison (strings, numbers, tuples, records and unions all do), and iteration is sorted by key,
not insertion order like a JS Map.
| F# | TS (Map) |
|---|---|
Map.empty | new Map() |
Map.add k v m | m.set(k, v) (but returns a new map) |
Map.remove k m | m.delete(k) |
Map.tryFind k m | m.get(k) |
Map.containsKey k m | m.has(k) |
Map.find k m or m.[k] | m.get(k)! (throws if missing) |
Map.count m | m.size |
Map.toList m | [...m.entries()] |
Map.filter (fun k v -> ...) m | no direct equivalent |
Map.fold (fun acc k v -> ...) init m | [...m].reduce(...) |
Updating a value: Map.change
The classic "increment a counter" needs the old value. Map.change gives you the current value as an option and lets you return the new one (or None to delete the key):
counts.set(word, (counts.get(word) ?? 0) + 1);
let increment (word: string) (counts: Map<string, int>) : Map<string, int> =
counts
|> Map.change word (fun current ->
match current with
| Some n -> Some(n + 1) // existing key: bump it
| None -> Some 1) // new key: start at 1
Build a whole map by folding over the input, starting from Map.empty:
let countWords (words: string list) : Map<string, int> =
words |> List.fold (fun counts word -> increment word counts) Map.empty
Set: unique values
const a = new Set(["read", "write"]);
const b = new Set(["write", "admin"]);
const union = new Set([...a, ...b]);
const both = new Set([...a].filter(x => b.has(x)));
let a = set [ "read"; "write" ] // `set` is shorthand for Set.ofList
let b = Set.ofList [ "write"; "admin" ]
let union = Set.union a b // set ["admin"; "read"; "write"]
let both = Set.intersect a b // set ["write"]
let onlyA = Set.difference a b // set ["read"] (also: a - b)
let canRead = a |> Set.contains "read" // true
let more = a |> Set.add "delete" // new set
Sets compare by value: set [ 1; 2 ] = set [ 2; 1 ] is true. That makes them great in tests and as map values.
Set.unionMany merges a whole list of sets, and Set.isSubset checks "has all of these".
Grouping and counting
// with lodash
const byStatus = _.groupBy(orders, o => o.status);
const counts = _.countBy(orders, o => o.status);
let byStatus : (Status * Order list) list = orders |> List.groupBy (fun o -> o.Status)
let counts : Map<Status, int> = orders |> List.countBy (fun o -> o.Status) |> Map.ofList
List.groupByreturns a list of(key, itemsWithThatKey)pairs. Items keep their original order within each group.List.countByreturns(key, count)pairs.Seq.groupByandSeq.countBydo the same for any sequence (an array, a database result, aseq { }).- Pipe into
Map.ofList/Map.ofSeqto get a lookup table. If the list has duplicate keys, the last one wins.
Building indexes
An index is a map from a key to either one record (unique key) or a list of records (grouping):
type Customer = { Id: int; Email: string; Country: string }
let byId : Map<int, Customer> =
customers |> List.map (fun c -> c.Id, c) |> Map.ofList
let byCountry : Map<string, Customer list> =
customers |> List.groupBy (fun c -> c.Country) |> Map.ofList
Looking something up with List.tryFind scans the whole list (O(n)). Doing that inside a loop over another list is
O(n²), the classic slow report. Build the map once, then every lookup is O(log n).
Dictionary and HashSet: when mutation is OK
.NET's System.Collections.Generic.Dictionary and HashSet are mutable, hash-based collections, the closest thing to
JS's Map and Set. They are faster for heavy workloads (O(1) average). Use them for hot loops, large data, caches and
memoization, and when a .NET API asks for them. Keep the mutation local: create it inside a function, fill it, and
return an immutable result.
const seen = new Set<string>();
const unique = ids.filter(id => {
if (seen.has(id)) return false;
seen.add(id);
return true;
});
open System.Collections.Generic
let dedupe (ids: string list) : string list =
let seen = HashSet<string>()
ids |> List.filter (fun id -> seen.Add id) // Add returns false if it was already there
let cache = Dictionary<string, int>()
cache.["a"] <- 1 // set via the indexer; `<-` assigns
match cache.TryGetValue "a" with // the out parameter becomes a tuple
| true, value -> printfn "hit %d" value
| false, _ -> printfn "miss"
Map / Set | Dictionary / HashSet | |
|---|---|---|
| Changes | return a new collection | mutate in place |
| Lookup | O(log n) | O(1) average |
| Order | sorted by key | unspecified |
= compares | contents | references |
| Use for | domain logic, shared state, default choice | hot loops, local caches, .NET interop |
Common beginner mistakes
- Throwing away the new map.
Map.add "k" 1 countson its own line does nothing useful (F# warns that the result is ignored). Bind it:let counts2 = .... Map.find/m.[key]on a key that might be missing. It throwsKeyNotFoundException. PreferMap.tryFind.- Expecting insertion order.
MapandSetiterate in sorted key order. Map.addwhen you meant "update". It overwrites. UseMap.changeto build on the old value.- Silent duplicates in
Map.ofList. The last duplicate key wins without any error. - Scanning lists in a loop. Build a map or set once instead of calling
List.tryFind/List.containsfor every item. - Comparing Dictionaries with
=. That compares references. Convert to aMap(or compare counts and entries) to compare contents. - Mutating a
Dictionarywhile iterating over it. Adding keys during aforloop over it throwsInvalidOperationException(removing has been allowed since .NET Core 3.0). Collect the changes and apply them after the loop.
Cheat sheet
Map.ofList [ k1, v1; k2, v2 ] Map.empty
Map.add k v m Map.remove k m Map.tryFind k m Map.containsKey k m
Map.change k (fun old -> newOption) m Map.fold (fun acc k v -> ...) init m
Map.toList m Map.keys m Map.count m Map.filter (fun k v -> ...) m
set [ ... ] Set.add Set.contains Set.union Set.intersect Set.difference Set.unionMany
List.groupBy f xs / List.countBy f xs |> Map.ofList
HashSet<'T>() .Add(x) returns bool Dictionary<'K, 'V>() d.[k] <- v d.TryGetValue k
Practise this lesson
In the app: a short video, 6 exercises checked by real tests and a 12-question concept check. Free with a GitHub account. Running the exercises against their tests needs Pro.
Open in the app