7

我正在阅读 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的 s。

到目前为止我所理解的：

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

来自维基百科的伪代码。

4

4 回答 4

12

为了说明@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不是尾递归的，因此不能转换为循环。

于 2015-08-28T13:01:27.863 回答
7

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

于 2015-08-28T12:48:45.420 回答
1

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

这导致了为什么f在奇数的情况下需要的答案 - 我们使用f在 的情况下返回结果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

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

于 2015-08-28T12:51:07.950 回答
1

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

但是，请注意，可以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 的作者选择了他们的变体。

于 2015-08-28T15:33:13.810 回答