18

これまでの合計とこれまでのカウントを保持するために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]))

さて、厳密な言語では、これは末尾再帰であり、問​​題はありません。しかし、Haskellは怠惰なので、私のグーグルは、（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の引数の評価を強制し、サンクによって引き起こされる問題を回避する必要があります。しかし、それでもスタックオーバーフローが発生します。

4

3 に答える 3

25

私はこれについて広範囲に書いています：

seqまず、はい、アキュムレータの使用の厳密な評価を要求し、Haskell98にとどまりたい場合は次のようになります。

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

'Double'は、最適化がオンになっている厳密なアトミックタイプDouble＃のラッパーであり、正確なタイプであるため、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の章で説明されているように。

于 2009-10-24T19:40:12.700 に答える
9

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は、式の最も外側の関数呼び出しです。Haskellの怠惰のため、これにより最初に評価されます。まだ評価されていないパラメーターでseq呼び出され、パラメーターの評価は、誰かが実際に値にアクセスしようとするポイントまで延期されます。sseq l (go (s+x) (l+1) xs)

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

の位置を変更するとseq、プログラムは過剰なメモリを使用せずに正常に実行されます。

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

于 2009-10-24T20:16:04.220 に答える
6

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+ygo

ああ、正しい場所に括弧がなかったので、おそらく無限タイプのエラーメッセージが表示されました。私が最初にあなたのプログラムを書き留めたときに同じエラーが発生しました:-)

$!演算子は正しい結合法則であるため、括弧なしgo $! (s+x) $! (l+1)は次と同じ意味go $! ((s+x) $! (l+1))です。これは明らかに間違っています。

于 2009-10-24T19:40:19.347 に答える