实施(^)

Question

我正在阅读标准haskell库的执行代码(^):

(^) :: (Num a, Integral b) => a -> b -> a
x0 ^ y0 | y0 < 0    = errorWithoutStackTrace "Negative exponent"
        | y0 == 0   = 1
        | otherwise = f x0 y0
    where -- f : x0 ^ y0 = x ^ y
          f x y | even y    = f (x * x) (y `quot` 2)
                | y == 1    = x
                | otherwise = g (x * x) ((y - 1) `quot` 2) x
          -- g : x0 ^ y0 = (x ^ y) * z
          g x y z | even y = g (x * x) (y `quot` 2) z
                  | y == 1 = x * z
                  | otherwise = g (x * x) ((y - 1) `quot` 2) (x * z)

现在这个定义g的部分对我来说很奇怪为什么不像这样实现它:

expo :: (Num a ,Integral b) => a -> b ->a
expo x0 y0 
    | y0 == 0 = 1
    | y0 <  0 = errorWithoutStackTrace "Negative exponent"
    | otherwise = f x0 y0
    where
      f x y | even y = f (x*x) (y `quot` 2)
              | y==1 = x
              | otherwise = x * f  x (y-1)

但确实插入说3 ^ 1000000表明(^)比世博会快约0.04秒.

为什么(^)比快expo？

Answer 1

作为编写代码的人,我可以告诉你为什么它很复杂.:)这个想法是尾递归以获得循环,并且还执行最小数量的乘法.我不喜欢复杂性,所以如果你找到更优雅的方式,请提交错误报告.

Answer 2

如果递归调用的返回值按原样返回,则函数是尾递归的,无需进一步处理.In expo,f不是尾递归的,因为otherwise = x * f x (y-1):返回值在返回之前f乘以x.both f和gin (^) 都是尾递归的,因为它们的返回值是未修改的.

为什么这很重要？尾递归函数可以比一般递归函数更有效地实现.因为编译器不需要为递归调用创建新的上下文(堆栈帧,你有什么),它可以重用调用者的上下文作为递归调用的上下文.这节省了调用函数的大量开销,就像内联函数比调用函数更有效.