8

Haskellを学ぶために、関数と再帰を正しく理解するために円周率計算を実装しました。

ライプニッツの公式を使用して円周率を計算すると、次のようになります。円周率は、指定されたパラメーターの許容誤差と、その値を取得するための再帰関数呼び出しの数に出力されます。

reverseSign :: (Fractional a, Ord a) => a -> a 
reverseSign num = ((if num > 0
                        then -1
                        else 1) * (abs(num) + 2))

piCalc :: (Fractional a, Integral b, Ord a) => a -> (a, b)
piCalc tolerance = piCalc' 1 0.0 tolerance 0

piCalc' :: (Ord a, Fractional a, Integral b) => a -> a -> a -> b -> (a, b)
piCalc' denom prevPi tolerance count = if abs(newPi - prevPi) < tolerance
                                        then (newPi, count)
                                        else piCalc' (reverseSign denom) newPi tolerance (count + 1)
                                        where newPi = prevPi + (4 / denom)

したがって、これをGHCIで実行すると、期待どおりに機能するようです。

*Main> piCalc 0.001
(3.1420924036835256,2000)

しかし、許容値を細かく設定しすぎると、次のようになります。

*Main> piCalc 0.0000001
(3.1415927035898146,*** Exception: stack overflow

これは私には完全に直感に反しているようです。実際の計算は正常に機能しますが、再帰呼び出しの数を出力しようとすると失敗しますか？

なんでそうなの？

4

2 に答える 2

10

カウントは計算中に評価されることはないため、最後まで大量のサンク（スタックをオーバーフロー）として残されます。

BangPatterns拡張と書き込みを有効にすることで、計算中にその評価を強制できますpiCalc' denom prevPi tolerance !count = ...

では、なぜ私たちはの評価を強制するだけでよいのcountですか？さて、他のすべての引数はで評価されますif。再度電話をかける前に、実際にそれらすべてを検査する必要があるpiCalc'ため、サンクが蓄積することはありません。「計算できることを約束する」だけでなく、実際の値が必要です。count一方、計算中には必要になることはなく、最後まで一連のサンクとして残ることができます。

于 2013-01-30T09:50:07.867 に答える
8

これは、従来のfoldl (+) 0 [1..1000000]スタックオーバーフローの変形です。問題は、の評価中にカウント値が評価されないことですpiCalc'。これは、必要に応じて追加を行うことを表す、増え続けるサンクのセットを搭載していることを意味します。必要な場合、それを評価するにはサンクの数に比例したスタックの深さが必要であるという事実がオーバーフローを引き起こします。

最も単純なソリューションは、BangPatterns拡張機能を利用して、の開始をに変更piCalc'します

piCalc' denom prevPi tolerance !count = ...

これにより、パターンが一致したときにの値が強制的にcount評価されます。つまり、サンクの巨大なチェーンが成長することはありません。

同様に、拡張機能を使用せずに、次のように書くことができます

piCalc' denom prevPi tolerance count = count `seq` ...

これは、意味的には上記のソリューションとまったく同じですがseq、言語拡張を介して暗黙的にではなく、明示的に使用します。これにより、移植性は向上しますが、もう少し冗長になります。

piの近似がネストされたサンクの長いシーケンスではない理由については、カウントは次のとおりです。 、、、およびpiCalc'の値を必要とする計算結果の分岐。完了したかどうか、または別の反復を実行する必要があるかどうかを判断する前に、これらの値を調べる必要があります。評価が実行されるのはそのブランチです（関数適用が実行されるとき、これは通常、関数の結果にパターンマッチングがあることを意味します）。一方、の計算では、の値に依存するものはありません。したがって、計算中には評価されません。newPiprevPitolerancepiCalc'count

于 2013-01-30T09:51:27.567 に答える