DeepSeq
問題
f_leak :: Int -> [Int] -> [Int] f_leak 0 xs = xs f_leak n xs = f_leak (n - 1) $! take 2 (xs ++ xs) -- f_good = ?
Main> f_leak 100000 [0,1] ERROR - Garbage collection fails to reclaim sufficient space Main> f_good 100000 [0,1] [0,1]
説明
未評価の式が大きくなってメモリを圧迫することがある(memory leak*1 )。そんなときに活躍するのがseq($!)である。
ところがseqの性質は
seq _|_ b = _|_ seq a b = b, if a /= _|_
だけである*2から、
data D a = D a seq (D undefined) /= _|_
となり、D xのxは評価されない。したがって上のfの場合でも
take 2 (xs ++ xs) -> (head_of_xs):(take (2 - 1) (tail_of_xs ++ xs))
となり、これが積み重なってメモリリークすることになる。
データの中身を奥まで全部評価するのがDeepSeq*3モジュールの役割りである。
例
import DeepSeq f_good :: Int -> [Int] -> [Int] f_good 0 xs = xs f_good n xs = f_good (n - 1) $!! take 2 (xs ++ xs) data Tree a = Tree a [Tree a] | E instance DeepSeq a => DeepSeq (Tree a) where deepSeq E y = y deepSeq (Tree a cs) y = deepSeq a $ deepSeq cs y data ToBeLazy a = ToBeLazy a instance DeepSeq (ToBeLazy a) where deepSeq _ y = y
標準的なDeepSeqモジュールの中ではこのような定義がある
($!!) :: (DeepSeq a) => (a -> b) -> a -> b f $!! x = x `deepSeq` f x <snip> class DeepSeq a where deepSeq :: a -> b -> b deepSeq = seq <snip> instance (DeepSeq a) => DeepSeq [a] where deepSeq [] y = y deepSeq (x:xs) y = deepSeq x $ deepSeq xs y <snip> instance DeepSeq Int where
注意
- コンテクストとしてDeepSeq aが指定されているために、リストの中身がまた(サブ)リストやツリーであるような場合でもそのサブリスト等の中身まで再帰的にすべて評価できる。
- 大きなデータ構造に何度も適用すると中身を辿るのに時間がかかって遅くなることがある。