Peeling the Banana: Recursion Schemes from First Principles

on YouTube ↗34m

" summary

Derives catamorphism from primitive recursion and functor algebras, implements generic folds and unfolds in Scala, and models factorial as a hylomorphism by composing a range coalgebra with a multiply algebra (no runtime tree built). Introduces the fixed-point type Fix to represent recursive types and reduce the in/out boilerplate, shows Scala code for cata/ana, and points to Matryoshka and Haskell’s recursion-schemes as ready libraries.

AI-written summary · about

" chapters (19)

1. 0:00Intro
2. 1:41The kind of banana
3. 4:16The journey
4. 5:42Recursive data types
5. 7:01Recursive collapse
6. 10:21Generalized collapse
7. 11:36Category Theory
8. 13:49Higher Kinded Types
9. 15:24Isomorphism
10. 16:11Functors
11. 17:34F-Algebras
12. 19:02Catamorphisms
13. 23:12Generalized building
14. 23:55Anamorphism
15. 25:44Generalized recursion
16. 26:27Hylomorphism
17. 28:23Boilerplate!
18. 29:41Removing boilerplate
19. 31:18Takeaways

" related talks

• 29mIntroduction to Recursion SchemesRatan Sebastian · Typelevel Summit NYC 2017
• 37mGoing bananas with recursion schemes for fixed point data typesPawel Szulc · Scala.IO 2017
• 56mAn introduction to recursion schemesNicolas Rinaudo · Scala Love in the City 2021
• 51mGoing bananas with recursion schemes for fixed point data typesPawel Szulc · Lambda Days 2017
• 38mRefactoring RecursionHarold Carr · Lambda World Cádiz 2019
• 32mRecursion schemes with HigherkindnessOli Makhasoeva, Andy Scott · Scale By The Bay 2019
• 01h 02mGoing bananas with recursion schemes for fixed point data typesPawel Szulc · Build Stuff 2016
• 47mHands on With Recursion Schemes - Part 1 of 2Jean Rémi Desjardins · LambdaConf 2017