「不動点コンビネータ」 という概念はだいぶ昔から知っていて「おもしろいな」と思っていたものの、「なぜその方法で実現できているのか」が腑に落ちておらず、ふと思い立って TypeScript をごちゃごちゃいじりながら考えてみたというやつのまとめ。¹

不動点コンビネータの説明

例として「フィボナッチ数列の第N項を返す関数 fib」を作ることを考える。

const fib = (n) => (n <= 2 ? 1 : fib(n - 1) + fib(n - 2))

fib(10) //=> 55

できました。

えっ...？いやまぁ実用的なプログラミングならこんな風に再帰関数を書けば簡単に実現できるけども。

不動点コンビネータとかいうやつ、いらんかった...？

ラムダ計算にする

話のとっかかりとして、この関数を ラムダ計算 にしていくことを考えたい。ラムダ計算の正確な定義などはググってもらうとして、ここでは 「関数の引数は1つまで」「関数の引数以外に識別子を使用しない (関数名や変数名を使用しない)」 という制約の下で計算を行いたい、というものだと理解しておけばよさそう。

で、いろいろ省略するが、出来上がったものがこちら。²

((a) => ((b) => a((n) => b(b)(n)))((b) => a((n) => b(b)(n))))(
  (fib) => (n) => (n <= 2 ? 1 : fib(n - 1) + fib(n - 2))
)(10) //=> 55

わぁ、むずかしそう。

でも確かに再帰を使わずに再帰っぽい計算ができていることはわかる。なんかすごい。

分解して不動点コンビネータを切り出す

理解するために、これをちょっと分解してみるとこうなる。

const Z = (a) => ((b) => a((n) => b(b)(n)))((b) => a((n) => b(b)(n)))

const fib = Z((f) => (n) => (n <= 2 ? 1 : f(n - 1) + f(n - 2)))

fib(10) //=> 55

Z という謎の関数を作り、Z にフィボナッチ数列の計算ロジックをいれることで関数 fib が作られていることがわかる。

このような振る舞いをする関数のことを 不動点コンビネータ という。不動点コンビネータにはいくつか種類があるが、上記の Z 関数は Z コンビネータ (値呼び Y コンビネータ) として知られている。

Z コンビネータに型をふる

ちなみに TypeScript では Z コンビネータに型をふることができる。

const Z = <Arg, Res>(a: (_: (_: Arg) => Res) => (_: Arg) => Res) => {
  type B = (_: B) => (_: Arg) => Res
  return ((b: B) => a((n) => b(b)(n)))((b) => a((n) => b(b)(n)))
}

const fib = Z<number, number>((f) => (n) => (n <= 2 ? 1 : f(n - 1) + f(n - 2)))

fib(10) //=> 55

関数内で定義している type B がポイントで、この定義は再帰型になっているため、再帰型が表現できない型システムでは Z コンビネータに型をふることができないらしい。

不動点コンビネータの利点

不動点コンビネータを知っているとなにか便利なことがあるか？というと 1ミリもない。

不動点コンビネータにより、第一級関数をサポートしているプログラミング言語において、明示的に再帰を書かずに再帰を実現する為に用いる事ができる。なお、一般にそういった言語では普通に再帰が使えるので、プログラミングにおいてはパズル的なテクニック以上の意味は無い。 一方、循環なく関数の意味を定義する（できる）、ということは、 計算理論の上では重要である。
不動点コンビネータ - Wikipedia

でもまぁなんか面白いよね！！！

不動点コンビネータの仕組みを理解したい

TypeScript で Z コンビネータを作っていくことによって不動点コンビネータがどのように動いているのかを理解していきたい。

※ 以下でやるのは理論的にちゃんとした導出では全くなく、あくまで結論ありきでゴチャゴチャと思考した過程でしかないという点には留意してほしい。

1. 初期状態

初期状態はこんな感じ。

簡単のために、ここでは引数や返り値の方については型引数は使わずにハードコーディングしている。

type Arg = number // fib 関数の引数は項番号 (自然数) なので number
type Res = number // fib 関数の返り値は数値なので number
type Fn = (_: Arg) => Res // fib 関数の型

const Z = /* これを作っていく */

const fib = Z((fn: Fn) => (n: Arg) => (n <= 2 ? 1 : fn(n - 1) + fn(n - 2)))

fib(10) // ※ このコードはまだ完成していないので実行できない

この関数 Z を作っていきたい。

2. とりあえず Z 関数をつくる

Z は (_: Fn) => Fn を受け取って Fn を返す関数なので、まずはそのような関数を作ってみる。

type Arg = number
type Res = number
type Fn = (_: Arg) => Res
type A = (_: Fn) => Fn // Z コンビネータの引数の型

const Z = (a: A): Fn => a(/* 何らかの Fn 型関数 */)

const fib = Z((fn: Fn) => (n: Arg) => (n <= 2 ? 1 : fn(n - 1) + fn(n - 2)))

fib(10) // ※ このコードはまだ完成していないので実行できない

素直に考えると引数 a に fn を渡せば欲しい関数が得られるのだから、 a(fn) などと書いて返したいところだが、まだ fn (Fn 型のなにか) が入手できない。

3. 謎の関数 `B` を導入

突然だがここで 何かしら上位存在からのお告げがあった ということにして、謎の関数 B を導入する。

このとき、B は「自分自身 (つまり B) を入れると Fn を返す関数」ということにする。

type Arg = number
type Res = number
type Fn = (_: Arg) => Res
type A = (_: Fn) => Fn
type B = (_: B) => Fn // B 自身を入れると Fn を返す謎の関数！！

const Z = (a: A): Fn => {
  const b: B = (b) => {/* ここはあとで考える */}
  const fn = b(b) // b が作れてしまえば、定義より、b(b) は Fn 型を返すので、
  return fn // 関数 Z 最終的に Fn 型の "何か" は返せる、めでたしめでたし
}

const fib = Z((fn: Fn) => (n: Arg) => (n <= 2 ? 1 : fn(n - 1) + fn(n - 2)))

fib(10) // ※ このコードはまだ完成していないので実行できない

B 型の関数 b の中身をどう作るかはひとまず置いておくとして、b(b) を return することで、とりあえずは関数 Z が Fn の形をした何かを返すことができるようになった。

3. 関数 `b` の中身を考えていく

関数 b は Fn 型を返すように作りたい。

Fn 型は得る手段として「b(b)」があるが、これは使えないっぽい。(理由はうまく説明できない。) 試しに b(b) で実行してみると Maximum call stack size exceeded エラーが発生する。

しかし b(b) 以外で Fn を得る方法なんて... ｵｯ!? 都合よく関数 a がいますねぇ！

type Arg = number
type Res = number
type Fn = (_: Arg) => Res
type A = (_: Fn) => Fn
type B = (_: B) => Fn

const Z = (a: A): Fn => {
  const b: B = (b) => {
    const fn: Fn = (arg) => {/* ここはあとで考える */}
    return a(fn)
  }
  const fn = b(b)
  return fn
}

const fib = Z((fn: Fn) => (n: Arg) => (n <= 2 ? 1 : fn(n - 1) + fn(n - 2)))

fib(10) // ※ このコードはまだ完成していないので実行できない

関数 a の返り値は Fn 型なので、関数 a を実行した結果を返すことで、関数 b も Fn 型を返すことができるようになった。

しかし関数 a を call するには Fn 型の関数を渡さないといけないので、ここでは (arg) => {/* ここはあとで考える */} を渡している。

4. 関数 `a` の引数を考えていく

関数 b の中で定義している関数 fn の中身はどう実装していくか考える。

Fn 型の関数は Arg 型を受け取って Res 型を返す必要がある。

Fn 型の関数をどうやって用意するかはあとで考えるとして、何らかの Fn
型関数を call することにする。

type Arg = number
type Res = number
type Fn = (_: Arg) => Res
type A = (_: Fn) => Fn
type B = (_: B) => Fn

const Z = (a: A): Fn => {
  const b: B = (b) => {
    const fn: Fn = (arg) => {/* 何らかの Fn 型関数 */}(arg)
    return a(fn)
  }
  const fn = b(b)
  return fn
}

const fib = Z((fn: Fn) => (n: Arg) => (n <= 2 ? 1 : fn(n - 1) + fn(n - 2)))

fib(10) // ※ このコードはまだ完成していないので実行できない

5. 「何らかの `Fn` 型関数」を用意する

「何らかの Fn 型関数」として、関数 b 内で定義した fn 自身が存在しているが、これは使えない。(これを OK とするならただの再帰関数になってしまう)

じゃあ他に「何らかの Fn 型関数」って何が用意できるかというと、ここで満を持して b(b) の登場！！

type Arg = number
type Res = number
type Fn = (_: Arg) => Res
type A = (_: Fn) => Fn
type B = (_: B) => Fn

const Z = (a: A): Fn => {
  const b: B = (b) => {
    const fn: Fn = (arg) => b(b)(arg) // 満を持して b(b) の登場！
    return a(fn)
  }
  const fn = b(b)
  return fn
}

const fib = Z((fn: Fn) => (n: Arg) => (n <= 2 ? 1 : fn(n - 1) + fn(n - 2)))

fib(10) //=> 55

うごいた！！！

手順 (3.) で Fn 型関数が欲しかったときに b(b) は使えなかったのに、ここでは b(b) を使って良いのは何故だろう？？？という点は不思議であるものの、とにかく動いた。

さて、あらためて振り返ると、勝手に導入した「謎の関数 b」から得られる fn がなぜちゃんと計算してくれるのだろうか？ただ Fn の型をしているだけで、期待する振る舞いをするかどうかはわからないんじゃないの？と思う。

しかしできあがった実装を見てみると、関数 b はちゃんと関数 a を実行した結果得られた fn を返していることがわかる。関数 b の内部では a を実行したうえで Fn 型を返しているので、b(b) で得られる関数は「内部で (期待通りの) fn が束縛されている fn」になっているわけで、つまり問題ないということがわかる。(ここの説明が超むずかしい)

6. 整理する

理解しやすくするために作っていた変数を消していく。

type Arg = number
type Res = number
type Fn = (_: Arg) => Res
type A = (_: Fn) => Fn
type B = (_: B) => Fn

const Z = (a: A): Fn => {
  const b: B = (b) => a((arg) => b(b)(arg))
  return b(b)
}

const fib = Z((fn: Fn) => (n: Arg) => (n <= 2 ? 1 : fn(n - 1) + fn(n - 2)))

fib(10) //=> 55

まずはこんな感じ。

const b: B = も消したいが、変数 b は b(b) のところで2回登場しているので、消そうとすると定義が重複してしまう。しかしラムダ計算にするためならまぁ仕方ない、消していく。

type Arg = number
type Res = number
type Fn = (_: Arg) => Res
type A = (_: Fn) => Fn
type B = (_: B) => Fn

const Z = (a: A): Fn => ((b: B) => a((arg) => b(b)(arg)))((b) => a((arg) => b(b)(arg)))

const fib = Z((fn: Fn) => (n: Arg) => (n <= 2 ? 1 : fn(n - 1) + fn(n - 2)))

fib(10) //=> 55

変数 b も消した。

7. 汎用的にする

いまは入出力の型 (Arg と Res) が number で固定されてしまっているので、これを型引数を使って任意の型を指定できるようにすると、冒頭で紹介したかたちになる。

const Z = <Arg, Res>(a: (_: (_: Arg) => Res) => (_: Arg) => Res) => {
  type B = (_: B) => (_: Arg) => Res
  return ((b: B) => a((n) => b(b)(n)))((b) => a((n) => b(b)(n)))
}

const fib = Z<number, number>((f) => (n) => (n <= 2 ? 1 : f(n - 1) + f(n - 2)))

fib(10) //=> 55

TypeScript で Z コンビネータが作れた。

めでたしめでたし。

なぜこんなことを考えはじめたかというと「タスクが山積みになると家の掃除がしたくなる」アレです。忙しかった...。 ↩
ラムダ計算に変換するのは自分でやったわけではなく、調べると例がたくさん出てくるので真似しただけ。 ↩