Pearls: Beauty in Small Programs
A gallery of short, famous Haskell programs — Quicksort and Mergesort with no swaps or mutation at all, primes tested against the literal textbook definition, and an infinite list of Fibonacci numbers defined in terms of itself — each one a small, complete demonstration of everything this book has covered.
Every field has its “pearls” — short programs so clean they get passed around and taught for decades, each one a complete, self-contained argument for why the language it’s written in exists. This chapter is a small gallery of them, chosen because each one directly showcases an idea from earlier in this book.
Quicksort, with no swaps at all
Quicksort, as it’s usually taught, is inseparable from mutation: pick a pivot, walk two indices toward each other swapping elements, partition the array in place. Here is a complete, correct, textbook C++ implementation — the Lomuto partition scheme:
// C++: classic in-place quicksort with explicit index bookkeeping
int partition(std::vector<int>& a, int lo, int hi) {
int pivot = a[hi];
int i = lo - 1;
for (int j = lo; j < hi; j++) {
if (a[j] < pivot) {
i++;
std::swap(a[i], a[j]); // mutation: two elements swap places
}
}
std::swap(a[i + 1], a[hi]); // pivot slides into its final spot
return i + 1;
}
void quicksort(std::vector<int>& a, int lo, int hi) {
if (lo < hi) {
int p = partition(a, lo, hi);
quicksort(a, lo, p - 1);
quicksort(a, p + 1, hi); // sort left and right of the pivot
}
}
Every line of partition is bookkeeping: tracking two indices, deciding when to swap, making sure i and j never trip over each other. It’s efficient — genuinely one of the best general-purpose sorts there is — but reading it tells you almost nothing about why it sorts. You have to trace through the index arithmetic by hand to convince yourself it’s correct.
Now the Haskell version — a direct transcription of quicksort’s actual mathematical definition, from Chapter 5’s insert and this book’s earlier list-comprehension examples:
quicksort :: Ord a => [a] -> [a]
quicksort [] = []
quicksort (p:xs) = quicksort smaller ++ [p] ++ quicksort larger
where
smaller = [x | x <- xs, x < p]
larger = [x | x <- xs, x >= p]
Figure: quicksort (3 : [7,1,9,4,2]) builds two brand-new lists — everything less than 3, and everything not — then recurses on each and glues the three pieces back together with ++. No index ever moves; nothing is ever swapped; every list involved, old and new, coexists unmodified for as long as anything still needs it.
Read the Haskell version aloud and it is the definition of quicksort: “the sorted list is the sorted smaller elements, then the pivot, then the sorted larger elements.” There is no bookkeeping to trace, because Chapter 5’s immutability means smaller and larger are simply values — computed once, referred to as often as needed, never at risk of the kind of off-by-one error that plagues hand-written partition loops.
This version is not a free lunch on performance: ++ costs time proportional to the length of its left argument, and building two entirely new lists per recursive call allocates far more than the in-place C++ version, which sorts within the original array using only auxiliary stack space. The Haskell version above is a pearl precisely because of its clarity, not because it’s the fastest possible quicksort — Haskell can still get a genuinely in-place quicksort back using the ST monad’s local mutability, once clarity has done its job of proving the algorithm correct.
This exact five-line quicksort, sometimes attributed informally to conversations following Tony Hoare’s original 1960 invention of the algorithm, is one of the most-quoted pieces of Haskell ever written — often used specifically to make the case that functional code can be shorter and more obviously correct than its imperative equivalent, not just different in style.
Mergesort: split, sort, merge
Quicksort partitions around a pivot; mergesort takes an even more direct route to the same goal — split the list in half, sort each half (however that gets done — including, recursively, by more splitting), then merge the two sorted halves back together in order.
Figure: Split all the way down to single elements — already trivially sorted — then merge pairs back together, in order, all the way back up. Every merge step is a simple linear scan comparing two already-sorted lists; nothing about it needs a pivot, an index, or a swap.
merge :: Ord a => [a] -> [a] -> [a]
merge [] ys = ys
merge xs [] = xs
merge (x:xs) (y:ys)
| x <= y = x : merge xs (y:ys)
| otherwise = y : merge (x:xs) ys
mergeSort :: Ord a => [a] -> [a]
mergeSort [] = []
mergeSort [x] = [x]
mergeSort xs = merge (mergeSort left) (mergeSort right)
where
(left, right) = splitAt (length xs `div` 2) xs
merge is the only place any actual comparing happens, and it reads exactly like the picture: walk both sorted lists side by side, always taking the smaller of the two current heads, until one list runs out — at which point the rest of the other list is already sorted, so it’s simply appended as-is. mergeSort itself does no comparing at all; it just keeps splitting until [] or a singleton (both trivially already sorted), then leans entirely on merge to reassemble the answer.
Mergesort’s worst-case time is , guaranteed — unlike the naive quicksort above, there’s no already-sorted-input pathology to worry about, because mergesort’s split point is always the middle, regardless of what the data looks like. The tradeoff is that a fully persistent, immutable mergesort like this one needs auxiliary space for the merge step, where a well-tuned in-place quicksort can get by with .
Notice the shape of mergeSort itself: two base cases ([] and [x]) and one recursive case that combines the results of two smaller subproblems — the textbook definition of a divide-and-conquer algorithm, transcribed with nothing extra. merge, meanwhile, is doing something you’ll see again shortly: threading through two lists in lockstep, choosing an output at each step, is exactly the shape zipWith uses in the fibs pearl below — just with a comparison instead of a fixed combining function.
Chapter 6 built the infinite list of primes with a sieve — elegant, but the sieving trick (filter out multiples of each prime as you find it) takes a moment of cleverness to see why it works at all. Here is a second, even more literal pearl: primality tested by simply asking the definition of “prime” the question directly.
A number’s factors are exactly the numbers that divide it evenly:
factors :: Int -> [Int]
factors n = [x | x <- [1..n], n `mod` x == 0]
ghci> factors 12
[1,2,3,4,6,12]
ghci> factors 13
[1,13]
A number is prime precisely when its only factors are 1 and itself — which is not a clever trick, it’s the textbook definition, transcribed directly:
isPrime :: Int -> Bool
isPrime n = factors n == [1, n]
primes :: [Int]
primes = filter isPrime allPositiveIntegers
where
allPositiveIntegers = [1..]
ghci> take 10 primes
[2,3,5,7,11,13,17,19,23,29]
filter isPrime allPositiveIntegers reads exactly the way you’d say it out loud: “the primes are whichever positive integers are prime.” Chapter 6’s laziness is what makes this legal at all — allPositiveIntegers is a genuinely infinite list, and filter only ever forces as many of its elements as take 10 (or whatever calls it) actually demands, checking isPrime on each candidate one at a time, forever, without needing to know in advance where to stop.
isPrime here recomputes factors n from scratch for every candidate, checking divisibility by every number up to n — work per candidate, compared to the sieve’s much cheaper amortized cost of only checking against primes already found. This version is a pearl for the same reason quicksort was: it is a direct, obviously-correct transcription of the definition, not the fastest way to compute the answer. Reach for this version to state what “prime” means unambiguously; reach for the sieve, or a proper trial-division-with-early-exit, when performance actually matters.
Notice the shape: isPrime doesn’t loop, doesn’t count, doesn’t track a running divisor — it asks a single yes/no question by comparing two lists, factors n and [1, n], for equality. This is the same instinct behind quicksort and Chapter 3’s colourOf: state what the answer is a comparison against, and let list equality and list comprehensions do the rest — math notation with :: instead of , the same correspondence Chapter 2 opened with.
Fibonacci, defined in terms of itself
Here is a third, arguably even more startling pearl: the infinite list of Fibonacci numbers, defined by referring to itself:
fibs :: [Integer]
fibs = 0 : 1 : zipWith (+) fibs (tail fibs)
ghci> take 10 fibs
[0,1,1,2,3,5,8,13,21,34]
Read this the way Chapter 6 taught: fibs is a value, not a function call, and Haskell’s laziness means the right-hand side isn’t computed all at once — it’s built exactly as far as something demands. zipWith (+) fibs (tail fibs) pairs each element of fibs with the next element of fibs and adds them — but fibs is the very list being defined, so this only works because laziness lets you refer to a value while it’s still being constructed, consuming each cell only after it already exists.
fibs = 0 : 1 : 1 : 2 : 3 : 5 : 8 : ...
tail fibs = 1 : 1 : 2 : 3 : 5 : 8 : ...
zipWith (+) = 1 : 2 : 3 : 5 : 8 : ... (this becomes fibs, from the 3rd element on)
Every element past the first two is defined as the sum of the two before it — which is exactly the mathematical definition of the Fibonacci sequence, transcribed with no loop, no mutable accumulator, and no explicit recursion on an index at all.
This style — a value defined using itself, made to work by laziness delaying evaluation just long enough — is called corecursion, and it is the natural dual of the ordinary recursion Chapter 4’s length' used. Where recursion breaks a finite problem down into smaller pieces until it bottoms out, corecursion builds a (potentially infinite) structure outward, one lazily-demanded piece at a time. primes from Chapter 6 and fibs here are both corecursive for exactly this reason.
Why these count as “beautiful”
All four pearls share the same shape: each is a direct transcription of the mathematical or logical definition of the problem, rather than a set of instructions for solving it. That gap — between describing what something is and instructing a machine how to compute it step by step — is the gap this entire book has been walking across, one vantage point at a time: immutability (Chapter 5) is what lets smaller and larger be trusted values instead of moving targets; laziness (Chapter 6) is what lets primes and fibs refer to an infinite space, or to themselves, without looping forever; purity (Chapter 7) is what lets you trust that quicksort xs means the same thing everywhere it appears.
Short, self-evidently-correct code isn’t just an academic nicety — it’s a direct productivity and safety argument. Codebases with a strong functional-core discipline (even in otherwise imperative languages, via libraries like Java’s Streams or C++‘s ranges) consistently report fewer off-by-one and state-synchronization bugs in exactly the kind of code these pearls represent: partitioning, filtering, and building sequences.
This is also, deliberately, close to the end of the pilgrimage. Every idea these short programs lean on — types, immutability, laziness, purity, and the Functor/Applicative/Monad vocabulary from the summit — is something you now have a name for. That’s the real payoff of the climb: pearls like these stop looking like tricks, and start looking like the obvious way to write the code.