JavaScriptを使って、チャーチ数で遊びましょう。
チャーチ数とは、関数で自然数を表現したものです。
ここでは、JavaScriptを使ってチャーチ数を定義し、初等的な計算を行います。
チャーチ数
チャーチ数 (Church numerals) とは、自然数 $n$ を
「関数 $f$ を『$f$ を $n$ 回適用する関数』に写す関数」
として定義するものです。
例えばJavaScriptを使って 2 をチャーチ数として表すと
const two = f => x => f(f(x));
となります。two(f) は、f を 2 回適用する関数となっていますね。
(=> について知らない方は「JavaScript アロー関数」で検索してみてください)
0 から 3 までをチャーチ数として表すと
const zero = f => x => x;
const one = f => x => f(x);
const two = f => x => f(f(x));
const three = f => x => f(f(f(x)));
となります。
チャーチ数の確認
チャーチ数は関数ですので、そのままコンソールに出力しても値がよくわかりません。
チャーチ数を自然数に変換するため、以下の関数を使いましょう。
const evaluate = n => n(x => x + 1)(0);
例えば evaluate(two) は、 0 に対し x => x + 1 を 2 回適用した結果ですから、結果は 2 となります。
console.log(evaluate(two)); // 2
注意
以降、チャーチ数 n とこれに対応する自然数を同一視して「n 回」という表現を使うことがあります。
チャーチ数の後者(successor)
まず、自然数の 後者 (successor) とは、平たく言うと「次の自然数」のことです。
自然数 n の後者は n + 1 です。
チャーチ数の後者は、以下の関数で定義できます。
const succ = n => f => x => f(n(f)(x));
チャーチ数 n の後者が succ(n) で得られることを確認しましょう。
n(f) は、 f を n 回適用する関数でしたね。
一方 succ(n)(f)、つまり x => f(n(f)(x)) は f を n + 1 回適用する関数です。
このことから succ(n) は n の後者であるといえます。
succ を使うと、1 から 3 までのチャーチ数は以下のように書き直すことができます。
const zero = f => x => x;
const one = succ(zero);
const two = succ(one);
const three = succ(two);
チャーチ数の計算
チャーチ数同士で初等的な計算をしてみましょう。
結論から書くと、チャーチ数の和、積、べき乗は以下の関数で定義できます。
const add = m => n => f => x => n(f)(m(f)(x));
const mul = m => n => f => x => n(m(f))(x);
const pow = m => n => f => x => n(m)(f)(x);
順を追って説明します。
チャーチ数の和
チャーチ数の和は以下の関数で定義できます。
const add = m => n => f => x => n(f)(m(f)(x));
チャーチ数 m と n の和が add(m)(n) で得られることを確認しましょう。
n(f)(m(f)(x)) は、 x に対し f を m 回適用し、さらに n 回適用したもの、つまり fを m + n 回適用したものです。
このことから add(m)(n)、つまり f => x => n(f)(m(f)(x)) は m と n の和であるといえます。
実際にチャーチ数の和を計算してみましょう。
console.log(evaluate(add(two)(three))); // 2 + 3 = 5
チャーチ数の積
チャーチ数の積は以下の関数で定義できます。
const mul = m => n => f => x => n(m(f))(x);
より簡潔に書くと
const mul = m => n => f => n(m(f));
となります。
チャーチ数 m と n の積が mul(m)(n) で得られることを確認しましょう。
n(m(f)) は『「f を m 回適用する関数」を n 回適用する関数』です。
m 回を n 回、これはつまり 「f を m * n 回適用する関数」ですね。
このことから mul(m)(n)、つまり f => n(m(f)) は m と n の積であるといえます。
実際にチャーチ数の積を計算してみましょう。
console.log(evaluate(mul(two)(three))); // 2 * 3 = 6
チャーチ数のべき乗
チャーチ数のべき乗は以下の関数で定義できます。
const pow = m => n => f => x => n(m)(f)(x);
より簡潔に書くと
const pow = m => n => n(m);
となります。
和や積と比べて複雑かと思いきや、定義自体は驚くほどシンプルですね。
チャーチ数 m の n 乗が pow(m)(n) で得られることを確認しましょう。
n(m) は「m を n 回適用する関数」です。
m を 1 回適用するごとに関数 f の個数は m 倍になりますから、
m を n 回適用すると f は m の n 乗個に増えます。
このことから pow(m)(n)、つまり n(m) は m の n 乗であるといえます。
定義自体はシンプルですが、頭が痛くなりますね。
実際にチャーチ数のべき乗を計算してみましょう。
console.log(evaluate(pow(two)(three))); // 2 ^ 3 = 8
まとめ
これまでやったことを1つのコードにまとめると、以下のようになります。
const succ = n => f => x => f(n(f)(x));
const zero = f => x => x;
const one = succ(zero);
const two = succ(one);
const three = succ(two);
const evaluate = n => n(x => x + 1)(0);
console.log(evaluate(two)); // 2
const add = m => n => f => x => n(f)(m(f)(x));
const mul = m => n => f => x => n(m(f))(x);
const pow = m => n => f => x => n(m)(f)(x);
console.log(evaluate(add(two)(three))); // 2 + 3 = 5
console.log(evaluate(mul(two)(three))); // 2 * 3 = 6
console.log(evaluate(pow(two)(three))); // 2 ^ 3 = 8
チャーチ数への興味が出た方は、これを機に「チャーチ数」や「ラムダ計算」で検索してみてください。