[Haskell-cafe] foldl vs. foldr

Chaddaï Fouché chaddai.fouche at gmail.com
Tue Sep 18 16:26:05 CEST 2012

> 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 ->
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.

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://www.haskell.org/pipermail/haskell-cafe/attachments/20120918/15673ec4/attachment.htm>

More information about the Haskell-Cafe mailing list