Programming Languages · Cluster
Functional Programming
Purity, higher-order abstraction, and recursion schemes.
- 01 Referential Transparency and the Substitution Test What it means for an expression to be replaceable by the value it denotes, which features break that property, and what compilers and proofs gain when it holds.
- 02 Call-by-Need Evaluation and In-Place Thunk Update How a lazy argument becomes a shared thunk, why forcing it overwrites the thunk with its value, and where the resulting retention of unevaluated expressions costs memory.
- 03 Fold as the Universal List Eliminator Why foldr is the unique homomorphism from lists to any algebra, how the universal property turns programs into equations, and where foldl diverges from it.
- 04 Tail Position, Accumulators, and Continuation-Passing Style Why a call in tail position needs no return frame, how accumulator arguments turn structural recursion into a loop, and what the CPS transformation costs.
- 05 Fold Fusion and the Elimination of Intermediate Lists How the foldr/build rule removes intermediate lists at compile time, what deforestation generalized it to, and why strictness and sharing break the rewrite.
- 06 Catamorphisms and Anamorphisms over Recursive Functors How a recursive datatype becomes the least fixed point of a functor, why its fold is unique, and what an unfold adds that a fold cannot express.
- 07 Recursion Schemes: Catamorphisms, Anamorphisms, and Hylomorphisms The zoo of structured recursion operators, what each adds over the plain fold, and how the composition of a fold with an unfold collapses into a single pass.
- 08 Monadic Sequencing and the Encoding of Effects Why an effectful program is a value describing actions, how bind sequences those descriptions, and what the monad laws do and do not guarantee.
- 09 Free Monads and Defunctionalized Interpreters How a free monad turns a program into a syntax tree of requests, why the interpreter is a fold, and where the left-nested bind makes that tree quadratic.
- 10 Lenses and Traversals as Composable Immutable Accessors How the van Laarhoven encoding represents a lens as a function over functors, why the laws are not enforced, and what composition costs at run time.