尝试显示数字时,GHCI中的堆栈溢出

Question

在尝试学习Haskell时,我已经实现了pi计算,以便正确理解函数和递归.

使用Leibniz公式计算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

这对我来说似乎完全违反直觉; 实际的计算工作正常,但只是试图打印多少递归调用失败？

为什么会这样？

Answer 1

在计算过程中不会计算计数,因此它会留下大量的thunk(溢出堆栈)直到最后.

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

那么为什么我们只需要强制进行评估count呢？好吧,所有其他参数都在评估中if.我们实际上需要在piCalc'再次打电话之前检查它们,所以thunks没有建立起来; 我们需要实际值,而不仅仅是"可以计算它们的承诺"!count另一方面,在计算过程中从不需要,并且可以保持为一系列的thunks直到最后.

Answer 2

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

最简单的解决方案利用了的BangPatterns延长,改变的开始piCalc'到

piCalc' denom prevPi tolerance !count = ...

这会强制在count模式匹配时评估值,这意味着它永远不会生成巨大的thunk链.

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

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

这与上述解决方案在语义上完全等效,但它seq通过语言扩展显式而非隐式使用.这使它更便携,但更冗长.

至于为什么圆周率的近似值是没有嵌套的thunk长序列,但数量是:piCalc'在计算需要的数值结果枝newPi,prevPi和tolerance.它必须先检查这些值,然后才能确定它是否已完成或是否需要运行另一次迭代.这是导致执行评估的分支(当执行函数应用程序时,通常意味着函数的结果是模式匹配.)另一方面,计算中的任何内容都piCalc'取决于值count,所以在计算过程中不进行评估.