関数型プログラミングのトピックはHabréで非常によく開示されています。λ計算 、 教会番号などのトピックに関する記事がたくさんあります。したがって、新しいものは何も開きませんが、役に立たない非常に非効率なプログラムを1つ作成します。
人生が蜜のように見えないように、JavaScript言語の小さなサブセットに限定します。つまり、1つの引数の匿名関数のみを使用します。 他には何も必要ありません（ほとんど）。
階乗を定義することから始めましょう、そして問題を解決する過程で必要なものを見てみましょう：
var fact = function (n) { if (n === 0) return 1; return n * fact(n - 1); };
したがって、関数、論理値（ゼロとの比較演算の結果用）、条件演算子、単位の乗算および減算の演算が必要です。さらに、再帰的な関数呼び出しを実装する必要があります。
準備はいい？
論理値True 、 FalseおよびIf関数を使用した簡単なものから始めましょう。 TrueおよびFalseは 、最初または2番目の引数を選択する2つの引数のカリー化された関数によって表されます。 Trueは最初の引数を選択し、 Falseは2番目の引数を選択します。 ifが3つの引数、ブール値、ブランチ、およびブランチのいずれかを取る場合 。
var True = function (x) { return function (y) { return x; }; }; var False = function (x) { return function (y) { return y; }; }; var If = function (p) { return function (t) { return function (e) { return p(t)(e); } }; };
次のようなコードを実行することにより、コンソールにふけることができます。
console.log(If(True)('foo')('bar')); console.log(If(False)('foo')('bar'));
次に、数字が必要です。 自然数のセットは、数値ZEROの値と操作PLUS_ ONEを決定することにより取得できます。 大まかに言えば、教会番号は2つの引数の関数であり、最初の引数を2番目の引数にn回適用します。nは対応する正の整数です。
var Zero = function (f) { return function (x) { return x; }; }; var Succ = function (n) { return function (f) { return function (x) { return f(n(f)(x)); }; }; };
さらに、数値がゼロかどうかをチェックする述語を定義し、階乗の実装ではそのようなチェックが必要になります。 数値の最初の引数が少なくとも1回実行されると、述語はFalseを返します。
var IsZero = function (n) { return n(function (x) { return False; })(True); };
数字の仕組みを確認します。
Succ(Succ(Succ(Zero)))(function (x) { return x + 1; })(0); console.log(If(IsZero(Zero))('zero')('not zero')); console.log(If(IsZero(Succ(Zero)))('zero')('not zero'));
ご覧のとおり、ゼロに3回追加され、述語は送信された番号を正しく認識します。
すべての自然数ができたので、2つの数値を乗算する関数を定義します。乗算の結果は、引数をn回m回適用する関数です。
var Mul = function (n) { return function (m) { return function (f) { return n(m(f)); }; }; };
数字から1を引く方法を学ぶことは残っています。 ここではすべてが少し複雑です。 減算の考え方は、数値のペア（n、n-1）が構築され、ペアの2番目の要素が取得されるということです。 したがって、ペアのコンストラクターと、最初と2番目の要素を取得する関数を取得する必要があります。 次に、以前の数を取得する機能を決定できます。
var Pair = function (a) { return function (b) { return function (t) { return t(a)(b); }; }; }; var Fst = function (p) { return p(True); }; var Snd = function (p) { return p(False); }; var Pred = function (n) { return function (s) { return function (z) { return Snd(n(function (p) { return Pair(s(Fst(p)))(Fst(p)); })(Pair(z)(z))); }; }; };
ペアと減算で遊んでみましょう：
Fst(Pair('foo')('bar')); // => "foo" Snd(Pair('foo')('bar')); // => "bar" Pred(Succ(Succ(Zero)))(function (x) { return x + 1; })(0); // => 1
すべての準備ができており、階乗を実装できるようです：
var fact = function (n) { return If(IsZero(n))(Succ(Zero))(Mul(n)(fact(Pred(n)))); };
しかし、2つの問題があります。1つ目は、JavaScriptが適用可能な計算順序を持つ言語であり、階乗がハングすることです。 引数の値に関係なく、再帰呼び出しを行います。 この問題は、再帰呼び出しを匿名関数にラップし、実行を遅らせることで簡単に解決できます。
var fact = function (n) { return If(IsZero(n))(Succ(Zero))(function (x) { return Mul(n)(fact(Pred(n)))(x); }); };
これで、関数は正しく機能します。
fact(Succ(Succ(Succ(Zero))))(function (x) { return x + 1; })(0); // => 6
最後の問題は残っています。 最初は、匿名関数のみを使用することを約束しましたが、ここではfactと呼ばれる再帰呼び出しを確認します。 私たちはそれを取り除く必要があり、 Yコンビネーターがこれを助けてくれます。 私はその仕事の原理を説明しません。このテーマに関する記事はHabrとHabrの両方にあります。 たとえば、このブログ投稿をお勧めします。 適用言語のYコンビネーターは次のようになります。
var Y = function (f) { return function (x) { return x(x); }(function (x) { return function (y) { return f(x(x))(y); }; }); };
次のように操作の正確性を確認できます。
Y(function (f) { return function (n) { return If(IsZero(n))(Succ(Zero))(function (x) { return Mul(n)(f(Pred(n)))(x); }); }; })(Succ(Succ(Succ(Zero))))(function (x) { return x + 1; })(0); // => 6
次に、階乗をYコンビネーターに代入して、最終バージョンを取得します。
var fact = function (x) { return x(x); }(function (x) { return function (y) { return function (f) { return function (n) { return If(IsZero(n))(Succ(Zero))(function (x) { return Mul(n)(f(Pred(n)))(x); }); }; }(x(x))(y); }; });
より便利にするために、 NatToChurchおよびChurchToNat関数を定義します 。
var NatToChurch = function (n) { return n == 0 ? Zero : function (f) { return function (x) { return f(NatToChurch(n - ChurchToNat(Succ(Zero)))(f)(x)); }; }; }; var ChurchToNat = function (n) { return n(function (x) { return x + 1; })(0); };
これで、実験をコンソールに配置できます。
ChurchToNat(fact(NatToChurch(5))); // => 120
最後のステップは、すべての順列を実行し、最終関数を取得することです。
注意、多くの機能
var fact = function (x) { return x(x); }(function (x) { return function (y) { return function (f) { return function (n) { return function (p) { return function (t) { return function (e) { return p(t)(e); } }; }(function (n) { return n(function (x) { return function (x) { return function (y) { return y; }; }; })(function (x) { return function (y) { return x; }; }); }(n))(function (n) { return function (f) { return function (x) { return f(n(f)(x)); }; }; }(function (f) { return function (x) { return x; }; }))(function (x) { return function (n) { return function (m) { return function (f) { return n(m(f)); }; }; }(n)(f(function (n) { return function (s) { return function (z) { return function (p) { return p(function (x) { return function (y) { return y; }; }); }(n(function (p) { return function (a) { return function (b) { return function (t) { return t(a)(b); }; }; }(s(function (p) { return p(function (x) { return function (y) { return x; }; }); }(p)))(function (p) { return p(function (x) { return function (y) { return x; }; }); }(p)); })(function (a) { return function (b) { return function (t) { return t(a)(b); }; }; }(z)(z))); }; }; }(n)))(x); }); }; }(x(x))(y); }; });
「なぜこれを行うのか？」という質問に答える必要があります。 率直に言って、私はこの質問に答えがありません。 すべてに良い！