Church Encoding は、λ計算（Lambda Calculus）由来のテクニックで、Number、Boolean、データ構造を関数だけで表現できる驚きの手法です！つまり、プリミティブな型を一切使わずに計算ができるんです。
この考え方は関数型プログラミングの基礎となっており、「計算とは何か？」を純粋に示してくれます。今回は、NumberとBooleanを関数のみで表す方法を一緒に見てみましょう！
Church Numerals: 数を関数でカウントする
もし、Numberがただの値ではなく、「何回何かをするか」を決める関数だったら…？それがChurch Numeralsの考え方です！
Church Numeralsとは？
// Church Numberは、関数`f`を特定の回数適用する関数です。
type ChurchNumber = <T>(f: (x: T) => T) => (x: T) => T;
一見難しそうですが、実際に使ってみるとシンプルです。
const zero: ChurchNumber = (f) => (x) => x; // `f`を0回適用
const one: ChurchNumber = (f) => (x) => f(x); // `f`を1回適用
const two: ChurchNumber = (f) => (x) => f(f(x)); // `f`を2回適用
それぞれの数は、「関数fを何回適用するか」を表しています。面白いですよね？ 😎
Church Numberの足し算
もちろん、足し算もできます！
足し算の仕組み
2つのChurch Number N と M を足すとは、「fをN+M回適用すること」と同じ。
const add = (n: ChurchNumber, m: ChurchNumber): ChurchNumber =>
(f) => (x) => n(f)(m(f)(x));
仕組みを分解
-
m(f)(x)はfを M回 適用 -
n(f)はfを N回 適用 -
n(f)(m(f)(x))で N + M回 適用される
例: 1 + 2
const one: ChurchNumber = (f) => (x) => f(x);
const two: ChurchNumber = (f) => (x) => f(f(x));
const three = add(one, two);
これを展開すると…
three = (f) => (x) => one(f)(two(f)(x));
-
two(f)(x)→f(f(x))（fを2回適用） -
one(f)(two(f)(x))→f(two(f)(x))→f(f(f(x)))（fを1回追加）
結果として three(f)(x) = f(f(f(x))) になり、3 を表していることが分かります！ ✅
動作確認
const increment = (n: number) => n + 1;
const zeroValue = 0;
console.log(three(increment)(zeroValue)); // 3
ちゃんと3になりました！ 🎉
Church Boolean: TrueとFalseも関数で！
Booleanも関数だけで表現できます！
Church Booleanの定義
type ChurchBoolean = <T>(a: T) => (b: T) => T;
const TRUE: ChurchBoolean = (a) => (b) => a;
const FALSE: ChurchBoolean = (a) => (b) => b;
動作の仕組み
-
TRUE(a, b) = a→ 常に最初の引数を返す -
FALSE(a, b) = b→ 常に2番目の引数を返す
これによって、条件分岐（Conditional Logic）を関数だけで実現できます！
論理積（AND）
const AND = (p: ChurchBoolean, q: ChurchBoolean): ChurchBoolean =>
(x) => (y) => p(q(x)(y))(y);
-
pがTRUEの場合 →q(x, y)を評価（つまりqをそのまま返す） -
pがFALSEの場合 →yを返す（FALSE）
例
console.log(AND(TRUE, TRUE)("Yes")("No")); // "Yes" (TRUE)
console.log(AND(TRUE, FALSE)("Yes")("No")); // "No" (FALSE)
console.log(AND(FALSE, TRUE)("Yes")("No")); // "No" (FALSE)
console.log(AND(FALSE, FALSE)("Yes")("No"));// "No" (FALSE)
論理和（OR）
const OR = (p: ChurchBoolean, q: ChurchBoolean): ChurchBoolean =>
(x) => (y) => p(x)(q(x)(y));
-
pがTRUEの場合 → 即座にx（TRUE）を返す -
pがFALSEの場合 →q(x, y)を評価（つまりqの結果を返す）
例
console.log(OR(TRUE, TRUE)("Yes")("No")); // "Yes" (TRUE)
console.log(OR(TRUE, FALSE)("Yes")("No")); // "Yes" (TRUE)
console.log(OR(FALSE, TRUE)("Yes")("No")); // "Yes" (TRUE)
console.log(OR(FALSE, FALSE)("Yes")("No"));// "No" (FALSE)
論理（NOT）
const NOT = (p: ChurchBoolean): ChurchBoolean =>
(x) => (y) => p(y)(x);
-
NOT(p)は引数xとyを入れ替えます。 -
pがTRUEの場合、通常はxを返しますが、NOTを適用するとyを返す（これはFALSEを表します）。 -
pがFALSEの場合、xを返す（これはTRUEを表します）。
このようにして、Boolean の値を適切に反転できます。
例
console.log(NOT(TRUE)("Yes")("No")); // "No" (FALSE)
console.log(NOT(FALSE)("Yes")("No")); // "Yes" (TRUE)
まとめ
Church NumeralとChurch Booleanを使えば、プリミティブなNumberやBooleanを使わずに、関数だけで表現できます！これは関数型プログラミングやλ計算の基礎であり、計算の本質を理解する助けになります。
次回は、関数だけでデータ構造を作る方法を紹介します！お楽しみに！ 🚀
Discussion