Introduction to Recursion Schemes
summary
Argues that explicit recursion yields duplicated traversal logic and instead implements generic traversals by encoding data as a pattern functor plus a Fix+Functor abstraction, then defines reusable catamorphism/anamorphism/paramorphism/apomorphism primitives in plain Scala (no heavy language features). Shows concrete algebras/co-algebras for sum, length, range, reconstructing a list from a sum, ordered insert, and merge sort via a hylomorphism; the implementations compile and compose, and the talk points to the matryoshka library and slides for runnable code.
AI-written summary · about
chapters (31)
- 0:00Introduction
- 1:00Exclusive Recursion
- 3:46Types of Recursion
- 4:13Kerimov System
- 4:42Sum Function
- 5:37Fold Function
- 7:51Subtree vs List
- 8:25Constructors
- 9:17Lists
- 10:24Trees
- 10:38Generic Fold
- 10:51Outputs
- 11:17The Problem
- 11:30Fix
- 13:01Pattern Matching
- 13:46Unfix Method
- 13:58Algebra
- 14:32Functor
- 15:47Examples of algebra
- 17:36Animals
- 18:17Co Algebra
- 20:20Range
- 20:57Unfold
- 21:36Para
- 21:52Algebras
- 23:56T Algebra
- 24:06Aapko
- 25:08Cosome
- 25:31Insert
- 26:29Hilarmorphisms
- 27:34Conclusion
related talks
56mAn introduction to recursion schemes
34mPeeling the Banana: Recursion Schemes from First Principles
47mHands on With Recursion Schemes - Part 1 of 2
32mRecursion schemes with Higherkindness
38mRefactoring Recursion
37mGoing bananas with recursion schemes for fixed point data types
51mGoing bananas with recursion schemes for fixed point data types
31mAbstract your representation and fix your functors