2

私には機能があります

// Will perform a given function twice
let twice f = (fun x -> f (f x))

それから私は何かを持っています。

// Take x add 1
let f x = x+1

2回呼び出す方法に応じて、左結合性に対する動作が異なります。

(twice (twice (twice (twice f)))) 0;; // Outputs 16
twice twice twice twice f 0;; // Outputs 65536

もう 2 回追加すると、私のプログラムは StackOverflow を実行しますが、これまでのところ、パターンなしで動作しているように見えます。

twice呼び出される回数を k とします。

カリー化されていないのは、答えを得るのに 2^k です。

カレーは非常に奇妙です。仮説 1:呼び出し回数が 4 未満の場合は 2^(2^(k-1)) のように見えるが、k が 4 の場合は 2^(2^k) のように動作する

誰かがパターンを見ますか？または、それを証明するために k = 4 を超えて実行できますか?

4

2 に答える 2

1

確かに、それはすべて結合性に関するものです。あなたが書くとき、

let x1 = twice twice twice twice f 0

に等しい

let x11 = (((twice twice) twice) twice) f 0

これにより、呼び出し順序が指数関数的に増加します。各twice呼び出しはf x2 回呼び出されることになっています。代わりに、それ自体を再帰的に呼び出し、最も内側の呼び出しのみが を呼び出しfます。

関数のプロトタイプを見ることができます：

let y1: ( _ -> _ -> int) = twice twice twice twice
// val y1: ((int -> int) -> int -> int)

連想性を適切に機能させるための最小限のコードは次のようになります。

// note we need to specify a type here
let y2: ( _ -> _ -> int) = twice >> twice >> twice >> twice
// the same with all arguments
let x2 = (twice >> twice >> twice >> twice) f 0

また

let y3 = f |> twice |> twice |> twice |> twice
let x3 = (f |> twice |> twice |> twice |> twice) 0
于 2013-06-06T11:18:33.157 に答える