← Back to Awesome

Sections

Recursion Schemes

GitHub repository ↗ synced 2026/8/9

Awesome Recursion Schemes Awesome

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

Awesome Recursion Schemes

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

  • 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 in JavaScript and Flow -
    Series introducing recursion schemes and related concepts in JavaScript,
    aimed at developers with a minimal functional programming background.

Articles

Catamorphisms

Definition on the Haskell Wiki.

Rotating Squares

Using a hylomorphism to rotate a quadtree by Jared Tobin.

Recursion Schemes, Part V: Hello, Hylomorphisms
Promorphisms, Pre and Post

Practical examples of pre- and postpromorphisms by Jared Tobin.

Time Traveling Recursion Schemes

Exploring histo and futu by example by Jared Tobin.

Recursion Schemes, Part IV: Time is of the Essence

Practical article about histomorphism and the futumorphism.

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).

Recursion Schemes in Scala

Introduces the fixpoint combinator, anamorphism, catamorphism, hylomorphism, paramorphism, apomorphism, histomorphism, dynamorphism and futumorphism.

What's in a Fold: The Basic Catamorphism in recursion-schemes

Introduces catamorphism as a generalization of fold.

  • Recursion Schemes: A Field Guide (Redux) -
    List of various recursion schemes with code samples.
  • Catamorphisms -
    Short definition with code on School of Haskell by Edward Kmett.

Hylomorphisms in the Wild

Stalking a Hylomorphism in the Wild

Advent of Code 2017, Domino challenge

Open Seasons on Hylomorphisms

Advent of Code 2018, String comparison challenge

Articles by Bartosz Milewski about solving small, practical problems by applying a hylomorphism.

Papers

  • 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.

Presentations

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.

Peeling the Banana: Recursion Schemes from First Principles

Zainab Ali's Introductory talk presented at LambdaWorld.

  • 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.

Cheat Sheets

The Hitchhiker's Guide to Morphisms

Overview of different morphisms including a printable PDF.

Podcasts

Magic Read Along

Casual discussions about

Scala Love

Podcast about Scala that brings up

The Haskell Cast

Recursion schemes come up in

category theory that often bring up recursion schemes, including episode
33
which talks about Histomorphisms
and Futumorphisms.
recursion schemes in the second episode.
Episode 13 with John Wiegley.

Implementations

  • recursion-schemes for
    Haskell - The canonical implementation by Edward Kmett.
  • Matryoshka for Scala using Scalaz -
    Generalized folds, unfolds, and traversals for fixed point data structures.
  • andyscott/droste for Scala using Cats -
    Generalized folds, unfolds, and traversals for fixed point data structures.
  • recursion_schemes for
    Idris, based off Edward Kmett's Haskell library.
  • purescript-matryoshka for PureScript -
    Work-in-process port of matryoshka.
  • recursion for ATS - Demonstration of
    recursion schemes in ATS.
  • dada for Dhall - a library for recursion
    schemes in Dhall.
  • static-land-recursion-schemes for JavaScript/Flow -
    Schemes for data structures written in the style of flow-static-land.
  • Katalyst for Kotlin - a re-envisioning based off Matryoshka using lightweight higher kinded polymorphism.