[Haskell-cafe] Lists concatenation being O(n)

Daniel Fischer daniel.is.fischer at googlemail.com
Fri Oct 14 18:00:07 CEST 2011


On Friday 14 October 2011, 17:10:00, Yves Parès wrote:
> Wow, I don't get core haskell, but I get you point.
> It's indeed odd foldl' doesn't use foldr (and sum doesn't use foldl'
> instead of foldl as (+) is strict (*)) if foldr permits loop fusion.

No, it's not odd. The fusion technology isn't yet capable of handling 
everything you throw at it, and you get catastrophically bad results if it 
fails.
With the current implementation, you pay a (significant) price at the 
points where fusion would succeed but have good enough worst-case 
behaviour.

> 
> (*) Anyway, is there a place where foldl is preferable over foldl' ?
> Never happened to me, I always use right-folding if I want lazy
> evaluation, to benefit from guarded recursion.

Bas quoted and linked the Foldr Foldl Foldl' page and referred to the 
example. As the author of that example, I know that it is an artificial 
example; I thought it up to answer the question "when would foldl be better 
than foldl'?". I have never come across such a situation in real life.



More information about the Haskell-Cafe mailing list