Control.DeepSeqを使って正格評価(訂正版)

Haskell

何が酷いって、記事を見なおしてみたらfoldrとfoldlのロジックを間違えてる。コレは死ねる。。。ただ、Bangについてはそれでもちょっと怪しいので訂正版の記事を作り直したいと思います。

古い記事 は自戒の意味も込めて残しておきます。(なんの意味があるのかは不明)

モンテカルロ法で円周率を計算するために多数のIOから取り出した結果の集計を行おうとした。

しかし未評価thunkによるメモリオーバーフローが発生し、インスタンス数を増やせなかった。途中でわざとprintを行なって未評価thunkを潰してメモリリークを防いでいたのだがもちろんこれは本質的な解決ではない。

また、Bang-Patternを使用して未評価thunkを潰そうとしたが、どうもthunkが潰れてくれない。

調べてみたところ、厳密な正格評価にはControl.DeepSeqが使用できることがわかったので試して見ることにした。

 

まず、リークを起こすコードの説明から。

main :: IO ()
main = do
    (count,total)  Int -> IO Stat
takeStat func count =
    foldLN1 sum_stat (liftM point_to_stat func) count (0,0)

foldLN1 :: (a->b->a) -> IO b -> Int -> a -> IO a
foldLN1 folder m count init =
    let foldLN_sub folder m count v = if count == 0
        then v
        else let v' = unsafePerformIO m
              in foldLN_sub folder m (count -1) $! folder v v'
    in return $ foldLN_sub folder m count init

だいぶ端折っているが、foldLN1という関数で$!の形でBang-Patternを使用している。にもかかわらず、実行するとメモリオーバーフローで落ちる。(どうやら、folder関数のthunkが潰れ切らないらしい) そこで、DeepSeqを使用したコードに修正する。

foldLN1 :: (NFData a) => (a->b->a) -> IO b -> Int -> a -> IO a
foldLN1 folder m count init =
    let foldLN_sub folder m count v = if count == 0
        then v
        else let v' = unsafePerformIO m
              in foldLN_sub folder m (count -1) $!! folder v v'
    in return $ foldLN_sub folder m count init

NFDataクラスはDeepSeqモジュールの正格評価を適用できるデータのクラス。$!!はBang-Patternsにおける$!に相当する。引数を(Bang PatternsにおけるWHNFではなく、)値になるまで評価する。

そもそも、unsafePerformIO使っているし、foldを自分で書くクソダサさと、無茶しまくっている、、、 でも、確かにコレで落ちない。

ちなみに、DeepSeqを使用しなくても下記のように時々thunkを潰すような処理を入れてあげると上手く回る。

foldLN2 :: (Show a) =>(a->b->a) -> IO b -> Int -> a -> IO a
foldLN2 folder m count init =
    let foldLN_sub folder m count v = if count == 0
        then v
        else let v' = unsafePerformIO $ do
                 when (count `mod` 100000 == 0) $ print_stat v count
                 m
              in foldLN_sub folder m (count -1) $! folder v v'
    in return $ foldLN_sub folder m count init

コード： Recursion2.hs

参考：

【まとめ】Haskellでの正格評価とWHNF
http://kamonama.blogspot.jp/2011/04/haskellwhnf.html
shelarcyさんの説明
http://www.sampou.org/cgi-bin/haskell.cgi?shelarcy

補足：

$ ghc --version
The Glorious Glasgow Haskell Compilation System, version 7.4.1
$ ghc -O Recursion.hs
[1 of 1] Compiling Main             ( Recursion.hs, Recursion.o )
Linking Recursion.exe ...