Zコンビネータを思いつきたい
2024/01/22
友達とラムダ計算の話をしていて、Zコンビネータを天下り的に与えられるのが納得できなかったので、導出を追いかけようと思います。
普通の再帰関数
nの階乗を求める関数fを、再帰を使って普通に書いてみます。
const f = (n) => (n === 0 ? 1 : n * f(n - 1));今回の目標は、代入を使わずにfを実装することです。上記のコードはconst f = と書いているのでダメです。
代入を使わずに再帰する
代入が使えないということで、とりあえずconst f = を削除してみます。
(n) => (n === 0 ? 1 : n * f(n - 1));このコードは動きません。fがどこにもないからです。
ラムダ計算という関数しかない世界で、fをどこかからもらってくるには、引数で受け取るしかないはずです。(f) => を先頭に追加します。
(f) => (n) => n === 0 ? 1 : n * f(n - 1);この新しい関数をgと呼ぶことにします。
gの定義：
(f) => (n) => n === 0 ? 1 : n * f(n - 1)gは、fを受け取ってfを返す関数です。引数はそのままfであり、戻り値である(n) => n === 0 ? 1 : n * f(n - 1)もまたfの実装そのものだからです。
以下のようにして、gに名前を付けて扱いやすくします。
// prettier-ignore
(
(g) => g
// ^ gを受け取る
)
(
// gを渡す
(f) => (n) => n === 0 ? 1 : n * f(n - 1)
);(g) => gはgをそのまま返しているので、上記のコードを評価するとgになります。目標はfを実装することなので、ここでなんとかしてfを返せないか考えます。
gは、fを受け取ってfを返す関数でした。なのでg(f)とすればfが得られます。しかし、ここにはfが無いので無理です。
// prettier-ignore
(
(g) => g(f)
// ^ fはないのでダメ
)
(
// g
(f) => (n) => n === 0 ? 1 : n * f(n - 1)
);ここにあるのはgだけです。うーん、なんとかg(g)みたいな感じでfが得られるようにできないかな？と考えます。
そういう都合の良い関数hの定義を考えてみます。
hの定義（不完全）：
(h) => (n) => n === 0 ? 1 : n * ???(n - 1)hは、hを受け取ってfを返す関数です。h(h)とするとfが得られるので都合が良いですね。
???の部分が問題です。以前はfと書いていましたが、ここにはfはありません。
しかしhはあるので、h(h)とすることでfが得られると気づきます。そのようにhを定義したからです。
したがって、hは以下のように定義できます。
hの定義：
(h) => (n) => n === 0 ? 1 : n * h(h)(n - 1)これを使って先程のコードのgをhに置き換えます。
// prettier-ignore
(
(h) => h(h)
// ^^^^ fを返せた！
)
(
// h
(h) => (n) => n === 0 ? 1 : n * h(h)(n - 1)
);これは実際に動きます。以下のコードは120に評価されます。
// prettier-ignore
(
(h) => h(h)
)
(
// h
(h) => (n) => n === 0 ? 1 : n * h(h)(n - 1)
)
(5); // 120に評価されるすごい！1
リファクタリング
現時点でも目標は達成なのですが、もうちょっとリファクタリングしてみます。
というのも、(n) => n === 0 ? 1 : n * h(h)(n - 1)の中でh(h)しているのが嫌です。階乗のロジックの中に再帰の都合のコードが混ざっている感じがするからです。
というわけで、hを受け取った直後を関数でくるんで、h(h)と階乗のロジックを分離します。
// prettier-ignore
(
(h) => h(h)
)
(
// リファクタ中のh
(h) =>
((f) => (n) => n === 0 ? 1 : n * f(n - 1))
// ^ fを受け取る
// ^ 単にfと書ける
(h(h))
// ^^^^ fを生成して渡す *1
);残念ながらこれは関数呼び出しが無限に発生してしまい動作しません。
JavaScriptでは引数部分が適用よりも前に評価されます（適用順序、作用的順序）。リファクタ中のhにhを渡すと、まず引数である*1部分のh(h)が評価されます。しかしそのh(h)もまたhにhを渡しているので、内部のh(h)が評価されて……というように無限に続いてしまいます。
これを回避するために、*1部分を関数でくるんで、評価を遅延させます。
くるんだ後もこれはfとして振る舞ってほしいです。なのでまず引数はnです。次に戻り値については、階乗の計算結果f(n)であるべきで、h(h)がfなので、h(h)(n)と書けます。
// prettier-ignore
(
(h) => h(h)
)
(
(h) =>
((f) => (n) => n === 0 ? 1 : n * f(n - 1)) // *2
// ^ ここでfを適用するまで↓のh(h)の評価が遅延される
((n) => h(h)(n))
// ^^^^ hの定義よりf
// ^^^^^^^^^^^^^^ (n) => f(n)、つまりfと同じ
);ここで、*2の部分がgの定義と同じだと気づきます。これを外側から与えてやるようにします。
// prettier-ignore
(
(g) =>
// ^ gを受け取る
(
(h) => h(h)
)
(
(h) =>
(g)
// ^ 単にgと書ける *3
((n) => h(h)(n))
)
)
(
// gを渡す
(f) => (n) => n === 0 ? 1 : n * f(n - 1)
);*3付近の無駄なカッコを消して整理します。
// prettier-ignore
(
(g) =>
(
(h) => h(h) // *4
)
(
(h) => g((n) => h(h)(n)) // *5
)
)
(
// g
(f) => (n) => n === 0 ? 1 : n * f(n - 1)
);*4と*5の行は見た目が似ていることに気づきます。実際、これらはどちらもhを受け取ってfを返すという、同じことをしています。
*4についてはh(h)を返しているため、hの定義より自明ですね。*5については、まず(n) => h(h)(n)がfとなるように先程作ったことを思い出します。そしてそれをgに与えているため、gの定義よりfを返しているとわかります。
というわけで、*4を*5で書き換えても大丈夫そうです。そのほうが長くなってしまいますが、対称性があってきれいなのでそうしてみます。
// prettier-ignore
(
// Z
(g) =>
(
(h) => g((n) => h(h)(n))
)
(
(h) => g((n) => h(h)(n))
)
)
(
// g
(f) => (n) => n === 0 ? 1 : n * f(n - 1)
);これでZコンビネータが現れました。
Wikipediaに書かれてるZコンビネータと比べると、引数の名前が違うだけで等価であるとわかります。
// 今回求めたZコンビネータ
(g) => ((h) => g((n) => h(h)(n)))((h) => g((n) => h(h)(n)));
// Wikipediaのやつ
(f) => ((x) => f((y) => x(x)(y)))((x) => f((y) => x(x)(y)));階乗に限らず、再帰したい関数をgの形で実装し、それに(g) => ((h) => g((n) => h(h)(n)))((h) => g((n) => h(h)(n)))を適用すれば、関数だけで再帰し放題なので勝ちです。
おまけ
TypeScriptには再帰型があるので、Zコンビネータにも型を付けられます。
nという命名は階乗に限った話なので、argに置き換えました。
type F<Arg, Result> = (arg: Arg) => Result;
type G<Arg, Result> = (f: F<Arg, Result>) => F<Arg, Result>;
type H<Arg, Result> = (h: H<Arg, Result>) => F<Arg, Result>;
const z = <Arg, Result>(g: G<Arg, Result>) =>
((h) => g((arg) => h(h)(arg)))((h: H<Arg, Result>) => g((arg) => h(h)(arg)));
const fib: F<number, number> = z((fib) => (n) => n === 1 ? 1 : n * fib(n - 1));
console.log(fib(5)); // 120予備知識が無い状態で上記の型を書くのは難しいでしょう。導出を理解することで、とても直感的に書けているのがわかります。
まとめ
Zコンビネータを思いついてみました。ウソです。
実際はいろいろな資料を参考にした上で、めちゃくちゃ噛み砕いた説明を自分なりにまとめただけでした。
これを無から生成しちゃう人がいるってやばいっすね。
参考資料
- 誰得UNIX: Yコンビネータを導出してみる
- 完全には理解できていないですが、多分今回の説明と同じ流れのことをやっているようで大変参考になりました。
- チョウゲンボウとホシムクドリから賢人鳥を導出する
- まったく理解できていないですが、いつかは僕も鳥を愛でたいなと思いました。
- これに似た形がSICPの練習問題 4.21に登場します。問題を解いていた当初は感覚でコードを書いていましたが、こうして導出を追ってみると納得です。↩
