GHC evaluation strategy

Question

I'm a little confused with how the following code executes when compiled with GHC 7.6.3

import qualified Data.Map as M

main = do let m1 = M.fromList $ zip [1..10000000] [1..]
          putStrLn $ "Value = " ++ (show $ M.map (+2) m1 M.! 555)

Compiled with ghc --make -O3, it gets me the following result:

$ /usr/bin/time ./MapLazy
Value = 557
29.88user 2.16system 0:32.12elapsed 99%CPU (0avgtext+0avgdata 2140348maxresident)k
0inputs+0outputs (0major+535227minor)pagefaults 0swaps

Yet, if I change it to just show $ m1 M.! 555, I get much lower memory usage, yet takes almost the same time:

$ /usr/bin/time ./MapLazy
555
23.82user 1.17system 0:25.06elapsed 99%CPU (0avgtext+0avgdata 1192100maxresident)k
0inputs+0outputs (0major+298165minor)pagefaults 0swaps

What's actually happening here? Does the entire Map get instantiated just because I read out a single value? Could I have prevented that somehow? I mean, it's a binary search tree, so I was expecting just the one path I looked up on the new map to be actually evaluated.

Answer 1

I think I got it. Let's look at the source for Data.Map.map.

map :: (a -> b) -> Map k a -> Map k b
map f m
  = mapWithKey (\_ x -> f x) m

mapWithKey :: (k -> a -> b) -> Map k a -> Map k b
mapWithKey _ Tip = Tip
mapWithKey f (Bin sx kx x l r) 
  = Bin sx kx (f kx x) (mapWithKey f l) (mapWithKey f r)

Now, mapWithKey seems to build just the top constructor of the tree and lazily recursing for the two branches... but:

data Map k a  = Tip 
              | Bin {-# UNPACK #-} !Size !k a !(Map k a) !(Map k a) 

Above we see that the subtrees are strict fields! So the recursive calls to mapWithKey will be forced, causing the full tree to be updated strictly instead of lazily.