不動点コンビネータ

combinator.js

"use strict";

// カリー化関数
const func = x => y => z => x + y + z;
func(1)(2)(3); // きもい


// 不動点コンビネータ
// 参考： http://mew.org/~kazu/material/2012-id-const.pdf
const y_con = f => (x => y => f(x(x))(y))
                   (x => y => f(x(x))(y));

const z_con = f => (x => f(y => x(x)(y)))
                   (x => f(y => x(x)(y)));

const fact = n => n == 0 ? 1 : n * fact(n - 1);
const fact_ = f => n => n == 0 ? 1 : n * f(n - 1); // 無名関数で再帰

console.assert(y_con(_=>fact)(5) == 120); // 終点の条件演算子を遅延評価で止める
console.assert(z_con(_=>fact)(5) == 120); // ためにfactをラムダでくくる

console.assert(y_con(fact_)(5) == 120); // こっちは二引数なので、そのままで大丈夫
console.assert(z_con(fact_)(5) == 120);


// SKIコンビネータ
const S = x => y => z => x(z)(y(z));
const K = x => y => x;

const T = K;                // 第一項を返す：True
const F = x => K(I)(x);     // 第二項を返す：False
const NOT = x => S(S(I)(K(F)))(K(T))(x);
const OR = x => S(I)(K(T))(x);
const AND = x => S(S)(K(K(F)))(x);

const B = x => S(K(S))(K)(x);       // (x,y,z) => x(y(z));
const C = x => S(B(B)(S))(K(K))(x); // (x,y,z) => x(z(y));
const M = x => S(I)(I)(x);          // x => x(x);
const L = x => C(B)(M)(x);          // (x,y) => x(y)(y);
const Y = x => B(M)(L)(x);          // Y = x => x(Y(x)); うごかない...

const ZERO = I;
const SUCC = S(S(K(S)))(K); //  インクリメント...