不動点コンビネータで無名相互再帰

**無名再帰**のうち自己再帰の例はすぐ見つかるが、**相互再帰**ができるのかよくわからなかったので調べた。

（コードを写した程度であり、理論や本当に合っているかはわかっていない）

---

言語としてはJavaScript（ECMAScript 2015）を使う。理由は以下の通り。

* アロー関数によって短く書ける
* ブラウザの「開発者ツール」ですぐに試せる
* ~~関数型言語とかよくわからない~~

## 無名関数
軽く復習する。

### 関数の名前
JavaScriptでは**関数もオブジェクト**。関数の作成時に名前を書かなくても、適当な変数に代入すれば `変数名(引数)` で呼び出せる。**関数そのものの名前[^name]は重要でなく**、関数オブジェクトを指し示す変数の名前が重要。さらに言えば、 `変数名` の部分を関数オブジェクトそのものに置き換えても構わない。

```javascript
function func1(num) {
	return "Hello, world" + "!".repeat(num);
}
func1(3);

func2 = function(num) {
	return "Hello, world" + "!".repeat(num);
};
func2(4);
```

アロー関数なら、ほぼ同じことを短く書ける。

```javascript
func3 = (num) => { return "Hello, world" + "!".repeat(num); };

// 仮引数が1個なら括弧不要、式を返すだけならreturn不要
func4 =  num  =>          "Hello, world" + "!".repeat(num)   ;
```

[^name]: `name` プロパティで参照できるもの。関数作成時に明示した名前か、無名の関数式を代入した変数の名前。

### 利用法
関数を使い捨てる場合にはわざわざ変数に代入しなくていい。

#### 関数を引数にする場合

```javascript
[1, 2, 3].map(num => "Hello, world" + "!".repeat(num));
// => ["Hello, world!",
//     "Hello, world!!",
//     "Hello, world!!!"]
```

#### 関数を戻り値にする場合

```javascript
createFunction = () => num => "Hello, world" + "!".repeat(num);
createFunction()(7);
// => "Hello, world!!!!!!!"

// functionで書き直した場合
createFunction = function() {
	return function(num) {
		return "Hello, world" + "!".repeat(num);
	};
};
```

#### 即時実行関数

```javascript
(num => "Hello, world" + "!".repeat(num))(10);
// => "Hello, world!!!!!!!!!!"
```

### 再帰での問題
関数に名前がついていないと、関数の中から再帰的に呼び出すことができない。

```javascript:階乗
(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コンビネータ**を使う[^uu]。

```javascript:階乗
// 関数の名前付け（名前付き関数式や変数への代入）が一切ない！
(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);
```

[^uu]: 短く書くため `u => u(u)` という関数を噛ませている。

### 再帰関数の引数が2個以上の場合
階乗と同じノリで書こうとするとエラーになる。これは、前節のZコンビネータが**1引数の再帰関数にしか対応していない**ため。

```javascript:最大公約数（ユークリッドの互除法）
// 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
```

対処方法はいくつかある。

#### [カリー化](https://ja.wikipedia.org/wiki/カリー化)する
たぶん正攻法。関数を呼ぶと「引数をひとつ埋めた新しい関数」を作って返してくるようにする。これによって**1引数の関数だけ**に書き直せる。

```javascript
recFunc = Z(gcd => a => b => b === 0 ? Math.abs(a) : gcd(b)(a % b));
recFunc(1920)(1080);
```

#### 引数を1個の配列にする
特別な知識が無くてもできる対応。格好悪いが、次節への準備として載せておく。

```javascript
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個という扱いにならないので括弧が必要。

```javascript
(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\*** というらしい。これでなぜ動くのか、そもそも合っているのかはわからない。

```javascript:偶奇判定
((...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` の上位互換なので、自己再帰の例ももちろん実行できる。

```javascript
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](https://ja.wikipedia.org/wiki/不動点コンビネータ)
* [Fixed-point combinator - Wikipedia](https://en.wikipedia.org/wiki/Fixed-point_combinator)
	* [Many faces of the fixed-point combinator](http://okmij.org/ftp/Computation/fixed-point-combinators.html) ： ここのScheme版をJavaScriptに翻訳した…つもり
	* [recursion - Fixed point combinator for mutually recursive functions? - Stack Overflow](https://stackoverflow.com/questions/4899113)
* [アロー関数 - JavaScript | MDN](https://developer.mozilla.org/ja/docs/Web/JavaScript/Reference/Functions/Arrow_functions)
* [関数式 - JavaScript | MDN](https://developer.mozilla.org/ja/docs/Web/JavaScript/Reference/Operators/function)