### 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!

1) First, you wrote:

So I got sucked into editing the wikipedia page for anamorphisms, which was a mess:
Commendable effort! Thanks!

2) You said:

Or a function that is defined using a certain syntactic pattern, corresponding to an unfold operator?
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:

([?]) is called an F-catamorphism (???? meaning ‘downwards’) since, interpreted as a computing agent, ([?]) descends along the structure of the argument (systematically replacing each "in" by ?.

Thus, by "anamorphism", Meijer and friends mean any function that could be defined as [(?)], for some ?.

4) You said:

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.

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:

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.

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.