Recursion Schemes in JavaScript and Flow with static-land-recursision-schemes
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, static-land-recursion-schemes, which provides them for use in JavaScript code typed with Flow, using flow-static-land. I don’t think a GitHub README is enough of an introduction to properly learn what recursion schemes are and how to use them, so I’m putting a series of tutorials on them on Medium. My aim is to make all of these posts accessible to developers who are familiar with JavaScript and Flow, without relying on knowledge of other functional languages, or of any functional techniques besides the use of higher-kinded types in Flow using brands. This post is the table of contents for this series, and will be updated as I add more posts.
The basics
A Brief Introduction to Recursion Schemes
Digging deeper
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.
- Catamorphisms
- Anamorphisms
- Hylomorphisms
- Paramorphism (coming soon)
