この記事を書いた理由は、Yコンビネーターがどのように機能するかを理解したいという願望でした。
脳が錆びて時計のように機能しないように、私は新しい珍しいことを試してみます。
興味のために、DOSでLua 5.xをコンパイルしましたが、これには問題はありませんでしたが、標準テストでLuaを確認したときに、理解できない要因コードを見つけました。
しかし、彼はこれが関数型プログラミングに関連していることを明確に理解しました。
その結果、
Wikipedia の記事、Rubyでの実用的な 記事、PythonのYコンビ ネーターに関する 記事を見つけまし
た 。
Yコンビネータを使用すると、通常の（匿名を含む）関数を再帰的な関数に変換できます。 その主な価値は理論的であり、正式な計算の理論を正当化しますが、一部の人はそれを実際に適用します（この感覚は上記の記事のコメントを読んだ後に現れました）。
ウィキペディアによると、Yコンビネーターは、入力関数fを取り、f（g）= gのような関数gを返す高次関数の特殊なケースです。 おそらくそうかもしれませんが、この定義は理解に何のメリットも与えませんでした
[1] [2] 。
それがすべてどのように機能するかという階乗の古典的な例を理解してみましょう。 Pythonに慣れるので、Pythonが使用されます。
解析のプロセスでは、補助関数
dumbが使用されますが、これは後で削除します。
defダム（ ） ：
合格する
次のラムダ関数を、階乗を計算する再帰関数に変換してみましょう。
test = lambda f： lambda n： 1 n == 0 else n * f （ n- 1 ）
test（dumb）（0）== 1であるため、すでに一歩前進しています。
test（dumb）（1）を呼び出してみましょう。 インタプリタは引数0で
dumbを呼び出すことができないため、例外が発生します。トリックを実行して、呼び出し
テスト（test（dumb））（1）を行うことができます。 このようにして、このような呼び出し
テスト（test（test（test（test（test（test（test（test（test（test（dumb）））））））に到達することもできます。
このような呼び出しを行うことは可能ですか：
test（test（...））（x） 、ここで...はテスト関数への無限の呼び出しです
それは可能であり、
Yコンビネータがこれを支援します。
そのような呼び出し構造が明確に見える形式の1つを次に示します。
def Y （ f ） ：
return f （ ラムダ x：Y （ f ） （ x ） ）
また、それに応じて、階乗は次のように定義できます。
階乗= Y （ 検定 ）
ウィキペディアの定義の一部として、内部ラムダ関数（
ラムダn：... ）へのリンクがあり、このリンクでtestを呼び出したと言うことができます。
別のよく知られている再帰関数は、次のように書くことができます。
fibbonacci = Y （ ラムダ f： ラムダ n：n == 0の場合は 1 または n == 1 else f （ n- 2 ） + f （ n- 1 ） ）
呼び出し構造が効果的に隠されているYコンビネーターの別の形式：
def Y （ f ） ：
def g （ k ） ：
return f （ ラムダ a： （ k （ k ） ） （ a ） ）
リターン g （ g ）
もちろん、そのような階乗の実装には実用的な価値はなく、通常の再帰呼び出しよりもさらに遅くなります。 キャッシュを使用すると、メモリを犠牲にして計算を高速化できます。 これを行うには、Yコンビネータをわずかに変更する必要があります。
def Ycache （ f、data ） ：
def _fn （ x ） ：
データにx がある場合：
戻りデータ[ x ]
その他 ：
temp = （ f （ lambda x：Ycache （ f、data ） （ x ） ）
） （ x ）
データ[ x ] = temp
一時帰り
_fnを返す
フィボナッチ数を計算する関数は次のようになります。
fibbonacci = Ycache （ test 、 { } ）
単純な再帰オプションとは対照的に、200番目のフィボナッチ数の計算はほぼ瞬時に行われます。
そして最後に、ちょっと
変わった ：
クイックソート （
quick_sort ）
qsort = lambda h： lambda lst： （ lst if len （ lst ） < = 1 else （
h （ [ item < lst [ 0 ] ]の 場合 、 lstのアイテムのアイテム） + \
[ lst [ 0 ] ] * lst。 count （ lst [ 0 ] ） + \
h （ [ item > lst [ 0 ] ]の 場合、 [ lstのアイテムのアイテム） ） ））
print （ Y （ qsort ） （ [ 1、13、2、12、3、11、4、10、5、9、6、8、7 ] ） ））
_________
テキストは
Habraで準備されます
[1]これは、何らかのクラスの関数
f（f（f（f（f（f（f（f（f（f（f（... f（x））））） ）））））は
yの値に収束し、
f（y）= yとなります。
[2]ウィキペディアは議論の中で、Y-コンビネーターはアルゴリズム的に不溶性の問題を解決する必要はなく、単に特定のクラスの関数での彼の振る舞いを提供するだけだと書いています。