haskell - GHC评估策略

Question

我对使用 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)

使用 ghc --make -O3 编译，它让我得到以下结果:

$ /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

但是，如果我将其更改为 show $ m1 M.! 555 ，我的内存使用量要低得多，但几乎需要同样的时间:

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

这里到底发生了什么？整个 Map 是否因为我读出了一个值而被实例化？我能以某种方式阻止这种情况吗？我的意思是，它是一棵二叉搜索树，所以我期望我在新 map 上查找的一条路径会被实际评估。

Answer 1

我想我明白了。让我们看看 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)

现在， mapWithKey似乎只构建树的顶部构造函数并懒惰地递归两个分支......但是:

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

上面我们看到子树是严格字段!所以递归调用 mapWithKey将被强制，导致整个树被严格更新而不是延迟更新。