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

这里的问题是在整个 10^9 递归调用结束之前无法开始计算总和。本质上，你是在计算

1/(n**2) + ( 1/((n-1)**2) + ( 1/((n-2)**2) + ....

括号阻止开始求和。相反，我们希望

(( 1/(n**2) + 1/((n-1)**2) ) + 1/((n-2)**2) ) + ....

最简单的方法是使用 "accumulator" 附加参数：

summ 1 acc = 1 + acc
summ n acc = summ (n-1) $! acc + 1/(n**2)

main = do
    putStr "%"
    print (errorPercent (summ (10^9) 0))  -- set acc to 0 at the beginning

为了提高性能，我建议向 summ 添加类型签名，例如summ :: Int -> Double -> Double.

完整节目如下。此处运行时间为 12 秒 (ghc -O2)。

summ :: Int -> Double -> Double
summ 1 acc = 1 + acc
summ n acc = summ (n-1) $! acc + 1 / (fromIntegral n**2)

main :: IO ()
main = do
    putStr "%"
    print (summ (10^9) 0)  -- set acc to 0 at the beginning

Answer 2

chi 已经回答了问题的一部分，我认为这是主要问题，但还有其他问题困扰着我。当你说 10**9 时，你会得到一个 浮点数 数字（因为 ** 是 "fractional" 指数）。然后您使用浮点相等性来检查递归的基本情况。

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)

等等。如果您没有从 10⁹ 次调用中得到堆栈溢出，您肯定会遇到无限次调用。

您应该在整数上定义您的函数，这样就没有舍入误差

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。

Haskell - 递归堆栈溢出

Haskell - Recursion Stack Overflow

stack-overflow

recursion