An introduction to recursion schemes
summary
Starts from a concrete cons list and refactors base case and step into a reusable fold → catamorphism, then generalizes by introducing a pattern functor (F) + Functor instance and a projection from the recursive type into F. Implements examples: product over lists and height of binary trees, shows the Fix (fixed‑point) encoding to remove boilerplate and discusses the tradeoff (library author vs user burden). Demonstrates exact code transformations and when each approach is preferable.
AI-written summary · about
chapters (8)
- 0:00Introduction to recursion
- 1:45Understanding data types
- 5:28Structural recursion patterns
- 10:02Generalizing structural recursion
- 15:49Abstraction with pattern functors
- 22:16Defining catamorphisms
- 30:52Applying recursion schemes
- 36:56Boilerplate and conclusions
related talks
38mRefactoring Recursion
29mIntroduction to Recursion Schemes
32mRecursion schemes with Higherkindness
34mPeeling the Banana: Recursion Schemes from First Principles
47mHands on With Recursion Schemes - Part 1 of 2
37mGoing bananas with recursion schemes for fixed point data types
01h 02mGoing bananas with recursion schemes for fixed point data types
31mAbstract your representation and fix your functors