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.

6 min read

In short

  • Map and Set are immutable: changes return new collections
  • Map.tryFind returns an option; Map.change updates from the old value
  • Sets give union, intersect, difference and subset checks
  • groupBy and countBy with Map.ofList build indexes
  • Use Dictionary and HashSet for 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.

▶ Try
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
▶ Try
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.ofList builds a map from a list of (key, value) tuples. "apple", 0.5 is a tuple; the parentheses are optional inside a list.
  • Map.add key value map returns a new map. If the key exists, its value is replaced.
  • Map.tryFind returns an option instead of undefined, 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.emptynew Map()
Map.add k v mm.set(k, v) (but returns a new map)
Map.remove k mm.delete(k)
Map.tryFind k mm.get(k)
Map.containsKey k mm.has(k)
Map.find k m or m.[k]m.get(k)! (throws if missing)
Map.count mm.size
Map.toList m[...m.entries()]
Map.filter (fun k v -> ...) mno 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):

▶ Try
counts.set(word, (counts.get(word) ?? 0) + 1);
▶ Try
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:

▶ Try
let countWords (words: string list) : Map<string, int> =
    words |> List.fold (fun counts word -> increment word counts) Map.empty

Set: unique values

▶ Try
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)));
▶ Try
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

▶ Try
// with lodash
const byStatus = _.groupBy(orders, o => o.status);
const counts = _.countBy(orders, o => o.status);
▶ Try
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.groupBy returns a list of (key, itemsWithThatKey) pairs. Items keep their original order within each group.
  • List.countBy returns (key, count) pairs.
  • Seq.groupBy and Seq.countBy do the same for any sequence (an array, a database result, a seq { }).
  • Pipe into Map.ofList / Map.ofSeq to 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):

▶ Try
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.

▶ Try
const seen = new Set<string>();
const unique = ids.filter(id => {
  if (seen.has(id)) return false;
  seen.add(id);
  return true;
});
▶ Try
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
▶ Try
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 / SetDictionary / HashSet
Changesreturn a new collectionmutate in place
LookupO(log n)O(1) average
Ordersorted by keyunspecified
= comparescontentsreferences
Use fordomain logic, shared state, default choicehot loops, local caches, .NET interop

Common beginner mistakes

  • Throwing away the new map. Map.add "k" 1 counts on 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 throws KeyNotFoundException. Prefer Map.tryFind.
  • Expecting insertion order. Map and Set iterate in sorted key order.
  • Map.add when you meant "update". It overwrites. Use Map.change to 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.contains for every item.
  • Comparing Dictionaries with =. That compares references. Convert to a Map (or compare counts and entries) to compare contents.
  • Mutating a Dictionary while iterating over it. Adding keys during a for loop over it throws InvalidOperationException (removing has been allowed since .NET Core 3.0). Collect the changes and apply them after the loop.

Cheat sheet

▶ Try
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