Recursion schemes for dummies?

Extremely loosely speaking, a catamorphism is just a slight generalization of fold, and an anamorphism is a slight generalization of unfold. (And a hylomorphism is just an unfold followed by a fold.). They’re presented in a more rigorous form usually, to make the connection to category theory clearer. The denser form lets us distinguish data (the necessarily finite product of an initial algebra) and codata (the possibly infinite product of a final coalgebra). This distinction lets us guarantee that a fold is never called on an infinite list. The other reason for the funny way that catamorphisms and anamorphisms are generally written is that by operating over F-algebras and F-coalgebras (generated from functors) we can write them once and for all, rather than once over a list, once over a binary tree, etc. This in turn helps make clear exactly why they’re all the same thing.

But from a pure intuition standpoint, you can think of cata and ana as reducing and producing, and that’s about it.

Edit: a bit more

A metamorphism (Gibbons) is like an inside-out hylo — its a fold followed by an unfold. So you can use it to tear down a stream and build up a new one with a potentially different structure.

Ekmett posted a nice “field guide” to the various schemes in the literature: http://comonad.com/reader/2009/recursion-schemes/

However, while the “intuitive” explanations are straightforward, the linked code is less so, and the blog posts on some of these might be a tad on the complex/forbidding side.

That said, except perhaps for histomorphisms I don’t think the rest of the zoo is necessarily something you’d want to think with directly most of the time. If you “get” hylo and meta, you can express nearly anything in terms of them alone. Typically the other morphisms are more restrictive, not less (but therefore give you more properties “for free”).

Leave a Comment

Hata!: SQLSTATE[HY000] [1045] Access denied for user 'divattrend_liink'@'localhost' (using password: YES)