jonnifyfsharp

Module C4.02

Trees & traversals

Give a cons cell a second tail and it becomes a tree. The linear walk becomes a descent.

A list gives a node one tail; a tree gives it two. In F# a binary tree is a discriminated union — Leaf or Node of a left subtree, a value, and a right subtree — and because the type has exactly two cases, the compiler forces both clauses on every recursive function. The linear walk of C4.01 becomes a traversal, depth-first or breadth-first, and when the tree stays balanced the O(n) walk collapses to an O(log n) descent. That collapse is the reason trees exist and the road into the trie family later in this chapter. This module mirrors the Elixir course's E4.02, re-derived in F#, and ties each dive to the real echo_fs EchoMQ schedule — itself an F# Map, a self-balancing search tree.

The three dives Back to C4 · Algorithms

A tree is a branching list

The single pointer of a cons cell splits in two. Where Elixir models a node as a tuple {value, left, right} or nil, F# models it as a union with a Leaf case and a Node case. The shape is the same idea; the difference is that the F# type names the empty tree, so the compiler will not let a recursive function forget it.

The running example across all three dives is a seven-node binary search tree: 12 at the root, 8 and 30 below it, and 5 · 10 · 20 · 42 as leaves. The first dive builds the type and folds it; the second walks it depth-first and breadth-first; the third asks what keeps the descent at O(log n) — and shows F#'s own Map and Set doing it.

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>

The three dives · select one

C4.02.1 binary trees C4.02.2 traversals C4.02.3 balancing the type the walk the descent
C4.02.1 · Binary trees

The discriminated union, recursive size / height / sum with the leaf-and-node clauses the compiler forces, and a BST insert that rebuilds only the path and shares the rest.

You learn the type and the recursive shape it dictates

Open this dive · or pick another above

The shape is recursive, so the functions are too: every tree operation folds a node from its two subtrees, bottoming out at Leaf. The order in which it combines them is what makes a traversal pre-, in-, post-, or level-order.

One tree, three angles

Select an angle. The diagram marks the tree; the readout names the F# behind it and its actual result, every value produced by dotnet fsi over the seven-node tree above. The shape is the recursive type; the depth-first order is in-order; the breadth-first order is level-order.

The angle · select one

12 8 30 5 10 20 42 left subtree < node < right subtree
shape · a Node is a value with a left and a right subtree, or Leaf. This is a binary search tree: everything left of a node is smaller, everything right is larger.

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

result: 7 nodes · height 3 · a root over two subtrees

The same seven nodes read three ways. In-order on a search tree comes out sorted; level-order reads the root, then its children, then theirs. Each is the recursion combined in a different order.

The module's EchoMQ tie

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.

Each dive carries an EchoMQ in F# block. The bus this course grounds in is echo_fs, the F# port of echo/apps/echo_mq at the repo root. Its in-memory core is built and tested; the Valkey transport (EchoMQ.Connector) is the part that is coming soon. The module's primary surface is the retry schedule — an F# Map, which is a self-balancing binary search tree internally.

EchoMQ in F#

A failed job is parked in EchoMQ.Store.Schedule, a Map<string, int64> from a job's branded id to its due-at time in milliseconds. Because a Map is an ordered, balanced search tree, the schedule is exactly this module's structure: keyed lookups in O(log n), an in-order scan to find due jobs, and 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>
      // ... Active, Dead, Paused, Completed, Failed }

Today: the schedule is an in-memory Map, fully tested. Coming soon: the Valkey transport (EchoMQ.Connector) moves the same ordered structure onto the wire behind the same surface.

The three dives

Read them in order. Each stands on valid F# — every // -> result below was produced by dotnet fsi — and each cross-links the matching Elixir E4.02 sibling and carries an EchoMQ block grounded in the real echo_fs store.

live module hub built dive ready soon specified
C4.02.1built

Binary trees

The DU, recursive size / height / sum, and a BST insert that shares the untouched subtrees.

  • the typethe recursive shape and structural sharing
C4.02.2built

Traversals — DFS & BFS

Pre-, in-, post-order depth-first; level-order breadth-first with a queue. In-order on a BST is sorted.

  • the walkthe four orders, and the bus's in-order due-scan
C4.02.3built

Balancing & immutability

Why balance keeps height at O(log n), how a degenerate tree decays into a list, and how F#'s Map / Set self-balance.

  • the descentbalance, decay, and the built-in balanced map

References

Sources

Related in this course