Recursion Schemes¶
Traversing nested data structures.
Source
46 resources imported from passy/awesome-recursion-schemes, dedicated to the public domain (CC0 / Unlicense). Thanks to its maintainers and contributors. Part of the KEEBOX Library · Category: Theory.
Introductions¶
- Awesome Recursion Schemes - A curation of useful resources for learning about and using recursion schemes.
- Practical Recursion Schemes -
- An Introduction to Recursion Schemes -
- Understanding Algebras -
- Recursion Schemes in JavaScript and Flow -
Articles¶
- Recursion Schemes: A Field Guide (Redux) -
- Catamorphisms - Definition on the Haskell Wiki.
- Catamorphisms -
- 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¶
- 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. -
- A Duality of Sorts, 2013, Hinze et al. -
- Sorting with Bialgebras and Distributive Laws, 2012, Hinze et al. -
- Scrap your boilerplate: a practical design pattern for generic programming, 2003, SPJ et al. -
Presentations¶
- Slidedecks by Tim Philip Williams -
- Unifying Structured Recursion Schemes -
- Recursion Schemes -
- F-algebras or: How I Learned to Stop Worrying and Love the Type System -
- A Gentle Introduction to Recursion Schemes -
- 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
- Scala Love - Podcast about Scala that brings up
- The Haskell Cast - Recursion schemes come up in
Implementations¶
- recursion-schemes for
- Matryoshka for Scala using Scalaz -
- andyscott/droste for Scala using Cats -
- recursion_schemes for
- purescript-matryoshka for PureScript -
- recursion for ATS - Demonstration of
- dada for Dhall - a library for recursion
- static-land-recursion-schemes for JavaScript/Flow -
- Katalyst for Kotlin - a re-envisioning based off Matryoshka using lightweight higher kinded polymorphism.