foldl laziness support

Lemmih lemmih at gmail.com
Sun Oct 15 10:16:39 EDT 2006


On 10/15/06, Serge D. Mechveliani <mechvel at botik.ru> wrote:
> 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
>        in
>        putStr
>        (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?

How about using 'foldr'?

-- 
Cheers,
  Lemmih


More information about the Glasgow-haskell-users mailing list