Haskell - 递归堆栈溢出问题

Question

我正在尝试将从1到非常大的数字（目前为10 ** 9）的所有n相加，但它会导致堆栈溢出。此外，我认为在1处停止并将n分别求和不是最有效的方法，但下面的代码是我对Haskell的全部了解。我真的不太了解函数式编程，希望能提供尽可能多的解释。（我也尝试在最后一行放置$！严格，这是其他地方告诉我的，但没有改变任何东西。如果您能解释我可以执行此递归函数的最有效方法，我会很高兴。）

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)))

- Terobero

---

顺便提一下，你可以将 summ 写成 summ n = sum [ 1 / i^2 | i <- [1..n] ]。很不错，对吧？（记得使用优化编译） - luqui

@luqui - 我认为你会想要使用 sum [ 1 / i^2 | i <- reverse [1..n] ] 来避免精度损失。 - Omnifarious

@luqui - 这是由于舍入误差导致的。浮点数在加在一起的数字大小相似时效果最佳。否则，从小数中添加的位数会从大数的末尾旋转并且甚至不会改变它。因此，即使您添加了几十万个这样的微小数字，它们也根本不会改变原始数字。 - Omnifarious

@Omnifarious，哦，这很有道理。因此，为了获得最大的准确性，我们应该按增加的幅度对数字列表进行排序（如果它是左折叠）。... 对吧？这很直观，但我不能排除可能存在某些关联选择，例如((x1+x4)+(x2+x5))+x3，可以实现更好的准确性。 - luqui

@luqui - 一般来说是这样的。但我也可以想象在某些特定情况下，不同的排序可能更好。对于其他操作也有其他规则。我不知道它们都是什么，但我知道充分利用浮点精度需要仔细考虑。 - Omnifarious

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)

等等，如果你在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)

无论哪种情况，你都应该采用累加器样式（accumulator style）来完成，并且你也肯定需要加上类型签名。

如果你好奇的话，这里有更多关于如何在 Haskell 中获取堆栈溢出的信息。

- luqui

Answer 2

这里的问题在于，只有当所有10^9个递归调用结束后，才能开始计算总和。实际上，你正在计算的是：

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

括号的作用是防止开始求和。相反，我们希望有

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

最简单的方法是使用“累加器”作为附加参数：

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

- chi

---

@Terobero 你在编译时使用了优化选项比如 -O2，然后再运行代码吗？如果你是在 GHCi 中运行代码的话，那通常会很慢。 - chi

我正在使用VSCode和Stack。在Windows中，我该如何做你说的那件事？ - Terobero

@Terobero 我对VSCode没有什么了解，不过我猜它可以使用GHC编译代码，因为它运行main而非给你一个REPL提示(是吗？)。如果还没有的话，在选项中应该有一些地方可以添加-O2。相反，我会使用命令行stack ghc -- File.hs -O2。 - chi

@Terobero 请看最后一次编辑。去掉 errorPercent，并开启 -O2 后，这个程序在这里运行10^9的数据只需要12秒。你20分钟太长了。 - chi

对于整数变量，使用 Int 或其他整型更快且更安全。使用 Double 可能会导致一些微妙的问题，例如当 x 是足够大的 Double 时，x == x+1，并且舍入误差可能很容易破坏程序。除了在近似值足够精确的情况下（例如不需要精确比较的情况，如 if x == 1 then ...），我倾向于避免使用浮点数。luqui 在他的回答中展示了为什么在这里使用 Double 不起作用。 - chi