Combinator

combinator.md

Turing-complete

計算理論において、ある計算のメカニズムが万能チューリングマシンと同じ計算能力をもつとき、その計算モデルはチューリング完全（チューリングかんぜん、Turing-complete）あるいは計算完備であるという。

• Combinatory Logic(コンビネータ論理)
  • コンビネータ計算
  • ラムダ計算

Combinatory Logic

SKI Combinator

SKIコンビネータは，チューリング完全であることが証明されている。

S = x => y => z => x(z)(y(z));
K = x => y => x;
I = x => x;

B = f => g => x => f(g(x));
C = f => x => y => f(y)(x);

関数合成

S(K)(K);    // Iコンビネータ
S(K(S))(K); // 関数適用 Bコンビネータ
S(I)(I);    // Loop
S(K(S(I)(I)))(S(S(K(S))K)(K(S(I)(I)))) // 再帰 Yコンビネータ

Number

0 = K(I)
1 = I
2 = S(B)(I)
3 = S(B)(S(B)(I))

Lambda calculus(ラムダ計算)

ラムダ計算は、計算模型のひとつで、計算の実行を関数への引数の評価（英語: evaluation）と適用（英語: application）としてモデル化・抽象化した計算体系である。

ラムダ計算は,チューリングマシンと等価な数理モデルである

論理演算

TRUE  := λx y. x           // x => y => x;
FALSE := λx y. y           // x => y => y;
NOT   := λp. p FALSE TRUE  // p => p(FALSE)(TRUE);

AND   := λp q. p q FALSE
OR    := λp q. p TRUE q
IF    := λp x y. p x y

Church numerals(チャーチ数)

0 := λf x. x
1 := λf x. f x
2 := λf x. f (f x)
3 := λf x. f (f (f x))

SUCC := λn f x. f (n f x)
PLUS := λm n f x. m f (n f x)
MULT := λm n f. m (n f)
MULT := λm n. m (PLUS n) 0
PRED := λn f x. n (λg h. h (g f)) (λu. x) (λu. u)

Hands ON 論理演算

論理演算子を関数化

const not = p => !p
const and = (p, q) => p && q
const or  = (p, q) => p || q
const xor = (p, q) => !(p && q) && (p || q)
const eor = (p, q) => and(nand(p, q), or(p, q))
const comparator = fn => array => fn(...array)

const bit = [true, false];
const twobit = [
  [false, false]
  , [false, true]
  , [true, false]
  , [true, true]
];

console.log('not', bit.map(not));
console.log('and', twobit.map(comparator(and)));
console.log('or' , twobit.map(comparator(or)));
console.log('xor', twobit.map(comparator(xor)));

Lambda計算

const p = console.log; // print

// TRUE/FALSE
const T = x => y => x; // λx y. x
const F = x => y => y; // λx y. y

// 確認
p(T);                  // p(T(true)(false));
p(F);                  // p(F(true)(false));

// NOT
const N = p => p(F)(T); // λp. p FALSE TRUE

// 確認
p(N(T));               // p(N(T)(true)(false));
p(N(F));               // p(N(F)(true)(false));

// IF
const IF = p => x => y => p(x)(y); // λp x y. p x y
p(IF(T));
p(IF(F));

// AND, OR, XOR (定義した T,F,N またはパラメータ p,q を用いて完成させよ)
const AND  = p => q => ()()();
const OR   = p => q => ()()();
const XOR  = p => q => ()()();
const NAND = p => q => ()()();
const NOR  = p => q => ()()();

数値演算

const p = console.log;

// 準備運動

p('a', (x => x)(0));
p('b', (x => x)(x => x)(0));
p('c', (x => x)(x => x)(x => x)(0));

const I = x => x;

p('a', I(0));
p('b', I(I)(0));
p('c', I(I)(I)(0));

p('a', (x => x + 1)(0));
p('b', (x => x + 1)(x => x + 1)(0));             // error
p('c', (x => x + 1)(x => x + 1)(x => x + 1)(0)); // error
p('b#1', (x => x + 1)((x => x + 1)(0)));
p('b#2', (f => g => x => f(g(x)))(x => x + 1)(x => x +1)(0));

// 数値を関数で表す

// p((x => x)(0));                   // 0
// p((x => x + 1)(0));               // 1
// p((x => x + 1)((x => x + 1)(0))); // 2

const identity = x => x;
const zero = 0;
const succ = x => x + 1;

// p(identity(zero));                      // 0 f(x)
// p(succ(identity(zero)));                // 1 f(f(x))
// p(succ(succ(identity(zero))));          // 2 f(f(f(x)))

const N = f => x => f(x);        // n(f)(x);

// const ZERO = f => x => f(x);  // f => x => x,     x = 0
const ONE  = f => x => f(x);     // f => x => x + 1, x = 0
const TWO  = f => x => f(f(x));  // f => x => x + 1, x = 0
const ZERO = f => x => x;        // f => x => x + 1(fは，なんでもよい)

// N(f)(x)

p(ZERO(x = x + 1)(0));
p(ONE(x = x + 1)(0));
p(TWO(x = x + 1)(0));

const toInt = N => N(x => x + 1)(0);

p(toInt(ZERO));
p(toInt(ONE));
p(toInt(TWO));

// 
const SUCC = n => f => x => f(n(f)(x));
const PLUS = m => n => f => x => (m)(f)(n(f)(x));
const MUL  = m => n => f => m(n(f));
const POW  = m => n => n(m);
const PRED = n => f => x => n(g => h => h(g(f)))(u => x)(u => u);

reference.md

Reference

Programming

Name	#	Haskell	Ramda	Sanctuary	Signature
identity	I	id	identity	I	a → a
constant	K	const	always	K	a → b → a
apply	A	($)	call	A	(a → b) → a → b
thrush	T	(&)	applyTo	T	a → (a → b) → b
duplication	W	join²	unnest²	join²	(a → a → b) → a → b
flip	C	flip	flip	flip	(a → b → c) → b → a → c
compose	B	(.), fmap²	map²	compose, map²	(b → c) → (a → b) → a → c
substitution	S	ap²	ap²	ap²	(a → b → c) → (a → b) → a → c
psi	P	on		on	(b → b → c) → (a → b) → a → a → c
fix-point¹	Y	fix			(a → a) → a

SKI Combinator

const I = x => x;
const K = x => y => x;
const A = f => x => f(x);
const T = x => f => f(x);
const W = f => x => f(x)(x);
const C = f => y => x => f(x)(y);
const B = f => g => x => f(g(x));
const S = f => g => x => f(x)(g(x));
const P = f => g => x => y => f(g(x))(g(y));
const Y = f => (g => g(g))(g => f(x => g(g)(x)));

Functional JavaScript

const identity = x  => x;
const always   = x  => () => x;
const T = always(true);
const F = always(false);

const flatten = complexArray =>
  complexArray.reduce((acc, array) =>
    Array.isArray(array)
      ? acc.concat(flatten(array))
      : acc.concat(array) ,[]);

const curry1   = fn => x => fn(x);
const curry2   = fn => x => y => fn(x, y);
const curry    = fn =>
  (...args) => fn.bind(undefined, ...args);
const uncurry = fn => (...args) =>
  args.reduce((fn, arg) => fn(arg), fn);

const collect  = curry((fn, xs) => Array.from(xs, fn));
const foldl    = curry((fn, xs) => xs.reduce(fn));
const foldr    = curry((fn, xs) => xs.reduceRight(fn));

const partial  = (fn, ...params) =>
  (...args) => fn(params.concat(args));


const _compose = (f, g)   => x => f(g(x));
const compose  = (...fns) => fns.reduce(_compose);
const pipe     = (...fns) => fns.reduceRight(_compose);

Note

¹) In JavaScript and other non-lazy languages, it is impossible to implement the Y-combinator. Instead a variant known as the applicative or strict fix-point combinator is implemented. This variant is sometimes rererred to as the Z-combinator.

²) Algebras like ap have different implementations for different types. They work like Function combinators only for Function inputs.

Note that when I use the word "combinator" in this context, it implies "function combinator in the untyped lambda calculus".

• To Mock a Mocking Bird (book of combinatory puzzles and examples)
• Combinator Birds (summary of all combinators named by the book)
• CombinatorsJS (implementation of all the same combinators in JavaScripts)
• Fantasy Combinators (implementation of common combinators in JavaScript)
• Collected Lambdas (collection of noteworthy combinators)
• Programming With Nothing (talk)
• Church Encoding (wikipedia)
• Fixed-point combinator (wikipedia)
• Lambda calculus (wikipedia)
• SKI combinator calculus (wikipedia)
• BCKW combinator calculus (wikipedia)