Recursion Schemes in Plain Language
summary
Recursion schemes claim that walking a recursive structure is separable from the operation applied at each node, so separates traversal from node logic and lets one reuse the same walk (fold, unfold, refold, apomorphism, Elgot, etc.). Examples: fold implements sum and map variations, unfold builds lists from seeds, refold interleaves unfold and fold and is used to transform ASTs. The talk asserts recursion schemes handle 80% of hard recursive cases and reports using refold in a compiler to transform/generate code successfully.
AI-written summary · about
chapters (27)
- 0:00Recursion schemes intro
- 1:06Personal journey
- 4:20Why recursion schemes
- 5:03Recursive data structures
- 7:13Practical recursive examples
- 8:22Introducing recurse
- 11:42Core concept
- 13:51Recurse vs recur
- 14:38How fold works
- 18:29Depth-first with fold
- 19:55Map with fold
- 21:23Unfold intro
- 23:57Unfolding a list
- 25:22Combine unfold and fold
- 27:10Refold in compilers
- 28:14Other recursion schemes
- 30:42Components breakdown
- 32:29Apomorphism
- 34:37Elgot recursion
- 35:20Terminology decoder
- 37:06Base functors
- 38:10Sorting with recursion
- 38:54Learning resources
- 40:20Hyomorphism perf
- 41:30When recursion schemes are most useful
- 42:13Pitfalls
- 43:43Q&A
related talks
53mReduce: From functional programming to C++17 Fold expressions
05mThe Shape of a Program
33mDeclarative programming in Rust
31mFunctional programming guerilla in the land of Rust
33mRust and Haskell, sitting in a tree
01h 27mDeclarative thinking, declarative practice
41mFunctional Rust - An Exploration
25mCompositional Reasoning about Advanced Iterator Patterns in Rust