Module C4.01
Lists, recursion & complexity
A list points one way, head to tail. That asymmetry fixes the cost of every operation — and decides what a queue keeps its backlog in.
The F# list is a singly-linked list of cons cells, not an
array — the same shape the Elixir course teaches in E4.01, re-derived
here on .NET. One fact decides the rest: prepending a head is O(1) and shares the tail, while
reaching the far end is O(n). Every list function is written by recursion, and the cost of an
operation is the number of cells it touches. This module builds the list from three angles across three dives —
the cons-cell shape, the tail recursion that walks it without growing the stack, and the big-O cost that shape
implies. The running example is the F# EchoMQ port's pending backlog: the queue keeps its
pending ids in an ordered set, and Store.browse turns that set into a list to show.
One shape, three readings
A cons cell is a pair: a head (one value) and a tail (a pointer to the rest
of the list). The list [ "JOB07"; "JOB05"; "JOB02" ] is three cells chained to the
empty list []. The :: operator (cons) reads and writes that
shape; match splits a cell into its head and tail. From there everything follows.
The first dive states the cons cell and the recursion that walks it. The second turns a stack-growing walk
into a constant-stack loop with an accumulator, the form List.fold packages. The
third reads the cost from the shape — O(1) at the head, O(n) at the far end — and shows why a queue keeps its
pending ids in a sorted Set (O(log n) minimum) rather than a plain list (O(n)).
The three dives · select one
A list is head :: tail — a chain of cons cells ending in the empty list. Prepending a head is O(1) and shares the tail; recursion walks the chain one cell at a time.
Open this dive · or pick another above
The list points one way. Operations that work at the head are cheap; operations that need the far end are not. Everything in this module follows from that asymmetry.
A list is cons cells
The list literal and the cons form are the same value. Select an angle: the diagram marks the cells in focus,
the code shows the F# (verified in dotnet fsi), and the readout names what the shape
means. Prepend touches one cell; a walk touches them all.
The angle · select one
role: head :: tail
Prepend is one new cell pointing at the old list; a count is a walk over every cell. Read the cost from how far into the chain the operation reaches.
The module's running example — the pending backlog
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 dive in this module carries an EchoMQ in F# block, grounded in the real
echo_fs port — the F# skeleton of the EchoMQ bus at the repository root. The bus
keeps each queue's pending ids in an ordered Set<string>; the display path turns
that set into a list. That single function ties the whole module together: it is a list materialized from a
set, read by recursion, with a cost the third dive explains.
EchoMQ in F#
The pending backlog is the queue's set of not-yet-claimed job ids. To show it, Store.browse
turns the set into a list, newest first, capped at n — quoted verbatim from
echo_fs/EchoMQ/Store.fs:
/// Newest-first browse over the pending ids themselves (no second index). let browse (n: int) (st: QueueState) : string list = st.Pending |> Set.toList |> List.rev |> List.truncate n
Verified in dotnet fsi:
let browse (n: int) (pending: Set<string>) : string list = pending |> Set.toList |> List.rev |> List.truncate n // val browse: n: int -> pending: Set<string> -> string list browse 2 (Set.ofList [ "JOB07"; "JOB05"; "JOB02" ]) // val it: string list = ["JOB07"; "JOB05"]
The F# EchoMQ materializes the backlog as a list today, from the in-memory core
(echo_fs/EchoMQ/Store.fs, Jobs.fs — built and tested). The
Valkey transport (EchoMQ.Connector) lands next; until then
Connector.eval raises "EchoMQ Valkey connector: coming soon".
The three dives
Read them in order. Each stands on valid F#: every // val it : echo below the code was
produced by dotnet fsi, and each carries an EchoMQ in F# block grounded in the
echo_fs port. Together they take a list from its shape, through the recursion that walks
it, to the cost model that decides which structure a queue keeps.
Cons cells & recursion
A list is head :: tail; prepend is O(1) and shares the tail; recursion walks the chain to [].
- EchoMQthe backlog as a list — a recursive walk over
Store.browse
Tail recursion & the accumulator
The accumulator turns a stack-growing walk into a constant-stack loop; List.fold names the pattern.
- EchoMQa tail-recursive consumer drain —
Jobs.claimuntilNone
Complexity on .NET
O(1) head versus O(n) length, append and last — and why pending is a sorted Set, not a list.
- EchoMQwhy
Pendingis aSet— O(log n) minimum, not O(n)
Elixir E4.01 · the same shape
Elixir's [head | tail] is a cons-cell list with O(1) prepend, a shared tail, and O(n) length — the model the Elixir course teaches.
F# C4.01 · on .NET
F#'s head :: tail is the same immutable cons-cell list. The cost model is identical; the runtime under it (the CLR, boxed reference cells) differs.
References
Sources
- Microsoft — F# documentation — lists, the
::operator, and recursion. - FSharp.Core API reference — the
ListandSetmodules. - The F# Software Foundation — F#'s home on the .NET runtime.
- Microsoft — .NET documentation — the CLR cost model the third dive reads against.
Related in this course
- Elixir — Lists, recursion & complexity (E4.01) — the sibling this module mirrors.
- C4 — Algorithms & Data Structures — the chapter this module opens.
- C1.07 — Collections — list, array, seq, Map & Set — the F# collection types in depth.
- C4.01.1 — Cons cells & recursion — start the module here.