3

私はいくつかの宿題をやっていますが、何かに何時間も立ち往生しています。本当に些細なことだと思いますが、利用可能なすべてのドキュメントを掘り下げた後でも、頭を包むことはできません。誰か手を貸してくれませんか？基本的に、OCaml プログラミングの演習では、関数 x^n を 2 乗アルゴリズムによる累乗で定義するよう求められます。

私は解決策を見てきました：

   let rec exp x = function
    0 -> 1
   | n when n mod 2 = 0  -> let y = exp x (n/2) in y*y
   | n when n mod 2 <> 0 -> let y = exp x ((n-1)/2) in y*y*x
   ;;

私が特に理解していないのは、fun ステートメントからパラメーター n をどのように省略できるか、および x との一致の変数として使用する必要がある理由です。これは、2 乗によるべき乗の定義との明らかな関連はありません。

これが私がそれを行う方法です：

   let rec exp x n = match n with
   0 -> 1
   | n when (n mod 2) = 1 -> (exp x ((n-1)/2)) * (exp x ((n-1)/2)) * x
   | n when (n mod 2) = 0 -> (exp x (n/2)) * (exp x (n/2))
   ;;
4

2 に答える 2

2

あなたのバージョンは構文的に正しく、良い答えが得られますが、実行には時間がかかります。あなたのコードでexpは、 が再帰的に 2 回呼び出されるため、2 倍の計算量が生成され、各呼び出しは 2 倍の計算量を生成しn=0ます。ソリューションでexpは、 が 1 回だけ呼び出され、結果が変数yに格納されてからy2 乗されます。

さて、構文については、

let f n = match n with
  | 0 -> 0
  | foo -> foo-1

次と同等です。

let f = function
  | 0 -> 0
  | foo -> foo-1

この行は、 2 つの引数let rec exp x = functionを取る関数の始まりです:と、パターン マッチングで使用される名前のない引数です。パターンマッチングでは、ラインx

 | n when n mod 2 = 0  ->

は、この引数に名前を付けますn。パターン マッチングのそれぞれのケースで異なる名前を使用できるというわけではありません (たとえそれがあまり明確でなくても):

| n when n mod 2 = 0  -> let y = exp x (n/2) in y*y
| p when p mod 2 <> 0 -> let y = exp x ((p-1)/2) in y*y*x
于 2012-10-21T09:45:10.927 に答える
1

キーワード「関数」は構文糖衣ではありません

match x with

しかし、

fun x -> match x with

したがって

let rec exp x = function

で置き換えることができます

let rec exp x = fun y -> match y with

もちろん、これはあなたのソリューションと同等です

let rec exp x y = match y with

混乱を避けるために、「n」ではなく「y」と書いたことに注意してください。一致後に導入された n 変数は新しい変数であり、一致するため、関数パラメーターにのみ関連しています。たとえば、代わりに

let y = x in ...

あなたは書くことができます：

match x with y -> ...

この一致式では、「y」式が一致した「パターン」です。そして、他のパターンと同様に、一致した値で変数 (ここでは y) をバインドします。(ここでは x の値) そして、他のパターンと同様に、パターン内の変数は新しい変数であり、以前に定義された変数を隠す可能性があります。あなたのコードで：

let rec exp x n = match n with
  0 -> 1
  | n when (n mod 2) = 1 -> (exp x ((n-1)/2)) * (exp x ((n-1)/2)) * x
  | n when (n mod 2) = 0 -> (exp x (n/2)) * (exp x (n/2))
;;

2 つのケースの変数 n は、パラメーター n を隠します。ただし、同じ名前の 2 つの変数は同じ値を持つため、これは問題ではありません。

于 2012-10-23T10:09:22.723 に答える