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 [EMAIL PROTECTED] 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])
fn =
-- 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
[EMAIL PROTECTED]
___
Glasgow-haskell-users mailing list
Glasgow-haskell-users@haskell.org
http://www.haskell.org/mailman/listinfo/glasgow-haskell-users
