Awesome Recursion Schemes

A curation of useful resources for learning about and using recursion schemes.

Recursion schemes are simple, composable combinators, that automate the process of traversing and recursing through nested data structures.

Introductions

Practical Recursion Schemes - Introduction to pattern functors, fix points, anamorphisms, catamorphisms, paramorphisms and hylomorphisms, requiring very little prior knowledge.
An Introduction to Recursion Schemes - Three-part series in which you discover recursion schemes from scratch and implement a small subset of Edward Kmett's library.
Understanding Algebras - Bartosz Milewski explains F-algebras and shows how to use them in the context of catamorphisms.

Recursion Schemes: A Field Guide (Redux) - List of various recursion schemes with code samples.
Catamorphisms - Definition on the Haskell Wiki.
Catamorphisms - Short definition with code on School of Haskell by Edward Kmett.
Rotating Squares - Using a hylomorphism to rotate a quadtree by Jared Tobin.
Promorphisms, Pre and Post - Pratical examples of pre- and postpromorphisms by Jared Tobin.
Time Traveling Recursion Schemes - Exploring histo and futu by example by Jared Tobin.
Cheat Sheet - Map of various recursion schemes and their duals.
Correcting the Visitor pattern - Showing that the Visitor pattern implements an f-algebra for use with a catamorphism (in Java).

Functional Programming with Bananas, Lenses, Envelopes and Barbed Wire, 1991, Meijer et al. - The original paper most of this is based on.
A Duality of Sorts, 2013, Hinze et al. - Shows that many basic sorting algorithms exist as a pair, and that these pairs arise naturally out of the duality between folds and unfolds.
Sorting with Bialgebras and Distributive Laws, 2012, Hinze et al. - Shows how paramorphisms and apomorphisms can be used for more efficient implementations of sorting algorithms.
Scrap your boilerplate: a practical design pattern for generic programming, 2003, SPJ et al. - Design pattern for writing programs that traverse data structures built from rich mutually-recursive data types.

Slidedecks by Tim Philip Williams - "Recursion Schemes by Example" and "Exotic Tools for Exotic Trades" provide concise definitions as well as practical examples of many recursion schemes.
Unifying Structured Recursion Schemes - 12 min presentation by Ralf Hinze, Nicolas Wu, and Jeremy Gibbons.
Recursion Schemes - Presented by Tim Williams at the London Haskell meetup.
F-algebras or: How I Learned to Stop Worrying and Love the Type System - Presented by Anthony Burzillo at the NYC Haskell User's Group.
A Gentle Introduction to Recursion Schemes - Presented by Jean Remi Desjardins at Lambdaconf 2016.
recursion-scheme-talk - Collection of slide decks about recursion schemes.
Bracer: Transforming Real-World Languages with Coproducts and Recursion Schemes - High-level talk about structuring programs with coproducts and recursion schemes by Patrick Thomson.
Recursion: Where Functional Programming Hits Bottom - Introduction to recursive fix point data structures and recursion schemes in Haskell and Scala by Greg Pfeil.
Programming with algebras - Bartosz Milewski's article in talk form, presented at LambdaCon.

Magic Read Along - Casual discussions about category theory that often bring up recursion schemes, including episode 33 which talks about Histomorphisms and Futumorphisms.

recursion-schemes for Haskell - The canonical implementation by Edward Kmett.
Matryoshka for Scala - Generalized folds, unfolds, and traversals for fixed point data structures.
purescript-matryoshka for PureScript - Work-in-process port of matryoshka.

This content is licensed under CC0.