archives

Catamorphisms and anamorphisms = general or primitive recursion?

By combining catamorphisms and anamorphisms, can one write only primitive recursive functions or any general recursive function? Do you know a good reference discussing that?

I was surprised by reading that "combining anamorphisms and catamorphisms [...] leads to general recursion" in an ICFP paper [1]. I would have expected to see "primitive recursion" there, and no reference is given for the statement.
Neel Krishnaswami states, on L-t-U forums [2], only that:
"Better still, a fold and an unfold composed together can describe any primitive recursive function."

I also skimmed again "Functional programming with bananas, lenses, envelopes and barbed wire", which builds only examples of primitive recursion - it does not go as far as Neel Krishnaswami.

[1] "Boxes Go Bananas: Encoding Higher-Order Abstract Syntax with Parametric Polymorphism", Geoffrey Washburn and Stephanie Weirich, ICFP 2003.
[2] http://lambda-the-ultimate.org/classic/message9257.html