What ARE anamorphisms
So I got sucked into editing the wikipedia page for anamorphisms, which was a mess: it didn't define the concept itself, except to say that it's a generalization of unfolds, and allude to category theory; it had duplicated code, but treated the duplicates as different, and was generally jargon-heavy and not very helpful.
But while fixing it, I got stuck on a puzzle: what exactly is an anamorphism?
Is an anamorphism a higher-order unfold operator? Or is it any function which is defined by partially applying such an operator? Or a function that is defined using a certain syntactic pattern, corresponding to an unfold operator? Or any function at all that could be so defined?
In the almighty "Programming with Bananas, Lenses, Envelopes and Barbed Wire," they seem to use "anamorphism" to refer to a function defined by a certain syntactic pattern. It's a question of interpretation, but they don't seem to define it as a higher-order function, exactly: the text posits some pre-existing operators and then the code sample, which takes just one argument (the "seed" value to unfold from), uses those posited operators.
It seems natural to me to use "anamorphism" to refer to the (unique) unfold operator for a given ADT, and likewise for "catamorphism" and fold. We still have the plural "anamorphisms," since we have many types with such operators. And, I'm not sure to what extent a function is intrinsically "an anamorphism" in Meijer, et al.'s sense. Of course, it is intrinsic whether a function can or cannot be defined that way; but when we start using the whole bag of bananas, lens, envelopes and barbed wire, I think we get multiple ways to define many functions, so it's less intrinsic.
I'd like to hear what others think: What are anamorphisms? Please comment!
Comments
Several comments:
1) First, you wrote:
Commendable effort! Thanks!2) You said:
I'm not sure what you mean by syntactic pattern. Can you explain?3) You referred to the almighty Bananas paper. It is almighty indeed, but the full(er) story appears in Meijer's and Fokkinga's "Program Calculation Properties of Continuous Algebras". In particular, they write about catamorphisms:
Thus, by "anamorphism", Meijer and friends mean any function that could be defined as [(?)], for some ?.
4) You said:
While it's hard to argue about naturality and intuition, I say that it doesn't seem natural to me. Even without looking at Meijer's original text, anamorphisms seemed to fit into the instance-of-the-recursion-scheme interpretation, rather than the polymorphic-higher-order-function one.
In particular, anamorphisms are special kind of (homo)morphisms, ones whose behaviour can be captured by some kind of recursion scheme. Compare with the other CoolGreekWord-morphism definitions in Category Theory (mono, epi, zero, etc.)
5) I'm uncertain as to what bothers you here:
Is it the fact that one might be able to define the same anamorphism as both [(?])] and [(?')] for different ?, ?'? If so, can you say what's so bad about that? There are other such ambiguous notions. The one of split monomorphism springs to mind first.
Ohad.
Posted by: Ohad | April 4, 2010 1:16 AM
*mutters about Unicode characters*
The question points stand for phi, psi. In particular, the perplexing "?'?" above should be read as "psi-prime?".
Ohad.
Posted by: Ohad | April 4, 2010 1:22 AM
Something useful is written in "A category theory primer" by Ralf Hinze, http://www.comlab.ox.ac.uk/ralf.hinze/SSGIP10/Notes.pdf (search for "anamorphism").
Posted by: Vag Vagoff | April 18, 2010 3:33 PM