F4 · chapter overview
Algorithms & data structures
The data behind the systems you built in F3. This chapter starts at the list — the BEAM's fundamental sequence — and works up through trees, sorting, and hash-based maps to the persistent tries that make immutable maps fast: HAMT and CHAMP. From there it turns to the ids that key them — the Snowflake bigint and its branded, base62 form — their persistence across SQLite, PostgreSQL, and Redis, and the branded CHAMP map behind a GenServer. Each structure comes with the cost model that tells you when to reach for it.
Twelve modules, each grounded in working Elixir and the running portal's data. The arc is deliberate: foundations first (lists, trees, sorting, maps), then the persistent-map spine (HAMT → CHAMP → identifiers → persistence → branded CHAMP), then practical recipes, dynamic programming, and a lab where you watch a branded CHAMP map grow node by node.
The chapter arc
Read it in order. The foundations earn the tries: once you can reason about a list's O(n) walk and a map's average-O(1) lookup, the HAMT and CHAMP show how a tree of small nodes gives you both persistence and speed. Modules F4.01 through F4.12 — lists through the branded-CHAMP lab — are all built.
Twelve modules · F4.01 through F4.06 are built
A data structure is a bet about which operations you will do most. This chapter is about reading that bet from the cost model — and choosing the structure that wins it.
Module navigation
F4.01 is built; open it below. The rest list their planned deep dives so the path through the chapter is visible from here.
Lists, recursion & complexity
Cons cells; big-O on the BEAM.
- F4.01.1Cons cells & the shape of a list
- F4.01.2Recursion over lists
- F4.01.3Complexity & big-O on the BEAM
Trees & traversals
Recursive tree shape and the three depth-first orders.
- F4.02.1Binary trees & recursive shape
- F4.02.2Depth-first: pre, in, post-order
- F4.02.3Breadth-first & balance
Sorting & searching
Comparison sorts and the cost of finding things.
- F4.03.1Merge & quicksort
- F4.03.2Linear & binary search
- F4.03.3Stability & sort cost
Maps, sets & hashing
Key lookup, membership, and what a hash buys you.
- F4.04.1Maps & key lookup
- F4.04.2MapSet & membership
- F4.04.3Hashing & collisions
Hash Array Mapped Tries (HAMT)
A tree of small nodes indexed by slices of the hash.
- F4.05.1Bitmapped nodes
- F4.05.2Hash-prefix indexing
- F4.05.3Structural sharing
CHAMP maps
A compressed HAMT: tighter nodes, faster iteration.
- F4.06.1Compressed node layout
- F4.06.2Cache-friendly iteration
- F4.06.3Canonical equality
Identifiers, Snowflake & branded ids
From naive ids to a Snowflake bigint and a branded, base62 id.
- F4.07.1Choosing an identifier
- F4.07.2The Snowflake bigint
- F4.07.3Branded ids
Branded ids & persistence
Branded ids as keys in SQLite, PostgreSQL, and Redis.
- F4.08.1Branded ids as keys
- F4.08.2SQLite & PostgreSQL
- F4.08.3Redis keys
Branded CHAMP maps & GenServer
A CHAMP keyed by branded ids, partitioned by namespace, behind a GenServer.
- F4.09.1Namespace-prefix partitioning
- F4.09.2The BrandedChamp trie
- F4.09.3A BrandedChamp GenServer
Practical recipes in Elixir
Turning algorithmic problems into idiomatic Elixir.
- F4.10.1Idiomatic patterns
- F4.10.2Streams & pipelines
- F4.10.3Profiling & complexity
Dynamic programming & advanced problems
Overlapping subproblems, memoized and tabulated.
- F4.11.1Memoization & overlapping subproblems
- F4.11.2Tabulation & bottom-up
- F4.11.3Classic DP problems
Lab: build a branded CHAMP store
An interactive lab: insert branded keys and watch the partitioned CHAMP restructure.
- F4.12.1Watch a branded CHAMP grow
- F4.12.2A Snowflake registry
- F4.12.3Query by time range
Begin with F4.01 — Lists, recursion & complexity. The chapter builds toward the branded CHAMP map, so the early modules on cost and hashing pay off directly in the persistent-map spine.