jonnifyfsharp

Dive C4.05.3

Structural sharing

Add a key and keep the old map too. The new version copies one path and shares the rest.

A persistent map returns a new version on every update and leaves the old one intact. It does not copy the whole structure: an update copies only the nodes on the path from the root to the changed entry and shares every other sub-tree — pointer-identical with the previous version. So an update is about O(log n) new nodes, not a full copy, and holding the old version costs nothing. This dive shows that property and verifies it on F#'s own Map in dotnet fsi: Add and Remove never mutate. The honest note carries through: F# gets structural sharing from a balanced search tree, not a HAMT — sharing is the property both give, and the reason either is a good persistent map.

Add a key, keep the old Module hub
C4.05.3 · part 1

Copy the path, share the rest

The mechanism is the same for a HAMT and a balanced tree. To add or change an entry, walk from the root to where it belongs, and build new nodes only along that path. Every sub-tree that hangs off the path is untouched and reused, shared by both versions. The old version still points at its old root, so it is exactly as it was; the new version points at a new root whose new path eventually rejoins the shared sub-trees. The cost is the depth — O(log n) — not the size.

An insert copies the path (gold) and shares the rest (sage)

v1 root v2 root (new) shared subtree v1 node new node shared leaf new leaf unchanged one new path
v2 = v1 with one key added. New nodes (gold): the root, one node, one leaf — the path. Shared (sage): the left subtree and the old leaf, pointer-identical in both. v1 is unchanged.
persistent
an update returns a new version; the old one survives, unchanged.
path copy
new nodes are built only from the root to the changed entry — O(log n) of them.
structural sharing
every sub-tree off the path is reused, pointer-identical, by both versions.
cost
an update is the depth, not the size; holding a prior version is free.
C4.05.3 · part 2

F#'s Map is persistent — verified

The clearest proof is in FSI. Build a map; add a key; check the original. The original is untouched — Add returned a new map and left the old one alone. Remove is the same: it returns a new map without the key, and the version it was called on still has it.

let v1 = Map.ofList [ "JOB02", 1; "JOB05", 2; "JOB07", 3 ]
let v2 = v1.Add("JOB09", 4)

v1.Count                  // val it : int = 3   — unchanged
v2.Count                  // val it : int = 4
v1.ContainsKey "JOB09"    // val it : bool = false  — old map intact
v2.ContainsKey "JOB09"    // val it : bool = true

let v3 = v2.Remove "JOB02"
v2.ContainsKey "JOB02"    // val it : bool = true   — v2 untouched
v3.ContainsKey "JOB02"    // val it : bool = false

The honest note: F# gets this from a balanced search tree, not a HAMT. The property on show — an update keeps the old version standing and shares structure — is what makes any of these structures a good persistent map. A HAMT shares whole 32-way sub-nodes; a balanced tree shares whole sub-trees; both leave the old version intact. F#'s stdlib chose the balanced tree, and echo_fs uses that stdlib Map.

Elixir — Map.put is non-destructive too

# Elixir — put returns a new map; the old one is untouched (Map is a HAMT here)
v1 = %{"JOB02" => 1, "JOB05" => 2, "JOB07" => 3}
v2 = Map.put(v1, "JOB09", 4)
Map.has_key?(v1, "JOB09")   # => false

F# — the same guarantee, from a balanced tree (verified in FSI)

// F# — Add returns a new map; the old one is untouched (Map is a balanced tree here)
let v1 = Map.ofList [ "JOB02", 1; "JOB05", 2; "JOB07", 3 ]
let v2 = v1.Add("JOB09", 4)
v1.ContainsKey "JOB09"   // val it : bool = false

Add a key; watch the old version survive

Apply an operation to a fixed map v1 = { JOB02→1; JOB05→2; JOB07→3 } and read both versions side by side. Add returns a new version with the key; Remove returns one without it; v1 never changes. The readout reports each version's contents and confirms the old one is intact — the values are computed by the same non-destructive map operations the code uses. The table below states the outcome without scripting.

v2 = op(v1) · v1 stays as it was

v1 (unchanged) JOB02 → 1 JOB05 → 2 JOB07 → 3 .Add("JOB09", 4) v2 (new version)
v2 = v1.Add("JOB09", 4) · v2 has 4 keys (JOB09→4 added); v1 still has 3 — the old version is intact.
Without JavaScript: v2 = v1.Add("JOB09", 4)
v1{ JOB02→1; JOB05→2; JOB07→3 } — 3 keys, unchanged
v2{ JOB02→1; JOB05→2; JOB07→3; JOB09→4 } — 4 keys

A new version, and the old one still standing — that is the whole value of a persistent map. The bus uses it to keep a prior state for free; whether the map underneath is a HAMT or a balanced tree, the guarantee is the same.

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.

Every state transition in the F# bus is a non-destructive map write. The admission writes a row with Rows.Add and produces a new state; the state it was given is untouched, so a prior snapshot survives for free. That is the property a registry calls for, and it is the property a HAMT and a balanced tree both provide. The honest framing holds: the map is an F# Map (a balanced tree) today; the Elixir bus backs the registry with the HAMT/CHAMP family; the surface is the same across the swap.

EchoMQ in F#

Each Rows.Add keeps the old state standing

The enqueue transition writes the row into the rows map and returns a new state, leaving the prior st intact. Quoted verbatim from echo_fs/EchoMQ/Store.fs:

/// Idempotent admission: refuse a duplicate id, else write the row and add
/// the id to the pending set. (The Elixir `@enqueue` script, in memory.)
let enqueue (id: string) (payload: string) (st: QueueState) : QueueState * Admission =
    if not (BrandedId.isValid id) then
        invalidArg (nameof id) "enqueue requires a valid branded id"

    if st.Rows.ContainsKey id then
        st, Admission.Duplicate
    else
        let row = Job.create id payload
        { st with
            Rows = st.Rows.Add(id, row)
            Pending = st.Pending.Add id },
        Admission.Enqueued

st.Rows.Add(id, row) returns a new Map; the previous st is never mutated. So the bus can hold an earlier state cheaply (verified in FSI over a fixed state):

let before = st0.Rows.Count          // val before : int = 0
let st1, _ = enqueue "JOB0NcQgyPQEbI" "ping" st0
st0.Rows.Count                        // val it : int = 0   — the prior state is intact
st1.Rows.Count                        // val it : int = 1

The F# EchoMQ writes its registry non-destructively today — EchoMQ.Store.Rows is an immutable F# Map (a balanced tree, not a HAMT), so each Rows.Add keeps the old state standing, in the in-memory core (echo_fs/EchoMQ/Store.fs — built and tested). The HAMT/CHAMP backing the Elixir bus uses, and the Valkey transport EchoMQ.Connector, land next; the non-destructive add surface holds across the swap.

The property

An update copies one path and shares the rest, so the old version survives. A HAMT and a balanced tree both give it.

The next module

C4.06 takes the CHAMP — a compressed HAMT that splits the one array in two for a canonical, cache-friendlier layout.

Where this leads

Structural sharing is the property that makes a persistent map worth having: a new version, the old one kept, for the price of one path. This closes the HAMT module — the trie shape, the bitmap node indexed by hash, and the sharing both a HAMT and a balanced tree provide. The next module, C4.06, takes the CHAMP: a compressed HAMT that splits the single packed array into two and gives the tree a canonical shape, the structure the bus's branded store grows into.

↑ C4.05 · Hash Array Mapped Tries ← C4.05.2 · The HAMT C4 · Algorithms hub →

References

Sources

Related in this course