如何避免 Haskell 中的 stackoverflow 错误

Question

我想实现这个功能：

正在调用 customPower 2 2 会回馈 2^2 + 2^1 + 1

正在调用 customPower 3 3 会回馈 3^3 + 3^2 + 3^1 + 1

这是我的代码：

customPower :: Int -> Int -> Int
customPower x y
          | y == 0 = 1
          | y > 0 = (x^(y)) + (customPower x y-1)

它给我堆栈溢出异常，我找不到错误在哪里。一切似乎都很好。

Answer 1

运算符的优先级低于函数调用，这意味着您的递归调用：

... + (customPower x y-1)

解释为：

... + ((customPower x y)-1)

所以你一直用相同的参数调用，因此递归永远不会结束。

我们可以通过为 y-1:

添加括号来解决这个问题

customPower :: Int -> Int -> Int
customPower x y
    | y > 0 = x^y + customPower x <b>(y-1)</b>
    | otherwise = 1

通过此修改，我们不会陷入无限循环：

Prelude> customPower 5 3
156

我们可以通过使用 sum :: Num a => [a] -> a and map :: (a -> b) -> [a] -> [b] 来重写上面的代码，用一行代码实现：

customPower :: (Num a, Integral b) => a -> b -> a
customPower x y = sum (map (x^) [0..y])

customPower :: (Num a, Integral b) => a -> b -> a
customPower x y = sum (take (y+1) (iterate (x*) 1))

由于 Haskell 的懒惰，上述尝试可能仍会导致调用堆栈与 y 的值成线性比例：函数是，就像@dfeuer 说的，不是尾递归函数，但是我们可以在这里使用累加器：

customPower :: Int -> Int -> Int
customPower x = go 1
    where go a y | y > 1 = a
                 | otherwise = seq a (go (a+x^y) (y-1))

由于上面的总和等于一个简单的公式，我们甚至可以计算出 O(y log x):

中的值

   y
.————            y+1
 ╲     i       x    - 1
 ╱    x    =   ————————
*————            x - 1
  i=0

所以我们可以计算出这个值：

customPower :: (Integral a, Integral b) => a -> b -> a
customPower x y = div (x^(y+1) - 1) (x - 1)

这通常会工作得更快，尽管在极少数情况下结果时间 x -1 大于类型的最大可表示数 a，这将导致溢出并 return 错误的数字。

How do I avoid stackoverflow error in Haskell