haskell - 如何避免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 (y-1)
    | otherwise = 1

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

Prelude> customPower 5 3
156 

我们可以通过使用 sum :: Num a => [a] -> a 和 map :: (a -> b) -> [a] -> [b] 重写上述内容，以单行代码实现:

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

或者我们可以使用 iterate :: (a -> a) -> a -> [a] :

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类型的最大可表示数字的次数，但这通常会更快地工作，这将导致溢出并返回错误的数字。