[Haskell-cafe] foldl vs. foldr

[Chaddaï Fouché]

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