jonnifyfsharp

Dive C4.05.1

Prefix tries

Store a key by its pieces, and keys that begin the same way share the road in.

Before the hashing, the shape. A trie — a prefix tree — stores keys piece by piece. Each node holds the value (if any) that ends exactly here, plus a map from the next piece to a child node. To find a key, walk it one piece at a time, following the child for each piece, and read the value at the end. Two keys that share a prefix — say "JO" and "JOB" — share every node down to where they diverge. Nothing is hashed yet; the HAMT's move, in the next dive, is to hash the key first and walk slices of that hash instead of raw pieces. This dive builds a small trie in F# and verifies it in dotnet fsi.

Walk a trie Module hub
C4.05.1 · part 1

A node is a value and a map of children

The model is one recursive record. A node carries an optional value — present only at a node where a key ends — and a map from the next character to a child node. The map of children is an F# Map; the recursion is the trie. add walks the key character by character, reusing the child that already exists for each character or starting an empty one, and sets the value at the end; find walks the same path and reads the value there.

type Trie<'v> =
    { Value: 'v option
      Children: Map<char, Trie<'v>> }

module Trie =
    let empty : Trie<'v> = { Value = None; Children = Map.empty }

    let rec add (key: string) (i: int) (v: 'v) (node: Trie<'v>) : Trie<'v> =
        if i = key.Length then { node with Value = Some v }
        else
            let c = key.[i]
            let child = node.Children |> Map.tryFind c |> Option.defaultValue empty
            { node with Children = node.Children.Add(c, add key (i + 1) v child) }

    let rec find (key: string) (i: int) (node: Trie<'v>) : 'v option =
        if i = key.Length then node.Value
        else
            match Map.tryFind key.[i] node.Children with
            | Some child -> find key (i + 1) child
            | None -> None
node
a Value: 'v option (a value only where a key ends) plus Children: Map<char, Trie<'v>>.
add
walks the key, descends or starts a child per character, and sets the value at the final node.
find
walks the same path; returns the node's value, or None if any character has no child.
shared prefix
keys with a common start share the nodes down to the point they differ — the trie's defining property.
C4.05.1 · part 2

Two keys, one shared root

Add "JO" then "JOB". Both descend through the 'J' child at the root and the 'O' child below it; "JO" ends there with its value, and "JOB" carries on to a 'B' child. Looking up a key that was never added returns None the moment a character has no child.

let t0 = Trie.empty
let t1 = Trie.add "JO" 0 1 t0
let t2 = Trie.add "JOB" 0 2 t1

Trie.find "JO"  0 t2   // val it : int option = Some 1
Trie.find "JOB" 0 t2   // val it : int option = Some 2
Trie.find "JX"  0 t2   // val it : int option = None
t2.Children.ContainsKey 'J'   // val it : bool = true  (both keys share it)
The shape carries over from Elixir directly. An Elixir trie is a map with a values slot and a children map; the F# trie is the same data, given a static type. The pattern — a node of a value and a map of children, walked by recursion — is identical on both runtimes.

Elixir — a trie node as a map

# Elixir — a trie node: value + children map
defp add(node, "", v), do: %{node | value: v}
defp add(node, <<c::utf8, rest::binary>>, v) do
  child = Map.get(node.children, c, %{value: nil, children: %{}})
  %{node | children: Map.put(node.children, c, add(child, rest, v))}
end

F# — the same node, statically typed (verified in FSI)

// F# — Value: 'v option ; Children: Map<char, Trie<'v>>
let rec add (key: string) (i: int) (v: 'v) (node: Trie<'v>) =
    if i = key.Length then { node with Value = Some v }
    else
        let c = key.[i]
        let child = node.Children |> Map.tryFind c |> Option.defaultValue Trie.empty
        { node with Children = node.Children.Add(c, add key (i + 1) v child) }

Walk the trie, key by key

Pick a key to look up in a fixed trie holding "JO", "JOB", and "JAR". The path lights up character by character as find descends; the readout shows the character being matched, the child taken, and the value at the end — or where the walk stopped at a missing child. Every step is computed by the same recursive descent the code uses, over the fixed trie.

find key : descend one character per level

root J A O JO = 1 JAR=3 JOB=2
find "JOB" · descend 'J' → 'O' → 'B'; the node at the end holds Some 2.

A trie reads a key by its pieces, and a shared start is a shared path. Switch the key from raw characters to slices of the key's hash, and a node from a child-per-character map to a bitmap-plus-array, and the trie becomes a HAMT — the next dive.

C4.05.1 · part 3

Why keying by digits is the HAMT's seed

A branded id like JOB0NcQgyPQEbI is fourteen characters: a three-letter namespace then an eleven-character Base62 snowflake. Keying a registry by the id's characters makes a trie whose top levels are the namespace (J, O, B), then the snowflake. Ids minted close in time share the high bytes of the timestamp, so they share a long prefix — and therefore most of the path.

That works, but a character trie has an awkward shape: branching depends on the alphabet, and a long key means a deep walk. The HAMT keeps the trie idea and fixes both: it hashes the key first, then reads the hash in fixed 5-bit slices, so every node branches exactly 32 ways and the depth is ~log₃₂ n regardless of key length. The next dive makes that switch.

This dive · a prefix trie

Walk the key's raw pieces; a node is a value plus a child-per-piece map. Shared prefixes share the path.

Next dive · the HAMT

Hash the key, walk 5-bit slices; a node is a bitmap plus a packed array. Branch 32 ways, depth ~log₃₂ n.

EchoMQ in F#

Status — echo_fs is an in-memory model. The EchoMQ protocol — the Lua transitions executing on a Valkey wire — is not implemented (there is no Lua and no Valkey client in the code); that is the coming-soon transport (EchoMQ.Connector). This block shows how the model uses the structure, not a running bus.

EchoMQ keys its job registry by the branded id directly: EchoMQ.Store.Rows is a Map<string, Job> over those ids. The trie view of this dive says: if that map were a prefix trie keyed by the id's digits, ids minted in the same window would share the path through their common prefix. The id itself is built to make that prefix meaningful — its namespace and timestamp lead.

EchoMQ in F#

Keying the registry by the branded id's digits

The registry's key is a branded id, and the id is gated to a strict shape before it is used as a key. Quoted verbatim from echo_fs/EchoMQ/BrandedId.fs:

/// The full-format check: 3 uppercase letters then 11 Base62 chars. A bare
/// `"JOB"` has a valid namespace but is **not** a valid id (the gate the key
/// builder enforces).
let isValid (id: string) : bool =
    not (isNull id)
    && id.Length = 14
    && Seq.forall isUpper (id.Substring(0, 3))
    && Seq.forall isBase62 (id.Substring(3))

Reading those fourteen digits as a trie path: the first three (JOB) are the namespace, the next eleven the Base62 snowflake. Ids from the same mint window share the leading digits, so a trie keyed this way shares their path (the descent below was verified in FSI over a fixed trie):

let reg =
    Trie.empty
    |> Trie.add "JOB0NcQgyPQEbI" 0 "ping"
    |> Trie.add "JOB0NcQh2mK1tW" 0 "scan"

reg.Children.ContainsKey 'J'   // val it : bool = true   (one shared J node)
Trie.find "JOB0NcQgyPQEbI" 0 reg   // val it : string option = Some "ping"

The F# EchoMQ keys its registry by the branded id today — EchoMQ.Store.Rows, a Map<string, Job> in the in-memory core (echo_fs/EchoMQ/Store.fs, BrandedId.fs — built and tested). The map is a balanced tree, not a trie; the trie above is the shape this dive teaches. The HAMT/CHAMP backing the Elixir bus uses is the next dive's subject, and the Valkey transport EchoMQ.Connector lands next.

The shape

A trie stores keys by their pieces; a shared prefix is a shared path. A branded id leads with namespace and timestamp.

The next dive

The HAMT hashes the key and walks 5-bit slices, so a node branches 32 ways and depth stays near-constant.

Where this leads

The trie is the shape. The next dive turns it into a HAMT: a node becomes a bitmap plus one packed array, the key becomes its hash, and the descent reads 5-bit slices of that hash — so a node branches 32 ways and the depth drops to ~log₃₂ n. The third reads how an update shares structure.

↑ C4.05 · Hash Array Mapped Tries C4.05.2 · The HAMT → C4.05.3 · Structural sharing

References

Sources

Related in this course