haskell - 在幂函数的尾递归定义中严格评估的重要性

Question

我理解这个函数和尾递归，但我不明白为什么严格的评估很重要。如果没有严格的评估，它仍然是尾递归的，对吧？那么如果没有严格的评估，这个函数什么时候会失败呢？

turboPower a b = turboPower' 1 a b
  where
    turboPower' x a 0 = x
    turboPower' x a b
        | x `seq` a `seq` b `seq` False = undefined
        | even b = turboPower' x (a*a) (b `div` 2)
        | otherwise = turboPower' (x*a) a (b-1)

Answer 1

它不会失败（除非指数很大，因此 thunk 可能变得足够大以溢出堆栈），它会（可能）效率较低，因为没有严格的评估，参数变成 thunk，导致

turboPower' (let xN = let x(N-1) = ...; a(N-1) = ... in x(N-1)*a(N-1)) (let aN = let a(N-1) = ... in a(N-1)*a(n-1)) (let bN = ...)

这里不应该太戏剧化，因为嵌套级别在指数中是对数的，因此对于所有实际计算来说仍然很小，但它会产生巨大的差异，例如

foo :: Integer -> Integer
foo n = go 0 n
  where
    go acc m
      | m < 1     = acc
      | otherwise = go (acc + m^3 + m `mod` 7) (m-1)

其中嵌套级别在 中是线性的n。