Re: [Haskell-cafe] 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

18.09.2012, 16:32, "Jan Stolarek" : 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ï