jonnifyfsharp

Dive C4.01.1

Cons cells & recursion

A list is a head, then the rest. Build it with one operator, read it with one match, walk it with one recursive clause.

An F# list is a chain of cons cells. Each cell is a pair: a head (one value) and a tail (a pointer to the rest of the list). The :: operator (cons) reads and writes that shape, so [ "JOB07"; "JOB05"; "JOB02" ] is the same value as "JOB07" :: ("JOB05" :: ("JOB02" :: [])) — three cells ending in the empty list []. Two consequences follow at once. Prepending a head is O(1): a new cell points at the old list and the tail is shared, so nothing is copied. And every list function is written by recursion — match head :: tail, act on the head, recurse on the tail, and stop at []. Every echo below was produced by dotnet fsi.

Walk a list Module hub
C4.01.1 · part 1

The cons cell — a head and a tail

A list literal is shorthand. Underneath, each comma is a cons cell built with ::, and the chain ends in the empty list. The literal form and the cons form are the same value — F# confirms it with structural equality.

let backlog = [ "JOB07"; "JOB05"; "JOB02" ]   // newest first, for display
let consForm = "JOB07" :: ("JOB05" :: ("JOB02" :: []))
backlog = consForm   // val it : bool = true

A match splits one cell into its head and tail:

match backlog with
| h :: t -> printfn "head=%s tail=%A" h t   // head=JOB07 tail=["JOB05"; "JOB02"]
| [] -> printfn "empty"
cons cell
a pair of a head (one value) and a tail (a pointer to the rest); the unit a list is built from.
:: (cons)
the operator that prepends a head onto a tail. x :: xs builds a new cell pointing at xs.
head / tail
List.head reads the first value (O(1)); List.tail returns the rest of the chain (O(1)).
[] (empty)
the empty list — the terminator every chain ends in and every recursion stops at.
C4.01.1 · part 2

Prepend is O(1); the tail is shared

Prepending with :: allocates exactly one new cell, whose tail points at the existing list. The old list is untouched and reused — structural sharing. That is why admitting a new id to the front of a backlog costs the same whether the backlog holds three ids or three million.

let admitted = "JOB09" :: backlog
// val admitted : string list = ["JOB09"; "JOB07"; "JOB05"; "JOB02"]
// backlog is unchanged and shared as admitted's tail — nothing copied
Appending is the opposite. backlog @ [ "JOB11" ] must copy every cell of the left list to reach its end, so it is O(n). The third dive reads this cost from the shape. The rule of thumb: build lists at the head, reverse once at the end if you need the other order.

Recursion walks the chain

A list function follows the cell structure: match head :: tail, act on the head, call yourself on the tail, and stop at []. Step the walk below over the fixed backlog [ "JOB07"; "JOB05"; "JOB02" ]. The ring marks the current head; the readout shows the running count and the cell being matched. Reaching the end touches every cell — an O(n) walk.

count : match head :: tail → recurse tail

JOB07 JOB05 JOB02 [] count = 0
at the head JOB07 · match _ :: t → count becomes 1 and recurse on the tail.
let rec count xs =
    match xs with
    | [] -> 0
    | _ :: t -> 1 + count t
// val count: xs: 'a list -> int
count backlog   // val it : int = 3

One clause per shape: the empty list ends the walk, a cell does the work and recurses on its tail. Reaching the end is O(n) because every cell is touched once.

C4.01.1 · part 3

The same shape as Elixir's list

This is the structure the Elixir course teaches in E4.01, on the BEAM. Elixir writes the cell as [head | tail]; F# writes it as head :: tail. Both are immutable singly-linked lists with O(1) prepend, a shared tail, and recursion as the way to walk. The recursive clause is line-for-line the same shape.

Elixir — recursive sum over [h | t]

# Elixir — match [h | t], act, recurse on t
def sum([h | t]), do: h + sum(t)
def sum([]), do: 0

F# — recursive sum over head :: tail (verified in FSI)

let rec sum xs =
    match xs with
    | h :: t -> h + sum t
    | [] -> 0
// val sum: xs: int list -> int
The efficiency note: both are cons-cell lists, so the big-O is identical. The runtime under them differs — a BEAM list lives in a per-process heap, while an F# list cell is a CLR heap object holding a head and a tail reference (a value-type element is boxed). The shape is what fixes the cost; the runtime is what hosts it.

EchoMQ in F#

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.

The F# EchoMQ port (echo_fs) keeps each queue's pending ids in an ordered Set<string>. To show the backlog, Store.browse turns that set into a list, and a recursive walk reads it cell by cell — the exact pattern this dive teaches, over the real bus.

EchoMQ in F#

The pending backlog viewed as a list. Store.browse is 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

A recursive walk over that list shows each pending id, head to tail — the same head :: tail clause, applied to the backlog (verified in FSI over a fixed set):

let backlog = browse 3 st   // e.g. ["JOB07"; "JOB05"; "JOB02"]

let rec showBacklog xs =
    match xs with
    | [] -> ()
    | id :: rest -> printfn "  pending %s" id; showBacklog rest
showBacklog backlog
//   pending JOB07
//   pending JOB05
//   pending JOB02

The F# EchoMQ materializes and walks 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 shape

A list is head :: tail: O(1) prepend, a shared tail, and a recursive walk that touches every cell.

The next dive

That recursive walk grows the stack. The accumulator makes it a constant-stack loop — the form a consumer drain uses.

Where this leads

The cons cell and its recursion are the foundation. The next dive turns a stack-growing recursive walk into a constant-stack loop with an accumulator — the form a tail-recursive consumer drain takes over Jobs.claim. The third reads the cost of these operations from the shape.

↑ C4.01 · Lists, recursion & complexity C4.01.2 · Tail recursion → C4.01.3 · Complexity on .NET

References

Sources

Related in this course