Dive C4.02.1

Binary trees

One type, two cases, and every recursive function falls out of the shape.

A binary tree is a node — a value with a left and a right subtree — or the empty tree. In F# that is a single discriminated union with a Leaf case and a Node case. The Elixir course models the same node as a tuple {value, left, right} or nil; the F# difference is that the type names the empty tree, so the compiler refuses a recursive function that forgets it. Because the type has exactly two cases, every operation has exactly two clauses: a value for Leaf and a fold of the node from its two subtrees. This dive builds the type, folds it three ways, and shows the one move that makes immutable trees cheap to update — sharing every subtree it does not touch.

Fold the tree Module hub

C4.02.1 · part 1

The type — Leaf or Node

One line defines the whole structure. A Tree<'T> is either Leaf — the empty tree — or a Node carrying a left subtree, a value, and a right subtree. The type is generic and recursive: the two Tree<'T> fields of Node are themselves trees.

Elixir — a node is a tuple or nil

# Elixir — {value, left, right} or nil
tree = {12,
  {8, {5, nil, nil}, {10, nil, nil}},
  {30, {20, nil, nil}, {42, nil, nil}}}

F# — a discriminated union (verified in FSI)

type Tree<'T> =
    | Leaf
    | Node of Tree<'T> * 'T * Tree<'T>

let tree =
    Node(
        Node(Node(Leaf, 5, Leaf), 8, Node(Leaf, 10, Leaf)),
        12,
        Node(Node(Leaf, 20, Leaf), 30, Node(Leaf, 42, Leaf)))
// val tree : Tree<int>

Tree<'T>: a generic union: the structure holds values of any one type 'T the tree is instantiated at.
Leaf: the empty tree — a named case, not nil. It is the base of every recursion.
Node of …: a triple of a left subtree, a value, and a right subtree. The two subtree fields are recursive.
this tree: a binary search tree: everything left of a node is smaller, everything right is larger.

Fold the tree three ways

Each function has a clause for Leaf and a clause for a Node. The node clause makes two recursive calls — one per subtree — and combines them. Select one to read its clauses and the result dotnet fsi produces over the seven-node tree.

The function · select one

let rec size t =
    match t with
    | Leaf -> 0
    | Node(l, _, r) -> 1 + size l + size r
// size tree -> 7

size · adds one for the node plus the sizes of both subtrees, bottoming out at 0 for Leaf. Over this tree, 7.

base: size Leaf = 0 · result: 7

There are always exactly two clauses to get right: what an empty tree is worth, and how to fold a node from its two subtrees. Miss neither and the function is total — the recursion cannot run off the end, and the compiler will say so.

C4.02.1 · part 2

Insert rebuilds the path and shares the rest

Trees are immutable, so insert returns a new tree — but it does not copy the old one. A binary search tree keeps smaller values left and larger right, so insert descends one side per level, rebuilding only the nodes on the path from the root to the new leaf and sharing every untouched subtree by reference. Inserting 15 walks 12 → 30 → 20 and hangs it on 20's empty left: three nodes rebuilt, one new leaf, the entire left half shared unchanged.

let rec insert x t =
    match t with
    | Leaf -> Node(Leaf, x, Leaf)
    | Node(l, v, r) when x < v -> Node(insert x l, v, r)
    | Node(l, v, r) when x > v -> Node(l, v, insert x r)
    | _ -> t   // already present

let tree2 = insert 15 tree
// size tree2 -> 8

insert 15 tree · rebuilt path vs shared subtrees

Three nodes rebuilt on the path, one new leaf, four subtrees shared by reference. For a balanced tree that is O(log n) new nodes per insert — the foundation of persistent data structures, and exactly how the tries later in this chapter stay cheap to update.

The sharing is literal, not a figure of speech. Take the left subtree of each version and compare them with reference equality: System.Object.ReferenceEquals(left tree, left tree2) returns true — the same object, untouched.

The idea

Solve a node by combining the answers from its two subtrees — and on insert, copy only the path you change.

In F#

f (Node(l, v, r)) = combine v (f l) (f r), with Leaf as the base; insert shares the rest by reference.

C4.02.1 · the bus

EchoMQ in F# — the schedule is a Map

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 in F#

The F# EchoMQ — the port at echo_fs — keeps its retry schedule in EchoMQ.Store.Schedule, an F# Map<string, int64> from a job's branded id to its due-at time in milliseconds. An F# Map is a self-balancing binary search tree internally, so the schedule is exactly this dive's structure: keyed lookups in O(log n), and the same structural sharing on every update.

// echo_fs/EchoMQ/Store.fs
type QueueState =
    { Rows: Map<string, Job>
      Pending: Set<string>
      /// id -> due-at (ms): jobs parked until their run-at time.
      Schedule: Map<string, int64>
      /// id -> lease deadline (ms): jobs claimed and in flight.
      Active: Map<string, int64>
      Dead: Set<string>
      Paused: bool
      Completed: int
      Failed: int }

When a job fails and is parked for a later attempt, Store.retry performs a single insert into that balanced tree — st.Schedule.Add(id, now + delayMs). The rest of the schedule is shared, untouched, the way insert shares subtrees above.

// echo_fs/EchoMQ/Store.fs — inside retry, the park branch
{ st with
    Rows = st.Rows.Add(id, row)
    Active = active
    Schedule = st.Schedule.Add(id, now + delayMs) }

Today: the schedule is an in-memory Map, built and tested. Coming soon: the Valkey transport — EchoMQ.Connector, which currently raises "EchoMQ Valkey connector: coming soon" — swaps the Map for the durable store behind the same surface, with no caller change.

Where this leads

The type dictates the recursion, and immutability makes update cheap by sharing. The next dive keeps the same tree and walks it — depth-first in three orders, then breadth-first with a queue — and shows that in-order on a search tree comes out sorted, the property the bus's due-scan rides.

↑ C4.02 · Trees & traversals C4.02.2 · Traversals → C4.02.3 · Balancing

References

Sources

Microsoft — F# documentation — discriminated unions, generics, and recursive functions.
FSharp.Core API reference — the Map module the EchoMQ schedule uses.
The F# Software Foundation — F# on the .NET runtime.

Related in this course

Elixir — F4.02.1 Binary trees & recursive shape — the E4 sibling, in tuples.
C1.06 — Discriminated unions & records — the type this dive builds on.
C4.02 — Trees & traversals — the module hub.
C4.02.2 — Traversals — the next dive.