jonnifyfsharp

Chapter C4

Algorithms & Data Structures

The structures a message queue is built from — re-derived in F#.

This chapter walks the same twelve rungs as the Elixir course's E4 · Algorithms & Data Structures — lists, trees, sorting, maps, HAMT, CHAMP, branded ids, persistence, a CHAMP behind an actor, recipes, dynamic programming, a lab — re-derived in F# with cross-links to each E4 sibling and notes on the F# implementation and its efficiency. The running example is EchoMQ, the Valkey-native job bus, now taking shape in F# as the echo_fs port: every dive shows how that port — an in-memory model — uses the structure. The EchoMQ protocol itself, the Lua transitions executing on a Valkey wire, is not implemented yet; that is the coming-soon transport. Twelve modules, three dives each.

The twelve modules The Elixir E4 chapter
branded id JOB + base62 pending — sorted set byte order = mint order broker — MailboxProcessor one writer consumer

The queue is made of these

A message queue is not a special structure. It is a few ordinary ones, assembled: a sorted set of time-ordered ids, a map of rows, a recurrence for the retry delay, and one writer to keep mints from racing. That is the whole chapter — each rung builds one of those pieces, and each dive shows the piece at work in EchoMQ.

EchoMQ keeps its pending jobs in a sorted set keyed by the branded id. Because the id is a time-ordered Snowflake and the Base62 encoding is fixed-width, the id order is the mint order — so the oldest job is always the smallest id, and a claim is a single pop-minimum with no second index to maintain. Claim the next job below and watch it leave oldest-first. The numbers come from the real echo_fs port.

Mint-ordered claim · EchoMQ in F#

pending — sorted by branded id pop-min claimed — the oldest mint

Pending (sorted set · head = oldest)

  • +5msinvoice.send
  • +12msreport.nightly
  • +23mswebhook.retry
  • +40msemail.welcome
  • +58mscache.warm
  • +71msimage.resize

Served (claim order)

  • none yet
Six jobs, each minted a few milliseconds apart, sit in the pending set sorted by branded id. Claim the next and the smallest id leaves first — the earliest mint, served with no second index.
// echo_fs — the F# EchoMQ (in-memory core built; Valkey wire coming soon)
let st, job = EchoMQ.Jobs.claim now leaseMs queue
//        pops the smallest branded id = the oldest mint

A queue is a sorted set of time-ordered ids, a map of rows, and one writer — the same algorithms this chapter builds, assembled into a bus.

The twelve modules

Each module re-derives one E4 rung in F#, three dives at a time, and carries an EchoMQ in F# block in every dive — a short scenario showing how the bus uses that structure, grounded in the real echo_fs port. The last module is a hands-on lab: assemble the pieces into a working in-memory queue.

live chapter front door built lesson ready soon specified
C4.01built

Lists, recursion & complexity

Cons cells; big-O on .NET.
C4.02built

Trees & traversals

Binary and n-ary trees; DFS/BFS, functionally.
C4.03built

Sorting & searching

Merge/quick sort and binary search, immutably.
C4.04built

Maps, sets & hashing

Hash maps, collisions, the cost model.
C4.05built

Hash Array Mapped Tries (HAMT)

Persistent maps via prefix trees.
C4.06built

CHAMP maps

Compressed Hash-Array Mapped Prefix-trees; layout & iteration.
C4.07built

Identifiers, Snowflake & branded ids

From naive ids to a Snowflake bigint and a branded, base62 id.
C4.08built

Branded ids & persistence

Branded ids as keys in SQLite, PostgreSQL, and Redis.
C4.09built

Branded CHAMP maps & MailboxProcessor

A CHAMP keyed by branded ids, behind F#’s actor — the MailboxProcessor.
C4.10built

Practical recipes in F#

Turning algorithmic problems into idiomatic F#.
C4.11built

Dynamic programming & advanced problems

Overlapping subproblems, memoized and tabulated.
C4.12built

Lab: build a branded CHAMP store

Assemble the pieces into a working in-memory queue.

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.

References

Sources

Related in this course