Concerning the laziness support problem, I thank people for explanations about foldl and foldr.
I wonder how to avoid these numerous cost pitfalls. Maybe, the complier could do more optimization?
Duncan Coutts <duncan.coutts@worc.ox.ac.uk> writes
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 automatically.
In my experience, the choice is almost always between foldl' and foldr.
[..]
I do not see foldl' in the standard library. Is it of the GHC lib extension? has it strictness annotation?
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 []
I see. Thank you. I have impression that something is here besides the intuition for the foldl/foldr choice. Here is a contrived example which is more close to my real situation. ----------------------------------------------------------------- import qualified Data.Set as Set (Set(..), empty, member, insert) import List (union, find) main = let n = 10^6 :: Int in putStr (shows (g1 n) "\n") f :: Int -> (Set.Set Int, [Int]) f n = -- original version, I write so because it is easy to program -- foldl add (Set.empty, []) [[1 .. i] | i <- [1 .. n]] where add (s, xs) ys = (Set.insert (sum xs) s, union xs ys) {- attempt to optimize (fails) -- h (Set.empty, []) [[1 .. i] | i <- [1 .. n]] where h (s, xs) [] = (s, xs) h (s, xs) (ys: yss) = h (Set.insert (sum xs) s, union xs ys) yss -} g1, g2 :: Int -> Bool -- client functions g1 n = case snd $ f n of x: _ -> even x _ -> False g2 n = let (set, xs) = f n in case find (> 100) xs of Just x -> Set.member (2*x) set _ -> False ----------------------------------------------------------------- Evidently, g1 n must have the cost of O(1). But in ghc-6.6 -O, it has O(n). How to improve f ? I tried foldr, and failed. The situation is so that some clients are as g1, and others are as g2, and, at least, g1 must be O(1). Regards, ----------------- Serge Mechveliani mechvel@botik.ru