### Re: foldl vs. foldr

wren ng thornton <wren <at> freegeek.org>

2012-09-19 23:32:25 GMT

On 9/18/12 8:32 AM, Jan Stolarek wrote:
> Hi list,
>
> I have yet another question about folds. Reading here and there I encountered statements that
> foldr is more important than foldl, e.g. in this post on the list:
> http://www.haskell.org/pipermail/haskell-cafe/2012-May/101338.html
> I want to know are such statements correct and, if so, why? I am aware that foldl' can in some
> circumstances operate in constant space, while foldr can operate on infinite lists if the folding
> function is lazy in the second parameter. Is there more to this subject? Properties that I
> mentioned are more of technical nature, not theoretical ones. Are there any significant
> theoretical advantages of foldr? I read Bird's and Wadler's "Introduction to functional
> programming" and it seems to me that foldl and foldr have the same properties and in many cases
> are interchangeable.
The interchangeability typically arises from the (weak) isomorphism between:
data CList a = CNil | Cons a (CList a)
data SList a = SNil | Snoc (SList a) a
In particular, interchangeability will fail whenever the isomorphism
fails--- namely, for infinite lists.
However, there is another issue at stake. The right fold is the natural
catamorphism for CList, and we like catamorphisms because they capture
the definability class of primitive recursive functions[1]. However,
catamorphisms inherently capture a bottom-up style of recursion (even
though they are evaluated top-down in a lazy language). There are times
when we'd rather capture a top-down style of recursion--- which is
exactly what left folds do[2]. Unfortunately, left folds have not been
studied as extensively as right folds. So it's not entirely clear what
their theoretical basis is, or how exactly their power relates to right
folds.
[1] That is, every primitive recursive ***function*** can be defined with a
catamorphism. However, do note that this may not be the most efficient
***algorithm*** for that function. Paramorphisms thus capture the class
better, since they can capture more efficient algorithms than
catamorphisms can. If you're familiar with the distinction between
"iterators" (cata) and "recursors" (para), this is exactly the same thing.
[2] Just as paramorphisms capture algorithms that catamorphisms can't,
left folds capture algorithms that right folds can't; e.g., some
constant stack/space algorithms. Though, unlike cata vs para, left folds
do not appear to be strictly more powerful. Right folds can capture
algorithms that left folds (apparently) can't; e.g., folds over infinite
structures. I say "apparently" because once you add scanl/r to the
discussion instead of just foldl/r, things get a lot murkier.
--
--
Live well,
~wren