foldl laziness support

Serge D. Mechveliani mechvel at
Sun Oct 15 10:05:43 EDT 2006

Dear Haskell implementors,

I keep on facing a frightening problem of the laziness support.
Consider the example of

import List (union)

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

unionMany = foldl union []

Compiling it in   ghc-6.6,  -O, 

we have the running cost  O(n),  instead of  O(1).

Now, changing to 

  unionMany []        =  []
  unionMany (xs: xss) =  union xs (unionMany xss)
we reach  O(1).
For example, for  n = 10^9,  the time remains less than   0.01 sec.

My program has many fragments of such kind, when a function produces
a long list, some client functions need all the list, and others need
only its small initial part.
When we rely on the standard library,  foldl  creeps in everywhere.
Also may things are easy to program via  foldl.

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


Serge Mechveliani
mechvel at

More information about the Glasgow-haskell-users mailing list