[Haskell-cafe] Lists concatenation being O(n)
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
With the current implementation, you pay a (significant) price at the
points where fusion would succeed but have good enough worst-case
> (*) 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