不動点コンビネータで無名再帰を作る流れをおさらい with JavaScript

この記事は はてなエンジニア Advent Calendar 2024 の 2 日目の記事です。
昨日は id:hogashi さんの「querySelectorAllの結果をmapしたいときはArray.fromすると良い」でした。

どうも、趣味で関数型言語をやっている者です。
長らく関数型言語をやってなかったら無名再帰を忘れかけていたので、おさらいがてら不動点コンビネータで無名再帰を作る流れを書き下します。

以下、JavaScript の文法で書かれたコードをもとに説明していきます。

目次

無名再帰とは

まずはモチベーションの確認から。
通常、再帰関数は、

function sum(nums) {
  if (nums.length === 0) {
    return 0;
  } else {
    const num = nums.pop();
    return num + sum(nums);
  }
}

といったように、関数定義の中で自分自身を呼ぶことで再帰処理を記述できます。
この例では、 return num + sum(nums); の部分で自分自身を呼んでいますね。

では、以下のような制約をイメージしてみてください。

• 関数に名前を付けることができない
• 関数定義の中で自分自身を呼ぶことができない

このような制限の中で再帰を書きたくなったらどうすればいいでしょうか？
そんな要望に応えるために人類は 無名再帰 という方法を編み出しました。その名の通り、関数名に依らない再帰処理の方法です。

今回は無名再帰の具体的な作り方を見ていきます。

不動点コンビネータ (Z コンビネータ)

いきなりですが 不動点コンビネータ というやつがあります。
関数を変換する関数 (高階関数) の形をしています。定義はこうです。

const fix = f => (g => g(g))(h => f(y => h(h)(y)));

なんだこれはって感じですね。落ち着いて fix(f) がどのように展開されるか見てみましょう。

fix(f)
→ (f => (g => g(g))(h => f(y => h(h)(y))))(f)
→ (g => g(g))(h => f(y => h(h)(y)))
→ (h => f(y => h(h)(y)))(h => f(y => h(h)(y)))
→ f(y => (h => f(y => h(h)(y)))(h => f(y => h(h)(y)))(y))
    = f(y => fix(f)(y))

fix(f) = f(y => fix(f)(y)) という関係が見えました。とはいえ、まだちょっと何がしたいのか分からない感じの関数ですね。

こんどはもっと具体的に f に特定の関数を代入してみましょう。

f = next => x => next(x) の場合

f = next => x => next(x) のときの fix(f)(0) を考えます。

const fix = f => (g => g(g))(h => f(y => h(h)(y)));
// fix(f) = f(y => fix(f)(y))
const f = next => x => next(x);

fix(f)(0)

// fix(f) の定義を展開
→ f(y => fix(f)(y))(0)

// f の定義を展開
→ (next => x => next(x))(y => fix(f)(y))(0)

// 無名関数を評価する
→ (x => (y => fix(f)(y))(x))(0)
→ (y => fix(f)(y))(0)

→ fix(f)(0)

なんと fix(f)(0) を評価すると再び fix(f)(0) が現れました。
関数を実行しようとすると同じ関数の実行に行き着くので、このプログラムは延々と同じ関数を呼び出し続けることになります。

この 関数の呼び出しが延々と繰り返される というやつは、実際にやってみると 処理が無限にループして停止しない という扱いになるでしょう。

ブラウザで fix(f)(0) を実行したときに表示されるエラー

そんな関数が役に立つのか？
大丈夫、もう少し別の例を見ていきましょう。

f = next => x => next(x + 1) の場合

f = next => x => next(x + 1) のときを考えましょう。
さきほどととても似ていますが x + 1 と足し算をしています。

const fix = f => (g => g(g))(h => f(y => h(h)(y)));
// fix(f) = f(y => fix(f)(y))
const f = next => x => next(x + 1);

fix(f)(0)
→ f(y => fix(f)(y))(0)
→ (next => x => next(x + 1))(y => fix(f)(y))(0)
→ (x => (y => fix(f)(y))(x + 1))(0)
→ (y => fix(f)(y))(0 + 1)
→ fix(f)(0 + 1)
→ fix(f)(1)

fix(f)(0) が評価されて fix(f)(1) になりました。
再度 fix(f)(1) を評価すると fix(f)(2) になります。さらに繰り返せば fix(f)(3) になります。

const fix = f => (g => g(g))(h => f(y => h(h)(y)));
// fix(f) = f(y => fix(f)(y))
const f = next => x => next(x + 1);

fix(f)(0)
→ ...
→ fix(f)(1)
→ ...
→ fix(f)(1 + 1)
→ fix(f)(2)
→ ...
→ fix(f)(2 + 1)
→ fix(f)(3)
→ ...

同じ関数を呼び出し続けているという点では先ほどの同じで。この例でも関数の実行は停止せずにエラーになります。
ただ今度は引数の部分で計算が行われているので、何か 再帰処理されている感じ が持てますね。

f = next => x => x > 1 ? x : next(x + 1) の場合

もう一歩踏み込んで条件分岐を加えてみましょう。
f = next => x => x > 1 ? x : next(x + 1) について考えます。

const fix = f => (g => g(g))(h => f(y => h(h)(y)));
// fix(f) = f(y => fix(f)(y))
const f = next => x => x > 1 ? x : next(x + 1);

fix(f)(0)
→ f(y => fix(f)(y))(0)
→ (next => x => x > 1 ? x : next(x + 1))(y => fix(f)(y))(0)
→ (x => x > 1 ? x : (y => fix(f)(y))(x + 1))(0)
→ 0 > 1 ? 0 : (y => fix(f)(y))(0 + 1)
→ (y => fix(f)(y))(0 + 1)
→ fix(f)(0 + 1)
→ fix(f)(1)
→ ...
→ fix(f)(2)
→ ...
→ (x => x > 1 ? x : (y => fix(f)(y))(x + 1))(2)
→ 2 > 1 ? 2 : (y => fix(f)(y))(2 + 1)
→ 2

ついに無限の関数呼び出しを回避できました。
ブラウザで実行してみても同じ結果が得られます。

エラーは無い

f がどんな式だったかもう一度見てみましょう。

const f = next => x => x > 1 ? x : next(x + 1);

種明かしすると next(~) の部分が再帰呼び出しに相当しています。
条件分岐を追加して next(~) ã‚’ 呼び出さない ことで再帰を打ち切ることができるのです。

この挙動を手続的に書いてみるとこんな感じになるはずです。

let x = 0;
while (true) {
  if (x > 2) {
    return x;
  } else {
    x += 1;
  }
}

どうでしょう？条件分岐を組み込んだ式 f を渡すことで 何か実用的な式を組み立てられそうな気がしてきた と思いませんか？

実用的な計算例: 階乗計算

いよいよ不動点コンビネータを使った実用的な例を見ていきましょう。
0以上の自然数 n の階乗 fact(n)を計算してみます。

まず階乗関数 fact を定義するための補助関数 _fact を次のように定義します。

const _fact = next => n => n === 1 ? 1 : n * next(n - 1);

これを fix に与えて展開してみましょう。

const fix = f => (g => g(g))(h => f(y => h(h)(y)));
// fix(f) = f(y => fix(f)(y))
const _fact = next => n => n === 1 ? 1 : n * next(n - 1);

fix(_fact)
→ (f(y => fix(f)(y)))(_fact)
→ _fact(y =>  fix(_fact)(y))
→ (next => n => n === 1 ? 1 : n * next(n - 1))(y =>  fix(_fact)(y))
→ n => n === 1 ? 1 : n * (y =>  fix(_fact)(y))(n - 1)

はい！ 三項演算子の else 節に注目してください fix(_fact)(y) という形で再帰的構造が見えていますね。

n にも具体的な値を入れてみましょう。 fix(_fact)(3) を展開します。

fix(_fact)(3)

// fix の定義に従い fix(_fact) を展開
→ _fact(y => fix(_fact)(y))(3)

// _fact の定義に従い式を展開
→ (next => n => n === 1 ? 1 : n * next(n - 1))(y => fix(_fact)(y))(3)
→ (n => n === 1 ? 1 : n * (y => fix(_fact)(y))(n - 1))(3)
→ 3 === 1 ? 1 : 3 * (y => fix(_fact)(y))(3 - 1)

// 三項演算子を評価
→ 3 * (y => fix(_fact)(y))(3 - 1)

// 3 - 1 を評価
→ 3 * (y => fix(_fact)(y))(2)
→ 3 * fix(_fact)(2)

// 以下、繰り返し
→ 3 * _fact(y => fix(_fact)(y))(2)
→ 3 * (next => n => n === 1 ? 1 : n * next(n - 1))(y => fix(_fact)(y))(2)
→ 3 * (n => n === 1 ? 1 : n * (y => fix(_fact)(y))(n - 1))(2)
→ 3 * (2 === 1 ? 1 : 2 * (y => fix(_fact)(y))(2 - 1))
→ 3 * 2 * (y => fix(_fact)(y))(2 - 1)
→ 3 * 2 * (y => fix(_fact)(y))(1)
→ 3 * 2 * fix(_fact)(1)

→ 3 * 2 * _fact(y => fix(_fact)(y))(1)
→ 3 * 2 * (next => n => n === 1 ? 1 : n * next(n - 1))(y => fix(_fact)(y))(1)
→ 3 * 2 * (n => n === 1 ? 1 : n * (y => fix(_fact)(y))(n - 1))(1)
→ 3 * 2 * (1 === 1 ? 1 : 1 * (y => fix(_fact)(y))(1 - 1))
→ 3 * 2 * 1

→ 6

ふぅ、お疲れさまでした。fix(_fact)(3) が 3 * 2 * 1 に展開される様子が見えて、まさに階乗計算している感じですね。

さてfix(_fact)(n) で n の階乗が計算できることが分かったので、

const fix = f => (g => g(g))(h => f(y => h(h)(y)));
const _fact = next => n => n === 1 ? 1 : n * next(n - 1);
const fact = fix(_fact);

として階乗関数 fact() を定義することができました。

実際に計算できている様子

 

何が起こっている？

あらためて _fact と fact の定義を見てみましょう。

const _fact = next => n => n === 1 ? 1 : n * next(n - 1);
const fact = fix(_fact);

_fact の定義にも fact の定義にも自分自身を呼び出す記述はありませんから、今回のテーマ通り 自分自身を呼び出すことなく再帰処理を実現できた ということになります。
さらに _fact の定義をよく見ていると仮引数の next をまるで再帰呼び出しのように使っていることが分かります。

形式的な知識としてはこうです。

• fix に関数 g を与えることで関数 f が得られる
• f は通常の1引数関数として振る舞う
• g の第一仮引数 next の呼び出しは、f の再帰呼び出しのように振る舞う

掴めてきましたか？実際に紙に手書きで運算してみるとより理解が深まるかも知れません。

2引数関数への展開

先ほどの例で見た fact() はただ一つの引数 n を取る1引数関数でした。
次に2引数関数を無名再帰で書く例を見てみましょう。

例に取り上げるのは自然数 m, n の最大公約数を求める関数 gcd(m, n) です。 ユークリッドの互除法 を使って計算します。

まずは名前再帰版です。

const gcd = (m, n) => n === 0 ? m : gcd(n, m % n);

gcd(1071, 1029);
// => 21

これを無名再帰で書きたいところですが困ったことがあります。さきほど紹介した不動点コンビネータ fix は1引数関数を作るときにしか使えないのです。

上手く機能していない

問題の解決策を3つ紹介します。

解決策1: 2引数版の不動点コンビネータを使う

const fix2 = f => (g => g(g))(h => f((x, y) => h(h)(x, y)));

この不動点コンビネータ fix2 は先ほどまで見てきた fix の2引数版です。
使い方は fix と変わりません。

const fix2 = f => (g => g(g))(h => f((x, y) => h(h)(x, y)));
const _gcd = next => (m, n) => n === 0 ? m : next(n, m % n);
const gcd = fix2(_gcd);

gcd(1071, 1029);
// => 21

fix2 を使えば正しく機能する

もちろん3引数関数を書きたくなったら3引数版の fix3 が、4引数関数を書きたくなったら4引数版の fix4 が必要になります。少し面倒ですね。

// 3引数版
const fix3 = f => (g => g(g))(h => f((x, y, z) => h(h)(x, y, z)));

// 4引数版
const fix4 = f => (g => g(g))(h => f((x, y, z, w) => h(h)(x, y, z, w)));

解決策2: カリー化🍛する

カリー化 という方法を使うと多引数関数と同等のものを1引数関数だけで書くことが可能になります。
例として Math.pow(x, y) ã‚’1引数関数で表現すると、

const pow = x => y => Math.pow(x, y);

Math.pow(2, 4);
// => 16

pow(2)(4); // 呼び出し方が変わるので注意
// => 16

pow は1引数関数です。
ただし pow(2) の返り値もまた1引数関数になっています。引数を一つずつ渡して 2回呼び出す ことで2引数での呼び出しと同等の結果が得られます。

カリー化してしまえば全ての関数は1引数関数になるので、先ほどの gcd ã‚’1引数版の fix を使って定義できます。

const fix = f => (g => g(g))(h => f(x => h(h)(x)));
const _gcd = next => m => n => n === 0 ? m : next(n)(m % n);
const gcd = fix(_gcd);

gcd(1071)(1029); // カリー化によって呼び出し方が変わるので注意
// => 21

カリー化すれば複数の引数を扱える

解決策3: 1引数関数にタプルを渡すことで対応する

「2引数を受け取る関数」は「2要素のタプルを1つ受け取る関数」と同等です。
JavaScript にはタプルが無いので配列で代用すると。

const pow = ([x, y]) => Math.pow(x, y);

Math.pow(2, 4);
// => 16

pow([2, 4]); // 呼び出し方が変わるので注意
// => 16

Math.pow(x, y) と同等の計算をする1引数関数 pow([x, y]) が定義できました。

1引数版の fix を使って、タプル渡しの gcd 関数を定義してみましょう。

const fix = f => (g => g(g))(h => f(x => h(h)(x)));
const _gcd = next => ([m, n]) => n === 0 ? m : next([n, m % n]);
const gcd = fix(_gcd);

gcd([1071, 1029]); // タプル渡しで呼び出す
// => 21

ECMAScript 2015 の分割代入によってタプル渡しが書きやすくなった

どの方法でも2引数関数の無名再帰に上手く対応できていますね。

型はどうなってる？

ここまで見てきた不動点コンビネータ fix やそれを使って定義した無名再帰関数に適切に型付けできるのか気になりますよね？
なんと TypeScript なら fix に適切に型をつけることが可能です。

このようになります。

function fix<S, T>(f: (_: (_: S) => T) => (_: S) => T) {
  type U = (_: U) => (_: S) => T;
  return (g => g(g))((h: U) => f((y: S) => h(h)(y)));
}

型付きの fix を使って階乗関数 fact を書いた例を TypeScript Playground に用意しました。
_fact に最低限の型注釈をつけるだけで fact = fix(_fact) の型が正しく推論されています。

• TypeScript Playground

正しく fact: (_: number) => number と推論されている

まとめ

不動点コンビネータを使うと決まったパターンで無名再帰が実現できることを見てきました。
また多引数関数に応用することや TypeScript による型付けについても知ることができました。

ここで紹介した不動点コンビネータや無名再帰は計算機科学の始まりの頃から研究されてきたテーマです。コンビネータ理論を確立してくれた先人に感謝します。

私からは以上です。

余談

この記事は下記の記事とほぼ同じ内容を JavaScript で焼き直したものです。
下記の記事ではサンプルコードを Haskell で書いていましたが、「Haskell でサンプルコード書いて誰が読めんねん！」と思ったので JavaScript で書き直しました。

blog.mudatobunka.org

余談2

不動点コンビネータの型付けについては下記の記事を大いに参考にさせていただきました。

qiita.com