Going bananas with recursion schemes for fixed point data types
summary
Claims a workable generalization of catamorphism to fixed‑point data types, implemented in Scala with Matryoshka and demonstrated on expression ASTs. Shows concrete algebras for evaluation, printing and an optimizer, replaces explicit recursion with reusable folds/unfolds, and composes anamorphism+cata into a single-pass hylomorphism for performance. Provides runnable code, integration notes, and cites papers; used in Quasar’s compiler work and shown to actually compile and run.
AI-written summary · about
chapters (9)
- 0:00Start
- 2:12Recursive Structures are common
- 20:56Functor 101
- 22:54Missing Ingredients
- 23:10E-algebra
- 26:12Anamorphism
- 28:11Hylomorphism
- 35:00To sum it up
- 36:24References
related talks
51mGoing bananas with recursion schemes for fixed point data types
34mPeeling the Banana: Recursion Schemes from First Principles
29mIntroduction to Recursion Schemes
01h 02mGoing bananas with recursion schemes for fixed point data types
47mHands on With Recursion Schemes - Part 1 of 2
56mAn introduction to recursion schemes
34mEfficient Nanopass Compilers using Cats and Matryoshka
02h 00mUsing Corecursion Schemes