awesome-recursion-schemes

Awesome Recursion Schemes

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

- Introduction to pattern functors, fix points, anamorphisms, catamorphisms, paramorphisms and hylomorphisms, requiring very little prior knowledge

- Three-part series in which you discover recursion schemes from scratch and implement a small subset of Edward Kmett's library

- Bartosz Milewski explains F-algebras and shows how to use them in the context of catamorphisms

- Series introducing recursion schemes and related concepts in JavaScript, aimed at developers with a minimal functional programming background

- List of various recursion schemes with code samples

Definition on the Haskell Wiki

- Short definition with code on School of Haskell by Edward Kmett

Using a hylomorphism to rotate a quadtree by Jared Tobin

Practical examples of pre- and postpromorphisms by Jared Tobin

Exploring histo and futu by example by Jared Tobin

Practical article about histomorphism and the futumorphism

Cheat Sheet

Map of various recursion schemes and their duals

Showing that the Visitor pattern implements an f-algebra for use with a catamorphism (in Java)

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

Introduces catamorphism as a generalization of fold

Advent of Code 2017, Domino challenge

Advent of Code 2018, String comparison challenge

- The original paper most of this is based on

- Shows that many basic sorting algorithms exist as a pair, and that these pairs arise naturally out of the duality between folds and unfolds

- Shows how paramorphisms and apomorphisms can be used for more efficient implementations of sorting algorithms

- Design pattern for writing programs that traverse data structures built from rich mutually-recursive data types

- "Recursion Schemes by Example" and "Exotic Tools for Exotic Trades" provide concise definitions as well as practical examples of many recursion schemes

- 12 min presentation by Ralf Hinze, Nicolas Wu, and Jeremy Gibbons

- Presented by Tim Williams at the London Haskell meetup

- Presented by Anthony Burzillo at the NYC Haskell User's Group

- Presented by Jean Remi Desjardins at Lambdaconf 2016

recursion-scheme-talk

Collection of slide decks about recursion schemes

High-level talk about structuring programs with coproducts and recursion schemes by Patrick Thomson

Introduction to recursive fix point data structures and recursion schemes in Haskell and Scala by Greg Pfeil

Bartosz Milewski's article in talk form, presented at LambdaCon

Zainab Ali's Introductory talk presented at LambdaWorld

Overview of different morphisms including a printable PDF

Casual discussions about category theory that often bring up recursion schemes, including which talks about Histomorphisms and Futumorphisms

Podcast about Scala that brings up recursion schemes in

Recursion schemes come up in

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

Katalyst

for Kotlin - a re-envisioning based off Matryoshka using lightweight higher kinded polymorphism