無名再帰のうち自己再帰の例はすぐ見つかるが、相互再帰ができるのかよくわからなかったので調べた。
（コードを写した程度であり、理論や本当に合っているかはわかっていない）
言語としてはJavaScript（ECMAScript 2015）を使う。理由は以下の通り。
- アロー関数によって短く書ける
- ブラウザの「開発者ツール」ですぐに試せる
関数型言語とかよくわからない
無名関数
軽く復習する。
関数の名前
JavaScriptでは関数もオブジェクト。関数の作成時に名前を書かなくても、適当な変数に代入すれば 変数名(引数) で呼び出せる。関数そのものの名前1は重要でなく、関数オブジェクトを指し示す変数の名前が重要。さらに言えば、 変数名 の部分を関数オブジェクトそのものに置き換えても構わない。
function func1(num) {
return "Hello, world" + "!".repeat(num);
}
func1(3);
func2 = function(num) {
return "Hello, world" + "!".repeat(num);
};
func2(4);
アロー関数なら、ほぼ同じことを短く書ける。
func3 = (num) => { return "Hello, world" + "!".repeat(num); };
// 仮引数が1個なら括弧不要、式を返すだけならreturn不要
func4 = num => "Hello, world" + "!".repeat(num) ;
利用法
関数を使い捨てる場合にはわざわざ変数に代入しなくていい。
関数を引数にする場合
[1, 2, 3].map(num => "Hello, world" + "!".repeat(num));
// => ["Hello, world!",
// "Hello, world!!",
// "Hello, world!!!"]
関数を戻り値にする場合
createFunction = () => num => "Hello, world" + "!".repeat(num);
createFunction()(7);
// => "Hello, world!!!!!!!"
// functionで書き直した場合
createFunction = function() {
return function(num) {
return "Hello, world" + "!".repeat(num);
};
};
即時実行関数
(num => "Hello, world" + "!".repeat(num))(10);
// => "Hello, world!!!!!!!!!!"
再帰での問題
関数に名前がついていないと、関数の中から再帰的に呼び出すことができない。
(function fact(n) { return n === 0 ? 1 : n * fact(n - 1) })(5);
// => 120
(n => n === 0 ? 1 : n * fact(n - 1))(5);
// => Uncaught ReferenceError: fact is not defined
となると無名関数で再帰はできない…わけではなく方法がある。
不動点コンビネータ
無名再帰を実現する方法。「関数を引数にとり新しい関数を返す」関数を駆使する。
基本形（Zコンビネータ）
有名なYコンビネータは引数が遅延評価される場合でないといけないので、それを変形したZコンビネータを使う2。
// 関数の名前付け（名前付き関数式や変数への代入）が一切ない！
(f => (u => u(u))(x => f(y => x(x)(y))))(
fact => n => n === 0 ? 1 : n * fact(n - 1)
)(5);
// 分解した形
const Z = f => (u => u(u))(x => f(y => x(x)(y)));
recFunc = Z(fact => n => n === 0 ? 1 : n * fact(n - 1));
recFunc(5);
再帰関数の引数が2個以上の場合
階乗と同じノリで書こうとするとエラーになる。これは、前節のZコンビネータが1引数の再帰関数にしか対応していないため。
// Zコンビネータは先程のを流用
recFunc = Z(gcd => (a, b) => b === 0 ? Math.abs(a) : gcd(b, a % b));
recFunc(1920, 1080);
// => Uncaught RangeError: Maximum call stack size exceeded
対処方法はいくつかある。
カリー化する
たぶん正攻法。関数を呼ぶと「引数をひとつ埋めた新しい関数」を作って返してくるようにする。これによって1引数の関数だけに書き直せる。
recFunc = Z(gcd => a => b => b === 0 ? Math.abs(a) : gcd(b)(a % b));
recFunc(1920)(1080);
引数を1個の配列にする
特別な知識が無くてもできる対応。格好悪いが、次節への準備として載せておく。
recFunc = Z(gcd => args => args[1] === 0 ? Math.abs(args[0]) : gcd([args[1], args[0] % args[1]]));
recFunc([1920, 1080]);
可変長引数に対応させる
配列から発展させると、再帰関数を普通に書けるようになる。
JavaScriptでは残余引数などの仕組みがあるので、不動点コンビネータ側で可変長引数に対応もできる。変更点は y を ...y にするだけ。なおアロー関数においては、仮引数が1個という扱いにならないので括弧が必要。
(f => (u => u(u))(x => f((...y) => x(x)(...y))))(
gcd => (a, b) => b === 0 ? Math.abs(a) : gcd(b, a % b)
)(1920, 1080);
// 分解した形
const Zn = f => (u => u(u))(x => f((...y) => x(x)(...y)));
recFunc = Zn(gcd => (a, b) => b === 0 ? Math.abs(a) : gcd(b, a % b));
recFunc(1920, 1080);
本題：相互再帰
引数ではなく再帰関数自体を複数にしたい。そのためのコンビネータは Y* というらしい。これでなぜ動くのか、そもそも合っているのかはわからない。
((...fs) => (u => u(u))(x => fs.map(f => (...y) => f(...x(x))(...y))))(
(e, o) => n => n === 0 || o(n - 1), // isEven
(e, o) => n => n !== 0 && e(n - 1) // isOdd
)[0](42); // isEven(42)
// 分解した形
const Zs = (...fs) => (u => u(u))(x => fs.map(f => (...y) => f(...x(x))(...y)));
[isEven, isOdd] =
Zs((e, o) => n => n === 0 || o(n - 1),
(e, o) => n => n !== 0 && e(n - 1));
isEven(42);
この Zs は（再帰関数を配列で返すことを除いて） Z や Zn の上位互換なので、自己再帰の例ももちろん実行できる。
Zs(fact => n => n === 0 ? 1 : n * fact(n - 1))[0](5);
Zs(gcd => a => b => b === 0 ? Math.abs(a) : gcd(b)(a % b))[0](1920)(1080); // カリー化
Zs(gcd => (a, b) => b === 0 ? Math.abs(a) : gcd(b, a % b))[0](1920, 1080); // 可変長引数
参考
- 不動点コンビネータ - Wikipedia
-
Fixed-point combinator - Wikipedia
- Many faces of the fixed-point combinator ： ここのScheme版をJavaScriptに翻訳した…つもり
- recursion - Fixed point combinator for mutually recursive functions? - Stack Overflow
- アロー関数 - JavaScript | MDN
- 関数式 - JavaScript | MDN