36400


円周率を近似するコードです。

[code]

    main :: IO ()
    main = do
        let points = [(x,y) | x<-range 10000, y<-range 10000]
        let all = length $ points
        let hit = length $ filter ((<= 1) . distance) points
        putStrLn $ show $ (fromIntegral hit * 4) / (fromIntegral all)
        where
            range n = (map (/ n) [0 .. n])
            distance (a,b) = sqrt(a*a+b*b)
    
[/code]

このコードを実行するとメモリが大量に消費され、システムが停止します。何か問題があるようです。

しかし、hit だけを評価、あるいは all だけを評価すると、このコードは動作します。

[code]

    main :: IO ()
    main = do
        let points = [(x,y) | x<-range 10000, y<-range 10000]
        let all = length $ points
        let hit = length $ filter ((<= 1) . distance) points
        putStrLn $ show hit
        --putStrLn $ show all -- このコメントアウトを外して hit と all 両方を表示しようとするとスペースリークが発生する
        where
            range n = (map (/ n) [0 .. n])
            distance (a,b) = sqrt(a*a+b*b)
    
[/code]

これは何が起きているのでしょうか？


CC BY-SA 3.0
2017-07-15T17:13:45.270
36399
2017-07-17T23:16:43.153
2017-07-17T23:16:43.153
3054
10773
question
haskell
内包表記で生成したリストを2回使うと、スペースリークでシステムが停止してしまう


`points`を2回使っていることが原因でスペースリークが起こっています。

2つ目のコードを使って説明します。

Haskellは遅延評価をする言語なので

> `let points = [(x,y) | x<-range 10000, y<-range 10000]`

の段階ではリストの長さに応じたメモリが確保されることはありません。実際に`points`の内容が計算されるのは、それが「必要」になった時です。

例えば`putStrLn`により`IO`アクションが発生する時がそれにあたります。

> `putStrLn $ show hit`

が実行されると`points`リストは先頭から末尾までスキャンされます。

そして、その計算結果は後に

> `putStrLn $ show all`

で使うためにメモリ上に保持されます。この時、リストの長さに比例するメモリを消費するわけですが、これがあなたの環境でスペースリークを引き起こす程の大きさなのでしょう。

一方で`points`が二度と使われないならば、Haskellは先ほど計算した結果を捨てることが出来ます。従ってスペースリークも起こりません。

以上説明したことは`points`と等しい2つのリストを使って、`all`と`hit`を定義することで検証できます。

[code]

    let points1 = [(x,y) | x<-range 10000, y<-range 10000]
    let points2 = [(x,y) | x<-range 10000, y<-range 10000]
    let all = length $ points1
    let hit = length $ filter ((<= 1) . distance) points2
    
[/code]


CC BY-SA 3.0
2017-07-15T18:33:33.963
36400
2017-07-15T18:33:33.963
13199
36399
answer


メモリを大量に消費してしまう原因はletrecさんの回答の通りです。

今回のケースのように、1個のリストから2つの値をたたみ込んで求めたい場合、  
ちょっと工夫しなければ、2回リストを走査（この場合、allとhitを求める処理）することになってしまい、結果2回目の走査のために、大きなリストを保持しなければならなくなります。  
その工夫を楽にするために[foldl](https://github.com/Gabriel439/Haskell-Foldl-
Library)というライブラリーがありますので、おすすめです。

foldlを使った場合、下記のように書き換えられ、メモリ消費量も抑えられます。

[code]

    import qualified Control.Foldl as L
    
    main :: IO ()
    main = do
        let points = [(x,y) | x <- range 10000, y <- range 10000]
        let all = L.length
        let hit = L.handles (L.filtered ((<= 1) . distance)) L.length
        let pi h a = fromIntegral h * 4 / fromIntegral a
        print $ L.fold (pi <$> hit <*> all) points
        where
            range n = map (/ n) [0 .. n]
            distance (a,b) = sqrt(a*a+b*b)
    
[/code]

Applicativeスタイルを使っているため、ちょっと慣れないと読みにくいかもしれませんが、参考までに。


CC BY-SA 3.0
2017-07-16T02:09:43.640
36406
2017-07-16T02:09:43.640
8007
36399
answer