The secret history of Recursion Schemes

TL;DR: From spaghetti goto to structured loops to tail-recursion and finally to recursion schemes, the talk traces how we learned to describe iteration mathematically and why most languages still hide the best abstractions. ## The goto abyss and the quest for structure Conditional branches give computers their power, but raw machine-level jumps tangle into unreadable “spaghetti.” Early programmers had no choice—until Fortran 54 offered symbolic expressions and automatic register allocation, trading 20 % performance for 5× programmer speed and 20× fewer lines of code. C added little beyond pointers and a bigger ecosystem; its real value was “infinite registers” handled by the compiler. Yet we kept the unrestricted goto. Dijkstra’s 1968 letter argued that goto density inversely measures code quality: unconstrained jumps erase any coordinate system for reasoning about intermediate states. The only excusable use is a forward jump to a single cleanup label when the program is already doomed. Linux still teems with gotos, evidence that kernel writers distrust compilers and enjoy “riding bareback on the silicon.” Locking the compiler to a rigid control-flow graph freezes intent in low-level details and removes pressure to make compilers better. ## Equations instead of loops To make progress observable we turn loops into equations: package the initial value, the update function, and the exit test into a self-contained **function**. If the function calls itself as its last act the call is **tail-recursive**, and decent compilers turn it into a jump. Old C compilers missed this, so Java speakers still chant “recursion can jump in a lake.” Modern GCC and Clang optimize tail calls—watch out only for Python, which explicitly forbids TCO to keep stack traces intact. Reading the generated assembly shows GCC pretending to optimize a tail-recursive Collatz yet returning 1 immediately (exploiting “infinite recursion is undefined”), while Clang emits a tidy loop. Moral: write tail-recursion or at least a do-while if you care about the loop shape. ## tailRec: one combinator to rule them all In Haskell we can capture the pattern once and for all: ```haskell tailRec :: (s -> Either r s) -> s -> r ``` The seed `s` is either replaced by a new seed (`Right`) or yields the final result (`Left`). Collatz becomes: ```haskell collatz = tailRec $ \n -> if n == 1 then Left 1 else Right (if even n then n `div` 2 else 3 * n + 1) ``` The structure—seed type, exit test, update—is declared in one line; the worker is a pure function, hence composable. Add monadic effects with `tailRecM`: ```haskell tailRecM :: Monad m => (s -> m (Either r s)) -> s -> m r ``` `tailRec` works only for **fixed-size state**; no unbounded memory is allocated and performance is predictable. Most languages, even those with higher-order functions, do not ship this combinator—Scala copied Haskell’s `recursion-schemes` library, but that’s an exception. ## When the data are recursive too Summing a list with naïve recursion keeps the whole spine on the stack. Tail-recursion fixes the stack but still forces us to “hammer a round peg into a square hole” by threading an accumulator and the remaining list as a pair. The real insight: **the control structure should mirror the data structure**. Recursive data types such as ```haskell data List a = Nil | Cons a (List a) data Rose a = Node a [Rose a] ``` are defined by their constructors and consumed by pattern matching. What we need are combinators that **traverse** these shapes while managing accumulators, effects, and early termination—something richer than `tailRec` yet just as generic. That “something richer” is the family of **recursion schemes**, the hidden heritage that mainstream languages still keep secret. Source: https://www.youtube.com/watch?v=JzMCwokUTl4