前奏词取幂很难理解

Question

我正在阅读Haskell Prelude并发现它非常容易理解,然后我偶然发现了exponention的定义:

(^)              :: (Num a, Integral b) => a -> b -> a
x ^ 0            =  1
x ^ n | n > 0    =  f x (n-1) x
                         where f _ 0 y = y
                         f x n y = g x n  where
                                g x n | even n  = g (x*x) (n `quot` 2)
                                     | otherwise = f x (n-1) (x*y)
_ ^ _            = error "Prelude.^: negative exponent"

我不明白需要两个嵌套where的.

到目前为止我所理解的:

(^)              :: (Num a, Integral b) => a -> b -> a

基数必须是数字,指数为intege,ok.

x ^ 0            =  1

基础案例,简单.

g x n | even n  = g (x*x) (n `quot` 2)
      | otherwise = f x (n-1) (x*y)

通过平方来表达......有点......为什么f需要助手？为什么f和g给定的单个字母的名字呢？它只是优化,我错过了一些明显的东西吗？

 _ ^ _            = error "Prelude.^: negative exponent"

之前检查过N> 0,如果我们到达这里N则为负,所以错误.

---

我的实现将直接转换为以下代码:

Function exp-by-squaring(x, n )
    if n < 0 then return exp-by-squaring(1 / x, - n );
    else if n = 0 then return 1; else if n = 1 then return x ;
    else if n is even then return exp-by-squaring(x * x, n / 2);
    else if n is odd then return x * exp-by-squaring(x * x, (n - 1) / 2).

来自维基百科的伪代码.

Answer 1

为了说明@dfeuer所说的内容,请注意方法f是:

1. f 返回一个值
2. 或者,f用新的参数调用自己

因此f是尾递归,因此可以很容易地转换成循环.

另一方面,通过平方来考虑这种取幂的替代实现:

-- assume n >= 0
exp x 0 = 1
exp x n | even n    = exp (x*x) (n `quot` 2)
        | otherwise = x * exp x (n-1)

这里的问题是在else子句中,最后执行的操作是乘法.所以exp要么:

1. 返回1
2. 用新参数调用自己
3. 用一些新的参数调用自身并将结果乘以x.

exp 不是尾递归,因此不能转换成循环.

Answer 2

f确实是一种优化.天真的方法将是"自上而下",计算x^(n `div` 2)然后平方结果.这种方法的缺点是它构建了一堆中间计算.是什么f让这个实现做的是第一方x(一次乘法),然后递归结果提升到减少指数,尾巴.最终结果是该功能可能完全在机器寄存器中运行.g当指数是偶数时,似乎有助于避免检查循环的结束,但我不确定这是不是一个好主意.