Thu 11 Jun 2009
Recursion Schemes: A Field Guide (Redux)
Posted by Edward Kmett under Category Theory , Haskell , Mathematics[10] Comments
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.
June 11th, 2009 at 6:03 pm
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?
June 11th, 2009 at 6:18 pm
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/
June 11th, 2009 at 7:22 pm
I think you could make this even better by choosing one or maybe two concrete examples for each scheme, preferably examples that are likely to be familiar. Then write each example in two forms: one that uses your abstraction, and one that does not.
June 12th, 2009 at 9:27 am
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.
June 15th, 2009 at 9:14 pm
It may be worth directing the Elgot (co-)algebra entries to point to the post you mentioned above. Unless you intended to do more elaboration on them.
June 16th, 2009 at 2:39 pm
I had hoped to go through and do a nice writeup on each in turn, but you’re probably right.
June 17th, 2009 at 7:02 am
I’m really happy to see this back up! Thank you. :-)
June 17th, 2009 at 3:53 pm
The field guide returns! How wonderful! Thank you, Edward, as well as Jeff Cutsinger, for bringing it back from the dead. I will let my students know of its revival.
January 11th, 2010 at 11:35 am
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 ?
January 24th, 2010 at 1:33 pm
@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.