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.
Discussion
I can’t see the difference between an Elgot algebra and an Elgot coalgebra in the table. Is this a typo or simply my misunderstanding?
construction vs. deconstruction
In one the near-algebra knows about the carrier of the coalgebra.
In the other the near-coalgebra knows about the carrier of the algebra.
See http://comonad.com/reader/2008/elgot-coalgebras/
I agree. At the time I first wrote this the plan was to go through and flesh each of these out in turn.
As you can see from the catamorphism link there is a lot of substance to fleshing out each one in terms of applicable laws, examples, etc.
I was able to recover the text of the paramorphism entry as well, so I’ll repost that some time soon (as soon as I get around to reformatting all the LaTeX in it) and see about proceeding from there.
Thanks for this (co-)recursion schemes guide.
I have toyed with the Charity language hence some basic schemes (catamorphism,paramorphism,anamorphism) are already familiar to me.
Plus histomorphism/futumorphism are well documented by Varmo Vene.
Others are not so well documented and quite difficult to grasp for mere mortal fonctional programmers like me.
One corecursion scheme that i face again and again is exploration. I mean i have an arithmetic expression type and i want to solve some “le compte est bon” problem. Or i have this move type (front|back|left|right|up|down) list, and i want to solve my Rubik’s cube. What corecursion scheme is that ?
@Damien:
Regarding “le compte est bon” you can implement that fairly directly as a hylomorphism. You need an algebra for an anamorphism that generates a list of all trees, and a coalgebra for a catamorphism that searches the list for the answers.
With more thought there is probably some kind of dynamorphic variation that evaluations the subtrees, figures out their valuation, and then proceeds as above, saving some effort in computing valuations of the subtrees in the catamorphism. For that matter, there is the code elsewhere on this blog for incremental folds which might be an easier way to integrate that incremental result.
The Rubik’s cube is probably most easily solved in the same manner. The choice of catamorphism will determine if you search breadth-first, depth-first, or using some other strategy.