Awesome Recursion Schemes – Massive Collection of Resources

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.

Contents

• Introductions
• Articles
• Papers
• Presentations
• Cheat Sheets
• Podcasts
• Implementations

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

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

Hylomorphisms in the Wild

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

• Stalking a Hylomorphism in the Wild – Advent of Code 2017, Domino challenge
• Open Seasons on Hylomorphisms – Advent of Code 2018, String comparison challenge

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

• 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.
• Peeling the Banana: Recursion Schemes from First Principles – Zainab Ali’s Introductory talk presented at LambdaWorld.

Cheat Sheets

• The Hitchhiker’s Guide to Morphisms – Overview of different morphisms including a printable PDF.

Podcasts

• Magic Read Along – Casual discussions about
  category theory that often bring up recursion schemes, including episode
  33 which talks about Histomorphisms
  and Futumorphisms.
• Scala Love – Podcast about Scala that brings up
  recursion schemes in the second episode.
• The Haskell Cast – Recursion schemes come up in
  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.