RecursionSchemas.MD

Recursion Schemes

• Implementations:
  Scala for Cats: andyscott/droste for Scalaz: slamdata/matryoshka
  Haskell ekmett/recursion-schemes vmchale/recursion
  Idris vmchale/recursion_schemes
  Purescript slamdata/purescript-matryoshka
  Kotlin aedans/Katalyst

• Resources:

  • slamdata/matryoshka main page contains very good overwie, PDF with summary of Recursion schemes
  • Introduction to Recursion Schemes with Matryoshka - Anatolii Kmetiuk (tutorial)
  • (Haskell) Recursion Schemes: A Field Guide (Redux) - Edward Kmett: (blog post)
  • Resources for learning and using recursion schemes - Pascal Hartig
  • (Haskell) Functional Programming with Bananas, Lenses, Envelopes and Barbed Wire - Erik Meijer, Maarten Fokkinga, Ross Paterson: (paper Haskell)
  • (Haskell) Rotten Bananas - Edward Kmett: (blog post)
  • (Haskell) Unnatural Transformations - Edward Kmett (blog post)
  • (Haskell) Program Reduction: A Win for Recursion Schemes - John Wiegley (blog post)
  • https://scrapbox.io/haskell-shoen/Recursion_Schemes

Algebra, Coalgebra, ElgotAlgebra

• Resources
  • slamdata/matryoshka docs - Algebras
  • (Haskell) Constructions on Typeclasses, Part 1: F-Algebras - Luke Palmer (blog post)
  • (Haskell) loop/recur F-Algebras Part 1 (video)
  • (Haskell) loop/recur F-Algebras Part 2 (video)
  • (Haskell) loop/recur F-Algebras Part 3 (video)

Fixpoint types

• Resources
  • slamdata/matryoshka docs - Fixpoint Types

Fix

case class Fix[F[_]](unFix: F[Fix[F]])

• Implementations: Scalaz ekmett/recursion-schemes andyscott/droste

Mu

• Implementations: matryoshka, andyscott/droste, ekmett/recursion-schemes, purescript-fixed-points

Nu

• Implementations: Scala matryoshka, andyscott/droste, ekmett/recursion-schemes, purescript-fixed-points

Recursion schemas - Folds

Cathamorphism

• Implementations ekmett/recursion-schemes cata gcata

• Resources

  • (Haskell) Recursion Schemes: A Field Guide (Redux) - Edward Kmett: (blog post)
  • (Haskell) Catamorphisms Folding data structures - Edward Kmett: (blog post)
  • (Haskell) - Catamorphisms - Edward Kmett: (article)

Paramorphism

• Implementations ekmett/recursion-schemes para gpara

• Resources:

  • (Haskell) Recursion Schemes: A Field Guide (Redux) - Edward Kmett: (blog post)

Zygomorphism

• Implementations ekmett/recursion-schemes zygo gzygo

• Resources:

  • (Haskell) Recursion Schemes: A Field Guide (Redux) - Edward Kmett: (blog post)

Histomorphism

• Implementations ekmett/recursion-schemes histo ghisto

• Resources:

  • (Haskell) Recursion Schemes: A Field Guide (Redux) - Edward Kmett: (blog post)

Prepromorphism

• Implementations ekmett/recursion-schemes prepro gprepro

• Resources:

  • (Haskell) Recursion Schemes: A Field Guide (Redux) - Edward Kmett: (blog post)

Recursion schemas - Unfolds

Anamorphism

• Implementations ekmett/recursion-schemes ana gana

• Resources:

  • (Haskell) Recursion Schemes: A Field Guide (Redux) - Edward Kmett: (blog post)

Apomorphism

• Implementations ekmett/recursion-schemes apo gapo

• Resources:

  • (Haskell) Recursion Schemes: A Field Guide (Redux) - Edward Kmett: (blog post)

Futumorphism

• Implementations ekmett/recursion-schemes futu gfutu

• Resources:

  • (Haskell) Recursion Schemes: A Field Guide (Redux) - Edward Kmett: (blog post)

Postpromorphism

• Implementations ekmett/recursion-schemes postpro gpostpro

• Resources:

  • (Haskell) Recursion Schemes: A Field Guide (Redux) - Edward Kmett: (blog post)

Recursion schemas - Refolds

Hylomorphism

• Implementations ekmett/recursion-schemes hylo ghylo

• Resources:

  • (Haskell) Recursion Schemes: A Field Guide (Redux) - Edward Kmett: (blog post)
  • (Haskell) Generalized Hylomorphisms - Edward Kmett (blog post)
  • Stalking a Hylomorphism in the Wild - Bartosz Milewski (blog post)
  • Open Season on Hylomorphisms - Bartosz Milewski (blog post)

Chronomorphism

• Implementations ekmett/recursion-schemes chrono gchrono

• Resources:

  • (Haskell) Recursion Schemes: A Field Guide (Redux) - Edward Kmett: (blog post)
  • (Haskell) Time for Chronomorphisms - Edward Kmett (blog post)
  • (Haskell) Dynamorphisms as Chronomorphisms - Edward Kmett (blog post)
  • Histo- and Dynamorphisms Revisited- Ralf Hinze, Nicolas Wu

Synchromorphism

• Implementation Synchro

• Resources:

  • (Haskell) Recursion Schemes: A Field Guide (Redux) - Edward Kmett: (blog post)

Exomorphism

• Implementation Exo

• Resources:

  • (Haskell) Recursion Schemes: A Field Guide (Redux) - Edward Kmett: (blog post)

Metamorphism Erwig

• Implementation Erwig

• Resources:

  • (Haskell) Recursion Schemes: A Field Guide (Redux) - Edward Kmett: (blog post)

Metamorphism Gibbons

• Implementation Gibbons

• Resources:

  • (Haskell) Recursion Schemes: A Field Guide (Redux) - Edward Kmett: (blog post)

Dynamorphism

• Implementation Dyna

• Resources:

  • (Haskell) Recursion Schemes: A Field Guide (Redux) - Edward Kmett: (blog post)
  • (Haskell) Dynamorphisms as Chronomorphisms - Edward Kmett (blog post)
  • Histo- and Dynamorphisms Revisited- Ralf Hinze, Nicolas Wu

Elgot algebra

• Implementations ekmett/recursion-schemes elgot

• Resources:

  • (Haskell) Recursion Schemes: A Field Guide (Redux) - Edward Kmett: (blog post)
  • (Haskell) Elgot (Co)Algebras - Edward Kmett (blog post)

Elgot coalgebra

• Implementations ekmett/recursion-schemes coelgot

• Resources:

  • (Haskell) Recursion Schemes: A Field Guide (Redux) - Edward Kmett: (blog post)
  • (Haskell) Elgot (Co)Algebras - Edward Kmett (blog post)