Koen wrote,
> I think Lambert Meertens calls this a "paramorphism".
> It is basically a catamorphism (fold), where you also
> have access to the structure you are recursing on, not
> just the result after recursion.
>
> But since the FP culture changed from:
>
> catamorphism ==> fold
> anamorphism ==> unfold
>
> I think
>
> paramorphism ==> recurse
>
> is just as well :-)
>
> I think it is also somewhere in Erik Meijer's thesis,
> but I don't have it here, so I don't know. (But maybe
> he doesn't want to be reminded of his banana period
> anymore :-)
That's correct (twice :-). It is a really nice subject, but I have move on to other
hunting grounds.
If you look at the bananas paper (http://www.cs.uu.nl/~erik/Research/Body.html) that
was refered to by Lazlo earlier in this thread, you find the following definition for
the "barbed wire" paramorphism h = [<b,plus>] over lists
h [] = b
h (a:as) = a `plus` (as, h as)
and later this is generalized for arbitrary recursive types.
Lennart's proposes recurse operator is indeed a special case of a paramorphism over
list-like datatypes. I think however, that the type should constrain c over Functor
(long live fmap :-)
recurse :: Functor c => (a -> c a -> b -> b) -> b -> c a -> b
Zipping lists however is *much* easier expressed using anamorphisms or unfold. The
reason is that when zipping two lists you are co-inductively *constructing* a list,
and not so much inductively destructing a list. Hence the trick of inductively
destructing a list that returns a function that inductively destructs the second list
and build the resulting list of pairs.
I would like to point everybody that is interested in this corner of FP to Graham
Hutton (http://www.cs.nott.ac.uk/~gmh/) and Jeremy Gibbons
(http://www.brookes.ac.uk/~p0071749/home.html) who are still active in this area and
have written a number of really nice papers on folds, unfolds and friends. Richard
Bird and Ross Paterson have some nice papers of doing folds etc on nested datatypes.
Have fun!
Erik
BTW
there is an interesting correspondence between COM's composite monikers and monadic
parsers.
