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 回答