Skip to content
LumenaryAcademy
Practice 55 min

Arrays, hash maps and the standard library

Fast data structures in a pure language. Arrays updated in place thanks to reference counting, strings, hash maps, hash sets and tree maps from Std, and how to choose between them.

Code tested · 3AI-draftedAwaiting review by a computer scientist
MotivationH

Lists are not enough

The List type of lesson 3 is a linked list: each element sits in its own cell with a pointer to the rest. That makes lists ideal for recursion and for proofs (a list is either empty or a head and a tail, and every function can follow that shape), and adding to the front is instant. But reaching the millionth element means following a million pointers, and every cell is a separate allocation scattered through memory, which modern processors handle badly.

Real programs need contiguous arrays with constant-time indexing, and dictionaries that find a key without scanning. Here a pure language seems to face a dilemma. If values never change, then "setting element 5 of an array" must produce a new array, and copying a million elements to change one would make arrays useless.

Lean's way out is one of its most distinctive engineering ideas. Every value on the heap carries a reference count: how many places currently point to it. When you update an array that nothing else refers to (its count is 1), no one could ever observe the old version, so Lean simply changes it in place. Only when the array is genuinely shared does Lean copy it. The program keeps its pure meaning, which proofs rely on, and runs with the speed of mutation. Leonardo de Moura and Sebastian Ullrich described the technique in a 2019 paper with the memorable title Counting Immutable Beans, and it is why this lesson can run a sieve over a million booleans in a pure function.

DefinitionsH

Arrays

Definition— Array

Array α is a contiguous, growable sequence of values of type α, written #[1, 2, 3]. Reading a[i] takes constant time, and so does a.push x (on average; the array occasionally grows its storage). Updates such as a.set! i x or a.modify i f take constant time when a is not shared, and copy the array when it is.

lean
/-- All primes below `n`, by the sieve of Eratosthenes. -/
def primesBelow (n : Nat) : Array Nat := Id.run do
  let mut isPrime := Array.replicate n true
  let mut primes := #[]
  for p in [2:n] do
    if isPrime[p]! then
      primes := primes.push p
      let mut multiple := p * p
      while multiple < n do
        isPrime := isPrime.set! multiple false
        multiple := multiple + p
  return primes

def main : IO Unit := do
  let small := #[5, 3, 8, 1]
  IO.println s!"{small}, size {small.size}, first {small[0]!}, at 9: {small[9]?}"
  IO.println s!"pushed: {small.push 13}, sorted: {small.qsort (· < ·)}"
  IO.println s!"mapped: {small.map (· * 2)}, kept: {small.filter (· > 2)}"
  IO.println s!"sum: {small.foldl (· + ·) 0}, as a list: {small.toList}"
  let primes := primesBelow 1000000
  IO.println s!"{primes.size} primes below one million; the last is {primes.back!}"
  IO.println s!"the first ten: {primes.extract 0 10}"
text
#[5, 3, 8, 1], size 4, first 5, at 9: none
pushed: #[5, 3, 8, 1, 13], sorted: #[1, 3, 5, 8]
mapped: #[10, 6, 16, 2], kept: #[5, 3, 8]
sum: 17, as a list: [5, 3, 8, 1]
78498 primes below one million; the last is 999983
the first ten: #[2, 3, 5, 7, 11, 13, 17, 19, 23, 29]

The first four lines show the everyday operations, all of which return new arrays and leave small as it was: push adds at the end, qsort sorts with a comparison, map, filter and foldl work as on lists, and extract i j takes the elements from index i up to, not including, j. The indexing forms are the ones from lesson 5: a[i]! panics if i is out of range (it prints an error, returns a default value such as 0, and lets the program continue, which is rarely what you want in production), a[i]? returns an Option, and a[i] with a proof is checked at compile time.

The sieve is the interesting part. isPrime holds a million booleans, and the inner loop sets entries to false more than two million times. Each isPrime.set! multiple false means "a new array, equal to the old one except at multiple". But the old array is referenced only by the variable we are about to rebind, so its count is 1, and Lean overwrites the entry in place. If every set! copied the array, the program would copy a million booleans more than two million times, moving trillions of values; instead each update touches one entry, and the whole program runs in a few seconds even in lean --run's interpreter.

How to lose the speed

In-place update depends on the array being unshared at the moment of the update. Two patterns break that:

lean
let backup := isPrime              -- now two references to the same array
isPrime := isPrime.set! 4 false    -- must copy: `backup` still needs the old contents

and, less obviously, holding onto an array inside a structure or closure while updating it elsewhere. The cost is not wrong answers (purity guarantees that backup really does keep the old contents) but a silent copy, which inside a loop turns linear code quadratic. When performance matters, keep one reference to a large array, update it with let mut or by passing it along, and do not stash copies. For hunting down an unexpected copy, Lean provides a debugging function, dbgTraceIfShared, that prints a message whenever the value passed to it is shared.

Two further structures are worth knowing: ByteArray and FloatArray store raw bytes and floats without the per-element boxing that a general Array needs, and Subarray (written a[i:j]) is a view of part of an array without copying it.

Worked examplesH

Strings, hash maps, hash sets and tree maps

Strings

A String is UTF-8 text, and Char is a Unicode character. The operations you will use most have appeared already: ++, interpolation with s!, length (in characters), splitOn, toList, toNat?, toInt?, isEmpty, push, intercalate, and foldl over the characters. Lean's string library was substantially redesigned in 2025 around byte positions and slices, views of part of a string that avoid copying; if you read older Lean code, you will meet functions that are now deprecated or renamed: String.get is deprecated, with a warning that names its replacement, and String.trim has become String.trimAscii, which returns a slice (call .toString on it for a String). The API reference for the version you use is the authority.

Std: hash maps, hash sets and tree maps

The core library, which every Lean file can use without imports, contains Nat, List, Array, String, Option and the other basic types. Std ships with Lean too and adds data structures and system facilities: hash maps and sets, tree maps and sets, iterators, a date and time library, asynchronous input and output, and more. Its modules must be imported by name, at the very top of the file:

lean
import Std.Data.HashMap
import Std.Data.HashSet
import Std.Data.TreeMap
open Std

def text : String :=
  "the sun rose over the hills and the river ran down from the hills to the sea " ++
  "and the sea took the river in"

/-- How many times each word occurs. -/
def frequencies (words : List String) : HashMap String Nat :=
  words.foldl (fun counts w => counts.alter w fun
    | none => some 1
    | some n => some (n + 1)) {}

def main : IO Unit := do
  let words := (text.splitOn " ").filter (· ≠ "")
  let counts := frequencies words
  IO.println s!"{words.length} words, {counts.size} different"
  IO.println s!"'the': {counts.getD "the" 0}, 'moon': {counts.getD "moon" 0}"
  IO.println s!"'river' present: {counts.contains "river"}, lookup 'sea': {counts.get? "sea"}"
  -- Most frequent first; ties in alphabetical order.
  let ranked := counts.toArray.qsort fun (w₁, n₁) (w₂, n₂) => n₁ > n₂ || (n₁ == n₂ && w₁ < w₂)
  IO.println s!"top three: {ranked.extract 0 3}"
  -- A tree map keeps its keys sorted.
  let sorted : TreeMap String Nat := counts.fold (fun m k v => m.insert k v) {}
  IO.println s!"first keys alphabetically: {sorted.keys.take 4}"
  let seen : HashSet Char := text.foldl (fun s c => if c.isAlpha then s.insert c else s) {}
  IO.println s!"{seen.size} different letters"
text
24 words, 14 different
'the': 7, 'moon': 0
'river' present: true, lookup 'sea': (some 2)
top three: #[(the, 7), (and, 2), (hills, 2)]
first keys alphabetically: [and, down, from, hills]
17 different letters

open Std lets us write HashMap instead of Std.HashMap. {} is the empty map or set. The operations are the familiar ones: insert, get? (an Option), getD (with a default), contains, erase, size, fold, toList and toArray. alter updates the entry for a key with a function from the old Option value to the new one, which handles "first time" and "seen before" in one step. Like arrays, hash maps are pure values updated in place when unshared, so the foldl builds the table without copying it.

A HashMap needs its keys to have BEq and Hashable instances; for your own key types, deriving BEq, Hashable provides both. Iteration order is unspecified, so never rely on it: here we sorted explicitly before printing a ranking. A TreeMap, a balanced binary search tree, needs an Ord instance instead, keeps its keys in order, and does each operation in logarithmic rather than (expected) constant time; use it when you need sorted output or range queries. HashSet and TreeSet are the corresponding sets.

These containers come with large libraries of proved lemmas about their operations (for instance, that looking up a key you have just inserted returns the value you inserted), which is what makes it practical to verify programs that use them.

ComputationC

A complete program: shortest path through a maze

Here is a program that puts the lesson together: arrays for the grid, a hash map for distances, loops in Id.run, and an early exit from main when the input is malformed. It finds the length of the shortest path through a maze by breadth-first search: explore every square one step from the start, then every square two steps away, and so on, so that the first time a square is reached is by a shortest route.

lean
import Std.Data.HashMap
open Std

/-- A maze: '#' is a wall, 'S' the start, 'E' the exit. -/
def maze : Array String := #[
  "##########",
  "#S   #   #",
  "# ## # # #",
  "#  #   # #",
  "## ##### #",
  "#      # #",
  "# #### #E#",
  "##########"]

abbrev Pos := Nat × Nat   -- (row, column)

def cell (grid : Array (Array Char)) (p : Pos) : Char :=
  (grid[p.1]?.bind (·[p.2]?)).getD '#'

def find (grid : Array (Array Char)) (c : Char) : Option Pos := Id.run do
  for r in [0:grid.size] do
    for col in [0:grid[r]!.size] do
      if grid[r]![col]! == c then return some (r, col)
  return none

def neighbours (p : Pos) : List Pos :=
  [(p.1 + 1, p.2), (p.1, p.2 + 1)] ++
  (if p.1 > 0 then [(p.1 - 1, p.2)] else []) ++
  (if p.2 > 0 then [(p.1, p.2 - 1)] else [])

/-- Breadth-first search: the distance from `start` to every reachable square. -/
def distances (grid : Array (Array Char)) (start : Pos) (limit : Nat) : HashMap Pos Nat := Id.run do
  let mut dist : HashMap Pos Nat := {}
  dist := dist.insert start 0
  let mut frontier := #[start]
  -- Each round moves one step further; `limit` bounds the number of rounds.
  for _ in [0:limit] do
    let mut next := #[]
    for p in frontier do
      for q in neighbours p do
        if cell grid q != '#' && !dist.contains q then
          dist := dist.insert q (dist.getD p 0 + 1)
          next := next.push q
    if next.isEmpty then break
    frontier := next
  return dist

def main : IO Unit := do
  let grid := maze.map (·.toList.toArray)
  let some start := find grid 'S' | IO.println "no start"
  let some exit := find grid 'E' | IO.println "no exit"
  let dist := distances grid start (grid.size * grid[0]!.size)
  match dist.get? exit with
  | some d => IO.println s!"The exit at {exit} is {d} steps from the start at {start}."
  | none => IO.println "The exit cannot be reached."
  IO.println s!"{dist.size} open squares are reachable."
text
The exit at (6, 8) is 16 steps from the start at (1, 1).
29 open squares are reachable.

Some details worth studying:

  • Pos is an abbrev for a pair, so it automatically has the BEq and Hashable instances of pairs of numbers and can be a hash-map key.
  • cell treats anything outside the grid as a wall, using Option.bind to chain the two lookups that might fail. Combined with the if p.1 > 0 checks in neighbours, which avoid the truncated 0 - 1 = 0 of Nat, the search can never step off the board.
  • distances processes the maze in rounds, one per step of distance, keeping the squares reached in the last round as the frontier. The for _ in [0:limit] loop with a break is deliberate: a loop over a range always ends, so distances is an ordinary total function. The number of squares is a safe limit, since a shortest path never visits a square twice. A while loop would also work, but while is implemented with partial (lesson 4), which would put the function beyond the reach of proofs.
  • let some start := find grid 'S' | IO.println "no start" handles the failure case first and returns from main, so the rest of the function can use start directly.
ExplanationH

Choosing data structures in Lean

NeedUseCost
recursion, pattern matching, proofsListprepend O(1); index and append O(n)
indexed access, large collectionsArrayindex, push, unshared update O(1)
key lookup, no order neededStd.HashMap, Std.HashSetO(1) expected
keys in order, ranges, min and maxStd.TreeMap, Std.TreeSetO(log n)
a fixed length checked by typesVectoras Array
bytes and floats in bulkByteArray, FloatArrayas Array, unboxed

Experienced Lean programmers write the specification and the proofs about a function in terms of lists, and the fast implementation in terms of arrays, and then connect the two with a lemma; the standard library itself works this way. For ordinary programs without proofs, use Array by default and List when you are building results by consing to the front or matching on head and tail.

Measure compiled code. lean --run and #eval interpret your program, which is convenient but much slower than the native executable that lake build produces; never judge performance from them. Inside a program, timeit "label" action runs an IO action and prints how long it took, and IO.monoMsNow reads a millisecond clock for your own measurements. As in any language, find the slow part before rewriting anything: in Lean it is very often an accidental copy of a shared array, a List used where an Array was needed, or a non-tail-recursive function over long input.

Two community resources help you find your way around a library this large. The API reference at lean-lang.org/doc/api documents every function in core and Std. Loogle searches by type: ask for Array ?a → List ?a and it lists the functions with that shape. And there is Batteries, a community library of extra data structures and lemmas that many projects depend on (lesson 10 shows how to add dependencies).

Common misconceptionsH

Common misconceptions

Misconception

"Immutable arrays must be slow." Not in Lean. An unshared array is updated in place, so pure array code runs like imperative code. The real risk is the opposite: an innocent extra reference that forces a copy on every update.

Misconception

"a[i]! is the normal way to index." It is the convenient way, and fine where an index has just been checked. But it hides failures: an out-of-range a[i]! prints an error and continues with a default value. In code that matters, prefer a[i]?, or a proof that the index is valid.

Misconception

"A hash map remembers insertion order." It does not, and its iteration order may change between versions of the library. Sort explicitly, or use a TreeMap, when order matters.

Misconception

"Std is a third-party package." Std is distributed with Lean itself and needs no dependency in your project, only an import. Batteries and Mathlib are separate packages that Lake downloads.

Exercises

Exercises

Use the definitions from the lesson; remember the imports when you try the hash-map examples yourself.

1. Arrays, hash maps and the standard library

Warm-upComputational

With primesBelow from the lesson, what is (primesBelow 100).size?

2. Arrays, hash maps and the standard library

Warm-upComputational

What does #eval #[5, 3, 8, 1].qsort (· > ·) show?

3. Arrays, hash maps and the standard library

CoreComputational

What is #[1, 2, 3, 4].foldl (fun acc x => acc * 10 + x) 0?

4. Arrays, hash maps and the standard library

CoreHuman

Inside a loop, you write let old := arr and then arr := arr.set! i v, keeping old alive until after the loop. What happens at each set!?

Choose one

5. Arrays, hash maps and the standard library

Warm-upComputational

In the word-frequency program, what would counts.get? "moon" evaluate to? ("moon" does not occur in the text.)

6. Arrays, hash maps and the standard library

CoreHuman

You need a map from student names to marks, and you must print it in alphabetical order of name. Which structure fits best?

Choose one

7. Arrays, hash maps and the standard library

StretchHuman

You define structure Coord where x : Int; y : Int and want to use it as a key. Which instances must Coord have? List the letters.

  • A: BEq (for a HashMap key)
  • B: Hashable (for a HashMap key)
  • C: Ord (for a TreeMap key)
  • D: ToString (for any map key)
  • E: Inhabited (for any map key)

Write elements separated by commas. Order and repeats don’t matter — just like in a set!

Further reading and resources

  • Counting Immutable Beans: Reference Counting Optimized for Purely Functional Programming · Sebastian Ullrich and Leonardo de Moura · 2019The paper describing how Lean reuses memory that is no longer shared, which makes pure arrays fast (IFL 2019).
  • Lean API referenceGenerated documentation for every function in the core library and Std, searchable by name.
  • LoogleSearch Lean libraries by name, by type or by pattern, for example every function from Array α to List α.
  • Hash tables (Lumenary CS)How hash tables work inside, independent of any language.