OCamlの匿名再帰関数

Question

匿名の再帰関数を作るにはどうすればいいですか？それは可能ですが、OCamlでどのように動作させるかはわかりません。私は行くそれを維持する方法がわからない

let a = 
    fun x -> .... 

...ここ

Answer 1

だけで無名関数を使って階乗の定義です：

let fact = 
    (fun f -> (fun x a -> f (x x) a) (fun x a -> f (x x) a)) 
    (fun f n -> if n < 2 then 1 else n * f (n - 1)) 

それは-rectypesを使用する必要がありますフラグ。ここで

は、それが動作することを示すセッションです：

$ rlwrap ocaml -rectypes 
     OCaml version 4.03.0 

let fact = 
    (fun f -> (fun x a -> f (x x) a) (fun x a -> f (x x) a)) 
    (fun f n -> if n < 2 then 1 else n * f (n - 1));; 
val fact : int -> int = <fun> 
# fact 8;; 
- : int = 40320 

私はここにY Combinatorのを見ることで、多少騙さ：Rosetta Code: Y Combinator

更新

免責事項：あなたが読むために、より良いだろう固定小数点数、およびY Combinatorを使って、あなたの情報を私から得ることができます。私は理論家ではなく、ちょうど謙虚な開業医です。

実際の計算はほとんど不可能です（しかし、私は確信しています）。しかし、高いレベルでは、このような考え方があります。

定義の最初の行は、一般に関数の固定小数点を計算するY連結子です。再帰関数は、関数から関数への関数の固定点です。

最初の目標は、固定小数点が階乗関数である関数を見つけることです。これが定義の2番目の行です。それにタイプint -> intの関数を与えると、タイプint -> intの別の関数が返されます。階乗関数を与えると、階乗関数を返します。これは、階乗関数がその固定点であることを意味する。

したがって、この関数にY結合子を適用すると、実際に階乗関数が得られます。

Answer 2

私はJeffrey Scofieldの答えに少し広げてみましょう。階乗関数の非匿名の再帰的な定義は

let rec fact n = 
    if n < 2 then 1 else n * fact (n - 1) 

可能性がありますが、匿名の再帰関数を定義しようとするときに発生する最初の問題は、実際の再帰呼び出し（私たちの場合はfact (n - 1)）を行う方法です。呼び出しには名前が必要ですが、無名関数の名前はありません。解決方法は、一時的な名前を使用することです。一時的な名前fでは、定義体は、「一時的な名前」fがバインドされていないので、ちょうど

fun n -> if n < 2 then 1 else n * f (n - 1) 

この用語は、タイプを持っていないです。しかし、これは、fと同様に境界を定めることによって型を持つ値にすることができます。私たちは結果gを呼ぶことにしましょう：

let g = fun f n -> if n < 2 then 1 else n * f (n - 1) 

gは、現時点ではまだ無名ではないですが、私は再びそれを参照したいという理由だけで。 gは(int -> int) -> (int -> int)であることに注意してください。私たちが望むもの（階乗関数）は、タイプ(int -> int)です。したがって、gは、私たちが望むタイプ（この場合は関数タイプ）を取り、同じタイプのものを生成します。直感は、gが階乗関数の近似を取ることです。すなわち、すべてnのNまでで働くfという関数があり、より良い近似を返します。つまり、Nすべてのnまで機能します。

最後に、gを実際の再帰的な定義に変えるものが必要です。 これは非常に一般的な作業です。 gは近似の質を改善することを思い出してください。最終階乗関数factは、それ以上改善することができないものです。したがってgをfactに適用すると、ちょうどfactと同じになります。実際には値の観点からのみ当てはまります。nのg fact nに固有の実際の計算はちょうどfact nのものと異なりますが、返される値は同じです）。つまり、factは固定小数点でgです。だから私たちに必要なのは、固定小数点を計算するものです。

幸いなことに、Yコンビネータを実行する関数が1つあります。値の観点から見ると、Yコンビネータ（OCamlではyを使用しましょう。大文字はコンストラクタ用に予約されています）は、gの場合はy g = g (y g)で定義されています：いくつかの関数gを指定すると、コンビネータはその固定点の1つを返します。我々の場合には その結果、

y : (`a -> `a) -> `a 

は、型変数は(int -> int)によってインスタンス化されます。 yを定義するための 可能な方法の1つは、

let y = fun g -> (fun x -> g (x x)) (fun x -> g (x x)) 

だろうが、これは遅延評価でのみ動作します（私は信じている、として、Haskellは持っています）。 OCamlは評価が高いので、使用するとスタックオーバーフローが発生します。その理由は、OCamlは、これまでgを呼び出すために取得せずに

g (y g) 8 
g (g (y g)) 8 
g (g (g (y g))) 8 
... 

にy g 8のようなものをオンしようとするということです。 溶液はyの内部遅延計算を使用することである。

let y = fun g -> (fun x a -> g (x x) a) (fun x a -> g (x x) a) 

一つの欠点は、yがそれ以上の任意のタイプのために動作しないことです。関数型に対してのみ機能します。

​​

しかし、他の値の再帰的定義ではなく、関数の再帰的定義をとにかく求めました。したがって、階乗関数の定義はy gであり、yおよびgは上記のように定義されています。どちらyもgはまだ無名ではないが、それは簡単に改善することができます。

(fun g -> (fun x a -> g (x x) a) (fun x a -> g (x x) a)) 
    (fun f n -> if n < 2 then 1 else n * f (n - 1)) 

UPDATE：

yの定義のみ-rectypesオプションで動作します。その理由は、xをそれ自身に適用するからです。