JavaScript でラムダ計算

「[ラムダ計算 - Wikipedia](https://ja.wikipedia.org/wiki/%E3%83%A9%E3%83%A0%E3%83%80%E8%A8%88%E7%AE%97)」を JavaScript に落とし込みながら読む。 補完的に 「[Church encoding - Wikipedia](https://en.wikipedia.org/wiki/Church_encoding)」、「[不動点コンビネータ - Wikipedia](https://ja.wikipedia.org/wiki/%E4%B8%8D%E5%8B%95%E7%82%B9%E3%82%B3%E3%83%B3%E3%83%93%E3%83%8D%E3%83%BC%E3%82%BF)」を参照。

# 01. ブール代数
二つの引数をとり左を返す関数と右を返す関数でBoolの二値 `TRUE`, `FALSE` を定義する:

```js
const TRUE = x => y => x;
const FALSE = x => y => y;
```

表示関数 `bisplay` を以下のように定義して以降使っていく:

```js
const bisplay = f => f('T')('F');

bisplay(TRUE); // -> T
bisplay(FALSE); // -> F
```

`NOT`, `AND`, `OR`, `IFELSE` を以下のように定義する:

```js
const NOT = p => p(FALSE)(TRUE);
  // p がTRUE なら左をとるので、FALSE に評価される
  // p がFALSE なら右をとるので TRUE に評価されるので納得

const AND = p => q => p(q)(FALSE);
  // p が TRUE なら q で評価され
  // p が FALSE なら FALSE に評価されるので納得

const OR =  p => q => p(TRUE)(q);
  // p が TRUE なら TRUE に評価される
  // p が FALSE なら q に評価されるので納得

const IFELSE = p => x => y => p(x)(y);
  // p が TRUE なら 左である x に評価され
  // p が FALSE なら 右である y に評価されるので納得
```

動作確認:

```js
[TRUE, FALSE].map(p => bisplay(NOT(p))); // -> [ 'F', 'T' ]

const truth = [[TRUE, TRUE], [TRUE, FALSE], [FALSE, TRUE], [FALSE, FALSE]];
truth.map(([p, q]) => bisplay(AND(p)(q))); // -> [ 'T', 'F', 'F', 'F' ]
truth.map(([p, q]) => bisplay(OR(p)(q))); // -> [ 'T', 'T', 'T', 'F' ]

[TRUE, FALSE].map(p => IFELSE(p)('koko')('doko')); // -> [ 'koko', 'doko' ]
```


# 02. 自然数
0 には与えられた関数を 0回適用する関数を割り当てる。1 には与えられた関数を 1回適用する関数を割り当てる。2 には与えられた関数を 2回適用する関数を割り当てる。このような決めごとで関数と自然数を対応付ける。`ZERO`と `SUCC` を以下に定義すれば、関数と自然数を対応付けられる:

```js
const ZERO = f => x => x;
const SUCC = n => f => x => f(n(f)(x));
  // n(f)(x) は x に f を n 回適用した値と読める
  // この値にもう一回 f を適用してあげているので、後続を表すことになる
```

動作確認。例えば `n => n + 1` という関数は、1 増やす関数なので、これが N 回適用されたら N 増える。そこで表示関数 `display` を以下のように定義する:

```js
const display = f => f(n => n + 1)(0);

display(ZERO); // -> 0
display(SUCC(ZERO)); // -> 1
display(SUCC(SUCC(ZERO))); // -> 2
display(SUCC(SUCC(SUCC(ZERO)))); // -> 3
```

ゼロ判定述語 `ISZERO` と後続の逆 `PRED` を定義:

```js
const ISZERO = n => n(x => FALSE)(TRUE);
  // x => FALSE は、「1回でも適用したらFALSEになる関数」
  // それを TRUE に n 回適用するので、 ISZERO の実装として妥当

const PRED = n => f => x => n(g => h => h(g(f)))(u => x)(u => u);
  // 考えたやつ天才やろ。わからん。
```

動作確認:

```js
const range = [ZERO, SUCC(ZERO), SUCC(SUCC(ZERO)), SUCC(SUCC(SUCC(ZERO)))];

range.map(ISZERO).map(bisplay); // -> [ 'T', 'F', 'F', 'F' ]

range.map(PRED).map(display); // -> [ 0, 0, 1, 2 ]
```

# 03. 足し算と掛け算
自然数が定義できれば、あとは数学と同じ定義で足し算と掛け算を定義できる:

```js
const PLUS = m => n => f => x => m(f)(n(f)(x));
  // n(f)(x) は x に f を n 回適用した値と読める
  // この値を X として、 m(f)(X) としている。
  // m(f)(X) は X に f を m 回適用しているのだが、
  // 先のとおり X は x に f を n回適用した値なので
  // 総合的にみると x に f を m + n 回適用した値になる
```

```js
const MULT = m => n => f => m(n(f));
  // n(f) は f を n 回適用する関数とよめる
  // この関数をさらに mに渡し m(n(f)) としているので、
  // f を n回適用する関数を m回適用する関数と評価できる
  // 総合的にみると f を m*n 回適用する関数であると読める
```

確かめる:

```js
const three = SUCC(SUCC(SUCC(ZERO)));
const five = SUCC(SUCC(three));

display(PLUS(three)(five)); // -> 8
display(PLUS(ZERO)(three)); // -> 3
display(MULT(three)(five)); // -> 15
display(MULT(ZERO)(five)); // -> 0
```

# 04. 再帰
Zコンビネータ:

```js
const Z = f => (x => f(y => x(x)(y)))(x => f(y => x(x)(y)));
```

を使うと、再帰が可能になる。階乗計算:

```js
const facto = Z(f => i =>
  ISZERO(i)(() => SUCC(ZERO))(() => MULT(i)(f(PRED(i))))()
);

display(facto(SUCC(SUCC(SUCC(SUCC(ZERO)))))); // -> 24
```

# 05. ペア / 二つ組

```js
const PAIR = x => y => f => f(x)(y);
const FIRST = p => p(TRUE);
const SECOND = p => p(FALSE);
```

動作確認:

```js
const pisplay = p => p(x => y => [x, y]);

const pair = PAIR('first')('second');
pisplay(pair); // -> [ 'first', 'second' ]
FIRST(pair); // -> 'first'
SECOND(pair); // -> 'second'
```

# 06. リスト

```js
const CONS = PAIR;
const HEAD = FIRST;
const TAIL = SECOND;
const NIL = FALSE;
const ISNIL = l => l(h => t => d => FALSE)(TRUE);
```

動作確認:

```js
bisplay(ISNIL(NIL)); // -> 'T'

const empty = NIL;
const added = CONS('a')(empty);
const moreAdded = CONS('b')(added);
const [b, x] = [HEAD(moreAdded), TAIL(moreAdded)];
b; // -> 'b'
const [a, y] = [HEAD(x), TAIL(x)];
a; // -> 'a'
bisplay(ISNIL(y)); // -> 'T'
```