Haskell - 递归堆栈

Question

我试图将所有 n 从 1 求和到一个非常大的数字(现在为 10**9)，但它会导致堆栈溢出。此外，我不认为在 1 处停止并在不同行中求和 n 是最有效的方法，但下面的代码是我对 Haskell 的全部知识。我真的不太了解函数式编程，我想尽可能多地解释一下。 (我也试过把 $!strict 放在最后一行，这在其他地方被告知，但它没有改变。如果你解释了我可以做这个递归函数的最有效的方式，我会很高兴。)

main :: IO()

summ 1 = 1
summ n = 1/(n**2) + summ (n-1)

expected_value = pi*pi/6
errorPercent n = n / expected_value * 100

main = do
    putStr "%"
    print (errorPercent (summ $! (10**9)))

Answer 1

chi 已经回答了一点问题，我认为这是主要问题，但还有其他问题困扰着我。当你说 10**9 ，你得到一个浮点数(因为 ** 是“分数”求幂)。然后您使用浮点相等来检查递归的基本情况。

summ 1 = ...

问题在于这是可能的，并且随着参数变大，很可能由于数值错误，您几乎不会错过基本情况并永远下降为负值。

summ 4 =        ... summ 3
summ 3 =        ... summ 2.000001
summ 2.000001 = ... summ 1.000001 
summ 1.000001 = ... summ 0.000001  -- BASE CASE MISSED!
summ 0.000001 = ... summ (-1.000001)
summ (-1.000001) = ... summ (-2.000001)

等等。如果您没有从 109 次调用中得到堆栈溢出，那么您肯定会遇到无穷多的调用。

您应该在整数上定义您的函数，以便没有舍入误差

summ :: Int -> Double
summ 1 = 1
summ n = 1 / (fromIntegral n ** 2) + summ (n - 1)
--            ^^^^^^^^^^^^
-- conversion necessary to go from Int to Double

main = ... print (summ (10 ^ 9))
--                      ^^^^^^
--      use integral exponentiation (^) instead of (**)

或使用更宽容的基本情况

summ :: Double -> Double
summ n | n <= 1 = 1
summ n = 1 / (n ** 2) + summ (n - 1)

在任何一种情况下，您都应该按照 chi 的建议以累加器样式执行此操作，并且您也绝对应该输入类型签名。

这是 more on how you get stack overflows in Haskell如果你很好奇。