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