Hi folks, I have two questions to tail recursion, optimisation(ghc) and the State monad. Sorry about bothering you with efficiency issues, but they become crusual to me since my programm needs more memory than I have :-( I compiled the following small examples with ghc -O6 -Wall -prof -auto-all -o test Test.hs (ghc 6.2.1) and ran them with ./test +RTS -K64M -sstderr
data Foo = Foo { foo :: !Integer , bar :: Double } deriving Show type Transformation a = a -> a
addX :: Integer -> Transformation Foo addX x f = f { foo = (foo f) + x } t1 :: Integer -> Transformation Foo t1 x = (addX x . addX (-x)) iterR :: [Integer] -> Transformation Foo iterR list f = foldr t1 f list iterL :: [Integer] -> Transformation Foo iterL list f = foldl (\ f' i -> t1 i f') f listiterR (take 100000 (repeat 1)) (Foo 0 0.0) 16,151,796 bytes copied during GC 11,546,120 bytes maximum residency (5 sample(s)) Productivity 20.3% of total user, 19.7% of total elapsed
iterL (take 100000 (repeat 1)) (Foo 0 0.0) 3,020 bytes copied during GC 25,904 bytes maximum residency (1 sample(s)) Productivity 100.0% of total user, 80.0% of total elapsed
Okay, foldl is tail recursive and foldr not. Fine! Now one weird thing: If I define t1 as:
t1' :: Integer -> Transformation Foo t1' x f = let newfoo = foldr addX f (take 10 $ repeat x) in newfoo {foo = foo f - foo newfoo}
iterR (take 100000 (repeat 1)) (Foo 0 0.0) 22,476 bytes copied during GC 2,113,876 bytes maximum residency (3 sample(s)) Productivity 60.0% of total user, 59.0% of total elapsed
Why is the compiler able to optimise the call of t1' and not the one of t1? My second question belongs to the State monad:
withFoo :: Foo -> State Foo (a) -> Foo withFoo state monad = execState monad state addXM :: Integer -> State Foo () addXM x = modify (\ f -> f { foo = (foo f) + x }) iterM :: [Integer] -> State Foo () iterM list = sequence_ $ map t1M list t1M :: Integer -> State Foo () t1M x = do addXM x addXM (-x)
withFoo (Foo 0 0.0) $ do iterM (take 100000 (repeat 1)) 48,989,348 bytes copied during GC 14,037,156 bytes maximum residency (7 sample(s)) Productivity 15.5% of total user, 14.7% of total elapsed
and if I define t1M as: t1M' :: Integer -> State Foo () t1M' x = do old <- get sequence_ $ map addXM (take 10 $ repeat x) modify (\ f -> f {foo = foo f - foo old}) then the memory consumption is awfully high:
withFoo (Foo 0 0.0) $ do iterM (take 100000 (repeat 1)) 172,468,996 bytes copied during GC 48,522,520 bytes maximum residency (10 sample(s)) Productivity 2.6% of total user, 2.5% of total elapsed
Is there a way to optimise the State monad version? Any help would be appreciated. Georg