Going bananas with recursion schemes for fixed point data types
summary
Claims a working Scala library and patterns not just theory: a Matryoshka Scala port implements generalized catamorphisms over Fix types, with code that builds expressions, defines F-algebras (evaluate, makeString, optimize) and runs catamorphism/anamorphism/hylomorphism. Examples show how Fix represents recursive ASTs, how hylo fuses unfold+fold for performance (nearly two‑times saving claimed), and a real project Quasar uses it in production so far without trampoline workarounds.
AI-written summary · about
chapters (41)
- 0:00Introduction
- 2:45Recursive structures
- 3:25Expressions
- 4:23Representation
- 4:41Color
- 5:11Evaluate
- 6:12String
- 8:55Traversing the structure
- 11:18Polymorphic
- 12:28Is it possible
- 13:07Expression of unit
- 14:19More complicated example
- 15:07String example
- 15:35Six point data type
- 15:51Professional speakers
- 16:01My wife
- 16:14Cat
- 16:40FixSex
- 18:07Express
- 18:24Integers
- 20:22Final structure
- 21:27Recap
- 22:20Kathamorphism
- 22:41Cattlemorphism
- 24:13Functor
- 26:56Implementation
- 28:27Algebra of Si
- 29:14The Driver
- 30:01The Algebra
- 32:24Optimize
- 33:19Catamorphism
- 33:32Other systemmorphisms
- 34:26Anamorphism example
- 34:42Dual full algebra
- 34:53Two expressions of double
- 35:44Highlowmorphism
- 35:56Catabolism
- 38:13Composable
- 43:11Quasar
- 43:38Twitter
- 43:57Tail recursion
related talks
37mGoing 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
31mAbstract your representation and fix your functors
34mEfficient Nanopass Compilers using Cats and Matryoshka
02h 00mUsing Corecursion Schemes