In particular, will the compiler be able to avoid allocating when
building up that large monadic computation in the foldrWithKey?
Since it is a foldr, the first action can be run without knowing the following ones. That is, at no time all actions must be allocated.
Hi all, Well, to test it out I went ahead and made a patch to containers, here: https://github.com/rrnewton/containers/commit/9b1a913c923fd9409932434894cca2... Henning, while I agree with you that GHC shouldn't truly *need* to generate a first class representation of that 10M-step monadic action... it remains the case that the updated test (attached to the end of this email), shows the traverseWithKey_ version allocating only 200K, whereas the foldrWithKey allocates 32M. Further, I argue that the traverseWithKey_ version is clearer to programmers that don't yet grok the first class nature of monadic actions (e.g. a fold to build up one big monadic action). And again, if we are not sure of the performance implications of that in this thread, I imagine many Haskell programmers would not be. So unless there's a strong counterargument, I propose the above patch for acceptance. -Ryan P.S. Using the HEAD version of cabal the allocation for -O0 foldrWithKey actually went up from 200M to 300M. Appendix: updated code below and at this URL: https://gist.github.com/rrnewton/5912513#file-maptest-hs -------------------------------------------- *import Control.DeepSeq* *import GHC.Stats* *import qualified Data.Map.Strict as M* *import Data.Time.Clock* *import Control.Exception* *import System.Mem* * * *main :: IO ()* *main = do* * t0 <- getCurrentTime* * let m0 = M.fromList (map (\i -> (i,i)) [1..1000000::Int])* * evaluate$ rnf m0 * * t1 <- getCurrentTime* * performGC* * s1 <- getGCStats * * putStrLn$"Constructed map in "++show (diffUTCTime t1 t0)++"\n "++ show s1++"\n"* * let fn 500000 v = putStrLn "Got it!"* * fn _ _ = return ()* * * * -- Regular traverseWithKey uses 48MB* * -- traverseWithKey_ usse 200K of allocation:* * M.traverseWithKey_ fn m0* * t2 <- getCurrentTime* * performGC* * s2 <- getGCStats * * putStrLn$"[traverseWithKey_] Consumed map in "++show (diffUTCTime t2 t1)++"\n "++ show s2++"\n"* * putStrLn$"Bytes allocated during consume: "++show (bytesAllocated s2 - bytesAllocated s1)* * * * -- foldrWithKey uses 32MB allocation:* * M.foldrWithKey (\k a -> (fn k a >>)) (return ()) m0* * t3 <- getCurrentTime* * performGC* * s3 <- getGCStats * * putStrLn$"[foldrWithKey] Consumed map in "++show (diffUTCTime t3 t2)++"\n "++ show s3++"\n"* * putStrLn$"Bytes allocated during consume: "++show (bytesAllocated s3 - bytesAllocated s2)* * return ()* * *