前奏求幂很难理解

Question

我正在阅读 Haskell Prelude 并发现它很容易理解，然后我偶然发现了指数定义：

(^)              :: (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

底数必须是数字，指数必须是整数，可以。

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

f确实是一种优化。天真的方法是 "top down"，计算 x^(n `div` 2)，然后对结果进行平方。这种方法的缺点是它构建了一堆中间计算。 f 让这个实现做的是首先对 x 进行平方（一次乘法），然后将结果提高到减少的指数，递归地拖尾。最终结果是该函数可能完全在机器寄存器中运行。 g 似乎有助于避免在指数为偶数时检查循环结束，但我不确定这是否是个好主意。

Answer 2

据我了解，只要指数是偶数，求幂就可以通过平方来解决。

这导致了为什么在奇数的情况下需要 f 的答案 - 我们使用 f 到 return g x 1 的结果，在所有其他奇怪的情况下，我们使用 f 返回 g-例程。

如果你看一个例子，我认为你最清楚：

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)

2^6 = -- x = 2, n = 6, 6 > 0 thus we can use the definition
f 2 (6-1) 2 = f 2 5 2 -- (*)
            = g 2 5 -- 5 is odd we are in the "otherwise" branch
            = f 2 4 (2*2) -- note that the second '2' is still in scope from  (*)
            = f 2 4 (4) -- (**) for reasons of better readability evaluate the expressions, be aware that haskell is lazy and wouldn't do that
            = g 2 4
            = g (2*2) (4 `quot` 2) = g 4 2
            = g (4*4) (2 `quot` 2) = g 16 1
            = f 16 0 (16*4) -- note that the 4 comes from the line marked with (**)
            = f 16 0 64 -- which is the base case for f
            = 64

现在回答您使用单字母函数名称的问题 - 这是您必须习惯的事情，这是社区中大多数人的写作方式。它对编译器如何命名函数没有影响 - 只要它们以小写字母开头。

Answer 3

为了说明@dfeuer 所说的内容，请注意 f 的书写方式：

freturns一个值
或者，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)

这里的问题是在 otherwise 子句中最后执行的操作是乘法。所以 exp 或者：

returns 1
用新参数调用自身
用一些新参数调用自身并将结果乘以 x。

exp 不是尾递归，因此不能转换为循环。

Answer 4

正如其他人指出的那样，该函数是使用尾递归编写的以提高效率。

但是，请注意，可以删除最里面的 where，同时保留尾递归，如下所示：而不是

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)

我们可以使用

x ^ n | n > 0 =  f x (n-1) x
      where f _ 0 y = y
            f x n y | even n    = f (x*x) (n `quot` 2) y
                    | otherwise = f x (n-1) (x*y)

这也可以说更具可读性。

但是我不知道前奏曲的作者为什么选择他们的变体。

前奏求幂很难理解

Prelude exponentiation is hard to understand

haskell

functional-programming

haskell-prelude