F4 · Foundations · module 1
Lists, recursion & complexity
The list is the BEAM's fundamental sequence, and it is a linked list of cons cells, not an array. That one fact explains everything that follows: why prepending is instant, why finding the length is not, why every list function is written by recursion, and how to read the cost of an operation straight from the shape of the data.
This module builds the list from three angles — the cons-cell shape, the recursion that walks it, and the big-O cost that shape implies. The portal's lesson minutes are the running example.
Prepend is O(1)
[12, 8, 30]
Prepend adds one cell pointing at the old head — O(1).
A list is cons cells
Each cons cell is a pair: a head (one value) and a tail (a pointer to the rest of the
list). [12, 8, 30] is three cells chained to the empty list [].
Select an angle to see what that shape means.
The angle · select one
role: [head | tail]
The list points one way, from head to tail. Operations that work at the head are cheap; operations that need the far end are not. Everything in this module follows from that asymmetry.
Three deep dives
In order: the cons-cell shape and its O(1) prepend; the recursion that walks a list; then the big-O cost model that shape gives you, and the operations to avoid in a hot path.
[head | tail]. Prepending is O(1); hd/1 and tl/1 read the cell; appending must copy.[h | t], act on the head, recurse on the tail, stop at [] — with a tail-recursive accumulator.++, and last — reading cost from how many cells an operation must touch.F3 · processes held state
In F3 a process kept state between messages. That state is made of data — and the list is where data structures start.
F4 · the data and its cost
A list is a chain of cons cells. Its shape fixes the cost of every operation, which is what this chapter learns to read.
Start with cons cells, then recursion over lists, then complexity on the BEAM. Next module: F4.02 — Trees & traversals, where the tail becomes two branches and a walk becomes a traversal.
References
Primary sources for this lesson, and where it connects in the course.
Sources
List— Elixir documentation — cons-cell lists and the functions over them.- Efficiency Guide — Erlang/OTP documentation — operation complexity on the BEAM.
- Okasaki, C. (1996). Purely Functional Data Structures. — the foundational text on persistent structures.