Jan Stolarek | 18 Sep 14:32 2012
Picon

foldl vs. foldr

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.

Greets,
Janek
Miguel Mitrofanov | 18 Sep 15:35 2012
Picon

Re: foldl vs. foldr

Hi Jan!

foldl always traverses the list to the end; in particular, if there is no end, it would hang forever (unless
the compiler is smart enough to detect an infinite loop, in which case it can throw an error). On the other
hand, if the first argument is lazy enough, foldr would stop before processing the complete list. So, for example

foldr (\_ _ -> ()) () [1..]

would give an answer, while

foldl (\_ _ -> ()) () [1..]

would hang.

In particular, you can reimplement foldl in terms of foldr, like that:

foldl op i ls = foldr (flip op) i (reverse ls)

but if you attempt to do the same with foldr:

foldr op i ls = foldl (flip op) i (reverse ls)

you would end up with a function which is more strict than the real foldr.

18.09.2012, 16:32, "Jan Stolarek" <jan.stolarek <at> p.lodz.pl>:
> 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
(Continue reading)

Chaddaï Fouché | 18 Sep 16:26 2012
Picon

Re: foldl vs. foldr

18.09.2012, 16:32, "Jan Stolarek" <jan.stolarek <at> p.lodz.pl>:
> 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?

Basically the difference is that foldr is really the natural catamorphism for the list type, that is for a type like :

data MyType = Zero | One A | Two B C | Recurse MyType

the natural catamorphism is a function that takes four arguments by which it will replace the four constructor so as to deconstruct a value of MyType :

myTypeCata :: r -> (A -> r) -> (B -> C -> r) -> (r -> r)   ->    (MyType -> r)
myTypeCata z o t re Zero = z
myTypeCata z o t re (One a) = o a
myTypeCata z o t re (Two b c) = t b c
myTypeCata z o t re (Recurse myType) = re (myTypeCata z o t re myType)

So foldr is the natural catamorphism for the list type and foldl is not.

--
Jedaï
_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe <at> haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
wren ng thornton | 20 Sep 01:32 2012

Re: foldl vs. foldr

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

Gmane