Y Combinatorによる再帰

この論文ではyコンビナータと呼ばれる高次関数を紹介します.それはすぐに有名に感謝しているstartup incubator 同じ名前の、しかし、この奇妙な響きは、すべてについて何ですか?
ほとんどの言語では、再帰は直接名前付き関数のサポートされています.たとえば、次のfactorial JavaScriptで書かれた関数は、再帰的に自身を呼び出します:

const factorial = n => n > 1 ? n * factorial(n-1) : 1
factorial(5) // 120

ラムダ、すなわち匿名関数は一般的に再帰のための組み込みサポートを持っていないが、論理が単純であるときに使用されるべきである(そして、それ以外の場合は名前付き関数に抜粋)、ラムダで再帰的な呼び出しをしたいと思わない.
したがって、上記のような再帰的な呼び出しをすることは、行く方法です.しかし、直接再帰を使用できないふりをしましょう.私たちの言語が一流の市民としての機能をサポートしている限り(変数に割り当てられ、引数として渡され、他のオブジェクトのように返される)、我々はまだ再帰を実装することができます.一つの良い方法はYコンバイナレータと呼ばれる高次関数です.名前は威圧的に聞こえるが、それはただの高次関数であり、別の関数をラップする関数である.
我々が以前にしたように直接再帰的な呼び出しをする代わりに、我々は我々を修正しますfactorial 関数はコールバック関数を呼び出します.このコールバック関数はfactorial 関数は再帰呼び出しを完了する.我々factorial したがって、関数は追加のパラメータを持ちます.recurse :

const factorial => recurse => n => n > 1 ? n * recurse(n-1) : 1;

上記の関数ではfactorial 直接、私たちはrecurse コールバック.
このコールバックはどんな感じですか?私たちはcallRecursively 関数は以下のようになります.

const callRecursively = target => args =>
                            target(args2 =>
                                target(args3 => 
                                    target(...)(args3))(args2))(args);

我々が我々の目標を呼ぶときfactorial この関数では、ターゲットが呼び出される次のパラメータを受け入れるコールバックを渡す必要があります.しかし、我々は無限の後退の問題に実行します.それぞれの呼び出しについては、新しいコールバックを供給し続ける必要があります.
それは私たちがこの制限を回避するのに役立つ巧妙なトリックがあることが判明.関数を作成し、関数を自身の引数として呼び出すことができます.JavaScriptではIIFE そうする.以下に、使用するメカニズムの例を示します.

(f => f(f))(self => console.log(self));

ラムダを供給するself => console.log(self) 自己実行ラムダへの引数として(f => f(f)) . このコード(例えばブラウザコンソール)を実行すると、変数self パラメータとして渡される関数を指します:

> (f => f(f))(self => console.log(self));
self => console.log(self)

我々は、無限の退陣の我々の問題を解決するために、この考えを使います.ターゲット関数を受け取るy(y Combinator)の関数を定義します.factorial ) と引数としてそのターゲット関数のパラメータ.私たちのY Combinator機能はそれから目標機能を呼びます.そして、それが再帰的な呼び出しをしたいときに、目標関数のためにコールバックを供給します.完全なコードは以下の通りです.

const Y = target => 
              args => 
                  (f => f(f))(self => target(a => self(self)(a)))(args);

const factorial = recurse => n => n > 1 ? n * recurse(n-1) : 1;

Y(factorial)(5); //120

上記のコードで、ターゲットの場合など.factorial , そして、その引数はy Combinator関数に渡されますself => target(a => self (self)(a)) . ターゲットが実行されるとコールバックa => self(self)(a) がtarget そのため、次の再帰呼び出しを開始できます.心に留めておきなさいself 関数への参照self => target(a => self(self)(a)) .
時factorial 関数は引数を受け取る5 我々の目標はcurried この例では、4 パラメータa . これは、ターゲット関数の終了条件が到達するまで、ターゲットへの再帰的な呼び出しをトリガーします.コールバックコードが実行されると、ハンドラに最初の引数としてリファレンスを渡す必要がありますself(self) 上記のコードのフラグメント.
Y Combinator関数は、最新のプログラミング言語で使用されるのを見たいと思っているものではありません.しかし、高次の関数は関数型プログラミングパラダイムの重要な部分であり、そのような関数がどのように振る舞うかの詳細については、まだ有用なエクササイズである.これらのラインに沿って機能を構成する一般的な考えは、広範囲にわたる使用ケースの向こう側に機能的プログラミングにおいて、共通に適用される.
また、洞察力を得るlambda calculus , 計算を理解するための強力な数学的枠組み例えば、我々は完全に自由変数がないことを示すために書かれたコードをインラインでインラインにすることができます.コードがこのようにインラインされているときには、正確に読めるわけではありませんが、このロジックの純粋なラムダ計算フォームに非常に近いものになります.

(target =>  args => (f => f(f))(self => target(a => self(self)(a)))(args))(recurse => n => n > 1 ? n * recurse(n-1) : 1)(5); //120

参考文献

Y combinator

Currying

Lambda calculus

IIFE