8

在尝试学习 Haskell 时，我实现了一个 pi 计算，以便正确理解函数和递归。

使用莱布尼茨公式计算 pi，我想出了以下内容，它将 pi 打印到给定参数的容差，以及递归函数调用的次数以获得该值：

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

在计算过程中从未对计数进行评估，因此直到最后它都会留下大量的 thunk（溢出堆栈）。

BangPatterns您可以在计算期间通过启用扩展和编写来强制其评估piCalc' denom prevPi tolerance !count = ...

那么为什么我们只需要强制评估count呢？好吧，所有其他参数都在if. 我们实际上需要在再次调用之前检查它们piCalc'，所以不会产生重复声；我们需要实际值，而不仅仅是“承诺可以计算它们”！count另一方面，在计算过程中永远不需要，并且可以作为一系列 thunk 一直保留到最后。

于 2013-01-30T09:50:07.867 回答
8

这是传统foldl (+) 0 [1..1000000]堆栈溢出的变体。问题是在评估 的过程中永远不会评估计数值piCalc'。这意味着它只携带一组不断增长的 thunk，表示在需要时要完成的添加。当需要它时，评估它需要与 thunk 数量成比例的堆栈深度这一事实会导致溢出。

最简单的解决方案是使用BangPatterns扩展名，将开头更改piCalc'为

piCalc' denom prevPi tolerance !count = ...

这会强制在count匹配模式时评估 的值，这意味着它永远不会长出巨大的 thunk 链。

等效地，并且不使用扩展名，您可以将其编写为

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

这在语义上与上述解决方案完全相同，但它seq通过语言扩展显式使用而不是隐式使用。这使它更便携，但更冗长。

至于为什么 pi 的近似值不是一长串嵌套的 thunk，而是 count 是：在需要、和piCalc'的值的计算结果上进行分支。它必须在决定是否完成或是否需要运行另一次迭代之前检查这些值。正是那个分支导致执行评估（当执行函数应用程序时，这通常意味着函数结果的模式匹配。）另一方面，计算中的任何内容都取决于,因此在计算过程中不会对其进行评估。newPiprevPitolerancepiCalc'count

于 2013-01-30T09:51:27.567 回答