foldl laziness support

[Duncan Coutts]

On Sun, 2006-10-15 at 18:05 +0400, Serge D. Mechveliani wrote:
> Dear Haskell implementors,
> 
> I keep on facing a frightening problem of the laziness support.

[snip]

> I wonder how to avoid these numerous cost pitfalls.
> Maybe, the complier could do more optimization?

There are important differences between foldl, foldl' and foldr. It is
quite important to choose the right one. I don't think this can be done
automagically.

In my experience, the choice is almost always between foldl' and foldr.
For lists, foldl is rarely useful (for arrays on the other hand both
foldl and foldr' are useful).

The usual rule of thumb is that if you are constructing some small
atomic value (e.g. an integer) then foldl' is the right choice. If
you're building a value that is naturally constructed and consumed
lazily (e.g. a list) then foldr is the right choice.

So as Lemmih says, in this case you want to use foldr:

-----------------------------------
import List (union)
main = let n = 10^4 :: Int
       in
       putStr
       (shows (take 2 $ unionMany [[1 .. i] | i <- [1 .. n]]) "\n")

unionMany = foldr union []
-----------------------------------

So this is just as easy to write as the foldl(') version.

As I said, I think it'd be hard to figure out automatically when it is
desirable and safe to switch (foldl f unit) to/from (foldr (flip f)
unit). Though, perhaps it'd be possible for some analysis tool to
provide a hint to the programmer based on the strictness of the function
we are folding and the strictness in the structure of the type we are
building. If it could be done reasonably reliably then it might be
useful to help programmers to choose appropriately and avoid performance
problems.

Duncan