ハスケルでの怠惰と尾の再帰、なぜこのクラッシュですか？

Question

私はこれまでのところ、これまでに合計を保持するために2つのアキュムレータを使用して、大きなリストの要素の平均を計算するには、この非常に単純な機能を持っており、数：

今

mean = go 0 0 
    where 
     go s l []  = s/fromIntegral l 
     go s l (x:xs) = go (s+x) (l+1) xs 

main = do 
    putStrLn (show (mean [0..10000000])) 

、厳格な言語で、これは希望テール再帰的であり、問​​題はありません。しかし、ハスケルが怠惰であるため、私のグーグルでは、（s + x）と（l + 1）がサンクとして再帰を受け継いでいることを理解できました。したがって、この全部がクラッシュし、やけど：

Stack space overflow: current size 8388608 bytes. 

はさらにグーグルの後、私はseqと$!を発見しました。私はこの文脈でそれらを使用しようとする私のすべての試みが無限であることを証明し、無限のタイプについて何かを言っているので、理解できません。

は最後に、私は、再帰呼び出しを変更することにより、それをすべて解決した、-XBangPatternsが見つかりました：

go !s !l (x:xs) = go (s+x) (l+1) xs 

しかし-XBangPatternsが現在拡張であるように私は、これで満足していません。私は-XBangPatternsを使わずに評価を厳しくする方法を知りたいです。 （そしておそらく、あまりにも何かを学ぶ！）

あなたが理解の私の欠如を理解するだけので、ここでは（唯一のコンパイル、それがあることをしてみてください）私が試したものです：

go s l (x:xs) = go (seq s (s+x)) (seq l (l+1)) xs 

私が理解できるものから、seqはここではsとlの引数の評価を強制する必要があるため、サンクによって引き起こされる問題は回避されます。しかし、私はまだスタックオーバーフローを取得します。

Answer 1

私はこの上で広範囲に書いた：まず

• Real World Haskell, ch 24: controlling evaluation
• On recursion and strictness in Haskell

、あなたはアキュムレータの厳格な評価を必要とする場合は、[はい、seqを使用し、Haskellの98にとどまります：

mean = go 0 0 
    where 
    go s l []  = s/fromIntegral l 
    go s l (x:xs) = s `seq` l `seq` 
         go (s+x) (l+1) xs 

main = print $ mean [0..10000000] 

*Main> main 
5000000.0 

第二：あなたには、いくつかのタイプの注釈を与える場合は正格性解析がでキックし、-O2でコンパイルします。

mean :: [Double] -> Double 
mean = go 0 0 
where 
    go :: Double -> Int -> [Double] -> Double 
    go s l []  = s/fromIntegral l 
    go s l (x:xs) = go (s+x) (l+1) xs 

main = print $ mean [0..10000000] 

$ ghc -O2 --make A.hs 
[1 of 1] Compiling Main    (A.hs, A.o) 
Linking A ... 

$ time ./A 
5000000.0 
./A 0.46s user 0.01s system 99% cpu 0.470 total 

「をダブル」は上の最適化で、厳格な原子タイプダブル＃のラッパーであるため、正確なGHCは厳密性分析を実行し、厳密なバージョンは問題ないと推測します。

import Data.Array.Vector 

main = print (mean (enumFromToFracU 1 10000000)) 

data Pair = Pair !Int !Double 

mean :: UArr Double -> Double 
mean xs = s/fromIntegral n 
    where 
    Pair n s  = foldlU k (Pair 0 0) xs 
    k (Pair n s) x = Pair (n+1) (s+x) 

$ ghc -O2 --make A.hs -funbox-strict-fields 
[1 of 1] Compiling Main    (A.hs, A.o) 
Linking A ... 

$ time ./A 
5000000.5 
./A 0.03s user 0.00s system 96% cpu 0.038 total 

上記のRWHの章で説明したとおりです。

Answer 2

seq s (s+x)は、sの評価を強制することは間違いありません。しかし、それは強制的にs+xではないので、あなたはまだサンクを構築しています。

を使用すると、加算の評価を強制することができます（両方の引数について2回）。

mean = go 0 0 
where 
    go s l []  = s/fromIntegral l 
    go s l (x:xs) = ((go $! s+x) $! l+1) xs 

---

$!関数の使用は相当にgo $! (s+x)を翻訳する：これは、バングパターンを使用するのと同じ効果を得ることができる

let y = s+x 
in seq y (go y) 

したがってyが最初に押し込まれます弱い頭の通常形は、最も外側の関数が適用されることを意味します。 yの場合、最も外側の関数は+であり、yは、goに渡される前の数に完全に評価されます。

---

ああ、正しい場所にかっこがないので、おそらく無限のタイプのエラーメッセージが表示されます。

$!演算子は右結合であるため、かっこはありません。go $! (s+x) $! (l+1)は、同じ意味で、go $! ((s+x) $! (l+1))で、明らかに間違っています。

Answer 3

seq関数は、関数が呼び出されると、最初のパラメータの評価を強制します。 seq s (s+x)をパラメータとして渡した場合、seqファンクションはではなく、と即時に呼び出されます。そのパラメータの値を評価する必要はないためです。再帰呼び出しの前にseqへの呼び出しを評価して、そのパラメータを強制的に評価できるようにします。

go s l (x:xs) = s `seq` l `seq` go (s+x) (l+1) xs 

これはseq s (seq l (go (s+x) (l+1) xs))の構文上のバリエーションです：

は、通常、これは、このリンクを行われます。ここではseqへの呼び出しが式の一番外側の関数呼び出しです。ハスケルの怠惰のために、これは最初に評価されます。seqはまだ評価されていないパラメータsとseq l (go (s+x) (l+1) xs)で呼び出され、パラメータの評価は誰かが実際に値にアクセスしようとする時点まで延期されます。

ここでseqは、残りの式を返す前に最初のパラメータを評価するように強制できます。評価の次のステップは、第2のseqになります。 seqへの呼び出しが、あるパラメータのどこかに埋め込まれていると、それらの目的を破って、長時間実行されない可能性があります。

seqの位置が変更された場合、プログラムは過剰なメモリを使用せずに正常に動作します。

問題を解決するもう1つの方法は、プログラムをコンパイルするときにGHCで最適化を有効にすることです（-Oまたは-O2）。オプティマイザは、無駄な怠惰を認識し、不要なメモリを割り当てないコードを生成します。