Recursion schemes are a useful functional programming tool for writing algorithms on recursive data types. They come from the paper “Programming with Bananas, Lenses, Envelopes and Barbed Wire”, and have implementations in Haskell, Scala, PureScript, and untyped JS using FantasyLand. They can be mind-bending at first, and while there’s a lot of great resources for learning about them, most of these rely on a Haskell or Scala background. I published a library of schemes,
If you want to use recursion schemes but don’t care how or why they work, then you can probably skip this section and move straight to the articles on specific schemes. These posts explore the Y-combinator and fixed points in functions, and then apply those ideas to functors. The aim to to show why recursion schemes libraries do things the way they do, and to make the general ideas around recursion schemes feel intuitive and natural.
- An Introduction to Function Fixed Points with the Y-Combinator
- Variations on the Y-Combinator and Recursion
The schemes themselves
These posts focus on specific recursion schemes, showing the general class of problems that they can be used to solve, how they work, and some examples of how they might be used in practice. This section is still a work-in-progress.