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"

ネストされた 2 つの の必要性がわかりません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)

2 乗によるべき乗... 一種の ... なぜ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

7

f確かに最適化です。単純なアプローチは「トップダウン」でx^(n `div` 2)あり、結果を計算してから二乗します。このアプローチの欠点は、中間計算のスタックを構築することです。fこの実装でできることは、最初に 2 乗( x1 回の乗算) を行い、次に結果を減数指数まで上げ、再帰的に末尾にすることです。最終結果は、関数が完全にマシン レジスタで動作する可能性が高いということです。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

ここで、1 文字の関数名を使用するという質問に移ります。これは、コミュニティのほとんどの人が書く方法であることに慣れる必要があります。関数の名前が小文字で始まる限り、コンパイラには影響しません。

于 2015-08-28T12:51:07.950 に答える