Peeling The Banana: Recursion Schemes from First Principles
summary
Derives recursion schemes from category theory and shows concrete implementations: uses functors, an isomorphism between R and F R, and the fixed-point type Fix to get in/out for recursive types; writes catamorphism folds (multiply, length), anamorphism unfolds (range), and composes them into a hylomorphism (factorial) that runs without building the intermediate list. Claims the technique generalizes across languages, notes under 5% audience familiarity with the banana paper (Meijer Fokkinga Paterson) and points to existing libraries.
AI-written summary · about
chapters (17)
- 0:00Intro
- 0:30The kind of banana
- 3:13The journey
- 4:03Recursive data types
- 5:26Recursive collapse
- 8:10Generalized collapse
- 9:09Category Theory
- 11:14Higher Kinded Types
- 12:43Isomorphism
- 15:33F-Algebras
- 16:38Catamorphisms
- 20:07Generalized building
- 21:15Anamorphism
- 23:04Generalized recursion
- 24:01Hylomorphism
- 27:20Removing boilerplate
- 33:29CODE MESH CALLING
related talks
58mMonoidal Catamorphisms
01h 52mIsomorphic Reasoning: Counting with Types Part 3
02h 28mIsomorphic Reasoning: Counting with Types Part 2
46mCorecursion, Codata, and Just a Little Combinatorial Game Theory
51mCategory Theory for People who Can't be Bothered to Learn It (Part 2)
01h 15mA Crash Course in Category Theory
01h 39mIsomorphic Reasoning: Counting with Types Part 1
38mCategory Theory as a Tool for Thought