About a year back I posted a field guide of recursion schemes on this blog and then lost it a few months later when I lost a couple of months of blog entries to a crash. I recently recovered the table of recursion schemes from the original post thanks to Google Reader's long memory and the help of Jeff Cutsinger.
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.
| 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 applying a natural transformation |
| 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 with a natural transformation |
| 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 bialgebraga |
| 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.