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? Regards, ----------------- Serge Mechveliani mechvel@botik.ru
On 10/15/06, Serge D. Mechveliani
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
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
Hello Serge, Sunday, October 15, 2006, 6:05:43 PM, you wrote: if i correctly understood your problem, ultimate solution is the fusion RULES for foldl that is planned for 6.8 (there is yicket about this). may be YOU can develop such rules? :) -- Best regards, Bulat mailto:Bulat.Ziganshin@gmail.com
participants (4)
-
Bulat Ziganshin -
Duncan Coutts -
Lemmih -
Serge D. Mechveliani