Skip to content
Tutorials Center
My learning

Topics

Lesson 18 of 37 ยท Collections and Sequences

F# Maps and Sets: Immutable Dictionaries, Set Operations and Dictionary

Use F# Map for immutable key-value lookups and Set for unique values: creation, add, remove, tryFind, set union, intersection and difference, plus when to pick Dictionary or HashSet instead.

Lists and arrays hold items by position. Often you want to find things by key, or keep only distinct values. F# provides two immutable collections for this: Map<'Key, 'Value>, an ordered dictionary, and Set<'T>, an ordered collection of unique items. This lesson covers both, with the Map and Set modules, and compares them with the mutable .NET Dictionary and HashSet you may reach for in performance-sensitive code.

Maps

A map associates keys with values. Create one from a list of pairs:

FSHARP
let capitals =
    Map [ ("France", "Paris")
          ("Japan", "Tokyo")
          ("Brazil", "Brasilia") ]

let empty: Map<string, int> = Map.empty
let fromList = [ (1, "one"); (2, "two") ] |> Map.ofList

Like everything in F#'s core collections, a map is immutable. "Adding" returns a new map and leaves the old one untouched (the two share most of their internal tree, so it is efficient):

FSHARP
let withSpain = capitals |> Map.add "Spain" "Madrid"
printfn "%d %d" capitals.Count withSpain.Count      // 3 4

Looking things up

FSHARP
capitals["Japan"]                       // "Tokyo"   (throws KeyNotFoundException if missing)
capitals |> Map.tryFind "Italy"         // None
capitals |> Map.tryFind "France"        // Some "Paris"
capitals |> Map.containsKey "Brazil"    // true
capitals.TryGetValue "Japan"            // (true, "Tokyo")
capitals |> Map.find "Japan"            // "Tokyo"

Use Map.tryFind when a key may be missing: it returns an option, which forces you to handle the absent case:

FSHARP
match capitals |> Map.tryFind "Italy" with
| Some city -> printfn "Capital: %s" city
| None -> printfn "Unknown country"

Changing and combining

FSHARP
capitals |> Map.remove "Japan"                       // new map without Japan
capitals |> Map.add "Japan" "Kyoto"                  // add replaces an existing key
capitals |> Map.change "France" (Option.map (fun city -> city + "!"))   // "Paris!"

Map.add on an existing key replaces the value. Map.change takes a function from option to option for a key, which is the tidy way to implement "update or insert".

A frequent task is counting occurrences:

FSHARP
let countWords (words: string list) =
    words
    |> List.fold
        (fun counts w ->
            let current = counts |> Map.tryFind w |> Option.defaultValue 0
            counts |> Map.add w (current + 1))
        Map.empty

countWords [ "a"; "b"; "a"; "c"; "a" ]
// map [("a", 3); ("b", 1); ("c", 1)]

Shorter: words |> List.countBy id |> Map.ofList.

Iterating

A map behaves as a sequence of KeyValuePairs ordered by key. The Map module offers map, filter, fold, iter, exists, forall, partition, toList, toSeq, keys and values:

FSHARP
capitals |> Map.iter (fun country city -> printfn "%s -> %s" country city)

capitals
|> Map.filter (fun _ city -> city.StartsWith "T")
|> Map.toList
// [("Japan", "Tokyo")]

capitals |> Map.map (fun _ city -> city.ToUpper())

Iteration order is sorted by key, regardless of insertion order. Keys must support comparison (strings, numbers, tuples of those, records of those...).

flowchart LR
    A["list of (key, value) pairs"] -->|Map.ofList| B["Map"]
    B -->|Map.tryFind key| C["Some value or None"]
    B -->|Map.add key value| D["new Map"]

Operations on a map produce new maps or options, never in-place changes.

Sets

A set stores each value once, in sorted order:

FSHARP
let colors = Set [ "red"; "green"; "blue"; "red" ]     // set ["blue"; "green"; "red"]
let primes = set [ 2; 3; 5; 7 ]                          // `set` is a convenience function
let empty: Set<int> = Set.empty

Basic operations:

FSHARP
let more = colors |> Set.add "yellow"
let less = colors |> Set.remove "red"
colors |> Set.contains "red"        // true
Set.count colors                    // 3
colors |> Set.map String.length     // set [3; 4; 5]  (duplicates disappear)
colors |> Set.filter (fun c -> c.Length > 3)

Adding an element that is already present returns the same set, no error.

Set algebra

Sets shine at mathematical set operations:

FSHARP
let a = set [ 1; 2; 3; 4 ]
let b = set [ 3; 4; 5 ]

Set.union a b             // set [1; 2; 3; 4; 5]
Set.intersect a b         // set [3; 4]
Set.difference a b        // set [1; 2]
a - b                     // same as difference
Set.isSubset (set [ 3 ]) a      // true

A neat use is removing duplicates and checking membership quickly (logarithmic time):

FSHARP
let uniqueSorted = [ 5; 3; 5; 1; 3 ] |> Set.ofList |> Set.toList    // [1; 3; 5]

Dictionary and HashSet: the mutable alternatives

The .NET collections are mutable hash tables with O(1) average lookup, and they do not require ordering:

FSHARP
open System.Collections.Generic

let counts = Dictionary<string, int>()
counts["a"] <- 1
counts["a"] <- counts["a"] + 1
printfn "%d" (counts["a"])     // 2

let seen = HashSet<int>()
printfn "%b" (seen.Add 5)      // true (it was new)
printfn "%b" (seen.Add 5)      // false (already there)

F# also has dict [ ("a", 1) ], which builds a read-only dictionary from pairs.

Map / Set Dictionary / HashSet
Mutability immutable mutable
Lookup O(log n) O(1) average
Order sorted by key not ordered
Key requirement comparison equality and hash
Best for functional code, snapshots, safe sharing big, hot loops; interop

Start with Map and Set. Switch to Dictionary when profiling shows a hot spot, and keep it inside one function so the mutation does not leak out.

C# stand-ins

C# Dictionary and HashSet are the mutable relatives; SortedDictionary is closest to F#'s Map. These stand-ins show counting words and the set algebra.

C# C# stand-in: counting words

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with Console.ReadLine()), it gets the next line from this box.

C# C# stand-in: set algebra

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with Console.ReadLine()), it gets the next line from this box.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. What does Map.add "k" 2 m do if "k" already exists in m?

    Add replaces an existing key and returns a new map; the original map is unchanged.
  2. 2. Which function looks up a key safely?

    tryFind returns an option, so a missing key gives None instead of an exception.
  3. 3. What is set [1; 2; 2; 3]?

    Sets keep each value only once.
  4. 4. When might you prefer Dictionary over Map?

    Dictionary has O(1) average lookups and is mutable; Map is immutable and ordered with O(log n) lookups.

Summary

  • Map<'K,'V> is an immutable, key-sorted dictionary; Map.add, remove and change return new maps; use Map.tryFind for safe lookup.
  • Set<'T> stores unique sorted values and supports union, intersect and difference.
  • Build them from lists with Map.ofList and Set.ofList; counting is List.countBy.
  • Dictionary and HashSet are the mutable, hash-based .NET alternatives for hot paths and interop.

Next: Comprehensions and collection functions