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，导致

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 中呈线性。