I talk an awful lot about different recursion schemes in this blog.

What I want to do for the next few posts is taxonomize a list of the general recursion schemes I have seen, cite the original references for them where available, and provide a concise implementation of each and try to motivate the connections between them. I'll likely go back through and add more information or post motivating examples for each as I work.

The following recursion schemes can be found in category-extras, along with variations on the underlying themes, so this should work as a punch-list. I'll update this post with links as I go.

Folds
Scheme Code Description
catamorphism† Cata tears down a structure level by level
paramorphism*† Para tears down a structure with primitive recursion
zygomorphism*† Zygo tears down a structure with the aid of a helper function
histomorphism† Histo tears down a structure with the aid of the previous answers it has given.
prepromorphism*† Prepro tears down a structure after repeatedly transforming it
Unfolds
Scheme Code Description
anamorphism† Ana builds up a structure level by level
apomorphism*† Apo builds up a structure opting to return a single level or an entire branch at each point
futumorphism† Futu builds up a structure multiple levels at a time
postpromorphism*† Postpro builds up a structure and repeatedly transforms it
Refolds
Scheme Code Description
hylomorphism† Hylo builds up and tears down a virtual structure
chronomorphism† Chrono builds up a virtual structure with a futumorphism and tears it down with a histomorphism
synchromorphism Synchro a high level transformation between data structures using a third data structure to queue intermediate results
exomorphism Exo a high level transformation between data structures from a trialgebra to a bialgebra
metamorphism Erwig a hylomorphism expressed in terms of bialgebras
metamorphism Gibbons A fold followed by an unfold; change of representation
dynamorphism† Dyna builds up a virtual structure with an anamorphism and tears it down with a histomorphism
Elgot algebra Elgot builds up a structure and tears it down but may shortcircuit the process during construction
Elgot coalgebra Elgot builds up a structure and tears it down but may shortcircuit the process during deconstruction

* This gives rise to a family of related recursion schemes, modeled in category-extras with distributive law combinators.
† The scheme can be generalized to accept one or more F-distributive (co)monads.

Haskell preliminaries

We'll need a few preliminary types.

First, we need to be able to take the fixed point of a functor. Since the least and greatest fixpoints of a functor coincide in Haskell, we just call this 'Fix' rather than Mu or Nu. 

 
data FixF f = InF { outF :: f (FixF f) }
 

Second, we'll need to define F-algebras and F-coalgebras.

 
type Algebra f a = f a -> a
type Coalgebra f a = a -> f a
 

Finally, we need a slight generalization of these. For a comonad W, an F-W-Algebra takes the form:

 
type GAlgebra f w a = f (w a) -> a
 

And similarly for a monad M, an F-M-coalgebra has the form:

 
type GCoalgebra f m a = a -> f (m a)
 

The intended use of GAlgebra and GCoalgebra is that you use them with F-distributive comonads and monads respectively in the sense of Uustalu, Vene and Pardo [1].

We can obtain all of these by importing from category-extras.

 
import Control.Functor.Fix
import Control.Functor.Algebra
 

References

[1] T. Uustalu, V. Vene, A. Pardo. Recursion Schemes from Comonads. Nordic Journal of Computing 8(2001), 366-390.