あぁ^〜永続版スプレー木（persistent splay tree）を実装するのに、二分木のZipperとオプショナルチェーンの相性がよすぎて心がぴょんぴょんするんじゃぁ^〜
スプレー木に限らず二分木の操作を実装すると、参照の付け替えが嵐のように発生する。左の子の参照をあっちに持ってきて、右の子の参照をこっちに持っていく。そういう騒がしいコードの破片があっちこっちに現れる。これは仕方のないことでもある。木の中身を操作するのではなく、木の構造を操作しているのだから、構造の変更（参照の付け替え）が大量発生するのは当然なのだ。当然なのだけど、それにしたって混乱する。
せめて参照の付け替えに自分の直感にそった名前を付けたくなる。今見ている頂点の参照を左の子に付け替えたり、右の子に付け替えたり、親に付け替えたり、、、いや、それって二分木のZipperじゃん。あとは木の回転があればよさそうじゃん。
しかし、二分木のZipperからイイ感じの名前をパクっても悩みは尽きない。今見ている頂点が葉の場合、子が居ないから左右に移動しようとしても失敗する。根の場合は親が居ないから更に親へ移動しようとすれば失敗する。木の回転だっていつでもできるわけじゃない。いちいち失敗していないか確かめながら処理を書くのはメンドウだ。どうにかならないものか。あれ？それってオプショナルチェーンで解決するじゃん。ようは二分木のZipperとオプショナルチェーンがあれば大丈夫じゃん。
そんな感じの思考を推し進めると、ボトムアップスプレーの1ステップがTypeScriptでは次のように書ける（goSplay）。たかが1ステップだと思うかもしれない。でも、失敗するまでステップを繰り返して、失敗するひとつ前の状態を返せば、ボトムアップスプレーを実現できる。そして、そのような失敗に関する繰り返しは簡単なループで書けてしまう。だから1ステップの操作さえあれば、いつでもNステップの操作へ拡張できるのだ。
const goSplay = <T,>(zipper: Zipper<T>): undefined | Zipper<T> => {
// Zig step
if (zipper.parent?.parent === undefined)
return rotParent(zipper);
// Zig-zag step
if (zipper.parent.direction !== zipper.parent.parent.direction)
return chain(zipper, rotParent, rotParent);
// Zig-zig step
return zipper.parent.direction === 'left'
? chain(zipper, goParent, rotParent, goLeft, rotParent)
: chain(zipper, goParent, rotParent, goRight, rotParent);
};プレイグラウンド
実装したスプレー木は下記のプレイグラウンドで試せる。
以下、備忘録。
二分木の型
最初にものすごく素朴な二分木を考えたい。具体的には、次のようにTypeScriptで書き下した Tree 型を二分木として考えたい。
type Tree<T> = undefined | TreeNode<T>;
type TreeNode<T> = Readonly<{
value: T,
left?: Tree<T>,
right?: Tree<T>
}>;value, left, right のプロパティを持つ TreeNode 型が木の頂点を表す。value は頂点が持つ値で、left は左の子（部分木）で、right は右の子（部分木）だ。木を表す Tree 型は undefined と TreeNode 型を合わせたものになっている。undefined を木として認めるのは不思議かもしれない。ただ、要素を持たない空の木を表すのに便利なので、undefined も木として認めることにする。
さて、素朴に定義された二分木を図示してみよう。
・真ん中：値 v を持って左の部分木 L と右の部分木 R を持つノード
・右：二分木の具体例
左側の黒丸（●）は空の二分木（undefined）を描いたものだ。空なので要素を持たない。
真ん中の v と L, R は頂点を表している。値 v を持っていて、左の部分木 L と右の部分木 R への参照を持っている。
右側の 1～10 の値を矢印で結んだ構造は、二分木の具体例である。木の根が値 5 を持つ。根の左の子は値 1 を持ち、根の右の子は値 7 を持つ。同様にして各頂点がさらにぶら下がっている。なお、0 の頂点のように左右の子がない頂点もある。TypeScript では、この木を次のように書ける。
const tree10: Tree<number> = {
value: 5,
left: {
value: 1,
left: { value: 0 },
right: {
value: 3,
left: { value: 2 },
right: { value: 4 }
}
},
right: {
value: 7,
left: { value: 6 },
right: {
value: 9,
left: { value: 8 },
right: { value: 10 }
}
}
};二分木のZipperの型
二分木が定義できたので、二分木の Zipper を定義したい。具体的には、次のように TypeScript で書き下した Zipper 型を二分木の Zipper として考えたい。この型が二分木を渡り歩くための便利な道具になる。
type Zipper<T> = Readonly<{
focus: TreeNode<T>,
parent?: undefined | Parent<T>
}>;
type Parent<T> = Readonly<{
direction: 'left' | 'right',
value: T,
tree?: Tree<T>,
parent?: undefined | Parent<T>
}>;まあ、便利と言われても、Zipper を知っているか、Schorr-Waite アルゴリズムを知っていないと何がどう便利なのかわからないだろう。便利さがわからないときは、絵で描いて感覚をつかむのが大事である。
試しに先ほど描いた二分木の具体例を渡り歩いてみよう。ただし、渡り歩くときに守らなければならない重要なルールがある。矢印の向きに渡り歩くことはできるが、矢印をさかのぼって渡り歩くことができないというルールだ。例えば、 A → B と描かれていれば、A から B へは渡り歩けるが、その逆に B から A へは渡り歩けない。
「いやいや、そんなルールを設けたら一度でも子に降りたら親に戻れないじゃないか」と心配しただろうか。でも安心して欲しい、渡り歩くときに矢印を逆転させればすぐに戻れる。そんなのアリかよって感じだが、矢印を変えてはいけないなんてルールはないのだから、アリよりのアリなのだ。
御託はここまでにして、二分木の根 5 から左の子 1 へ降りる。
絵の中の四角が二分木の Zipper型を表す。四角の中の丸は Zipper型が focus プロパティで焦点を当てている頂点（TreeNode型）になる。そして、黒丸はZipper型が parent プロパティで参照している親（Parent型）である。
改めて上の絵を見ると、5 → 1 の矢印があるので、根 5 から左の子 1 への移動はルール上問題ない。そして移動する際に矢印を逆転させ、1 → 5 の矢印にしている。これによって 1 から 5 へいつでも戻れるようになった。
続けて 1 から右の子 3 へ移動してみよう。1 → 3 の矢印があるので、この移動もルールに適っている。そして移動する際に矢印を逆転させ、3 → 1 の矢印にするのも忘れてはいけない。これによって 3 から 1 へ、いつでも戻れるようになる。
では、本当に親に戻れるか試してみよう。3 → 1 の矢印があるのでこの移動もルールに反していない。だから戻れる。矢印を反転しておいてよかった。おっと、戻るときに矢印を逆転させ、1 → 3 の矢印にすることも忘れてはいけない。これでもう一度 3 に降りれるようになった。
さらに根へ戻ってみる。最初の状態に戻れた。このように焦点を当てている頂点から別の頂点へ移動するたびに、移動に使った矢印を反転させれば、二分木を自由に動けるようになる。便利だ。
「・・・最初から矢印を双方向にしておけばよくない？」と指摘したくなるだろうか。その指摘はまったくその通りで、子が親の参照を持つ場合、矢印は双方向になるので二分木の Zipper を使う必要はない。面倒なルールは気にせず好きに動けるようになる。ただ、子が親の参照を持つと永続性を失う。二分木の Zipper を使う方は永続性を保てる。そんなトレードオフがある。ここでは永続性を取って二分木の Zipper を使うことにしよう。
ところで、Zipper に「二分木の」といちいち付けていたのは、二分木以外のデータ構造に対しても、それぞれの Zipper が存在するからだ。理論的には型関数の形式的な偏微分から導出される型関数が Zipper になる。そんな形式的に定まるデータ構造が、このような利便性を備えているのは大変に驚くべきことかもしれない。ただ、使いたいのは二分木の Zipper であって、一般的な Zipper に用はない。だから、理論面は無視して、二分木の Zipper に集中する。以降、Zipper とだけ書いてあれば、それは二分木の Zipper を指していると思って欲しい。
ちなみに Zipper については下記サイトの説明がわかりやすい。
失敗を短絡しつつ関数適用する関数（optional）
Zipper 用の goLeft や goRight などの操作を早く実装したいのはやまやまだが、これらの操作は失敗する可能性がある。例えば、左の子が存在しない頂点から、さらに左に進むことはできない。そのため、左の子が存在しない頂点に焦点が当たっている状態で goLeft を呼び出すと失敗してしまう。失敗をハンドリングする機構を先に用意したほうがよさそうだ。
失敗する可能性のある処理をうまく扱うための機能は TypeScript（というか JavaScript）にもある。例えば、オプショナルチェーン (?.) や、Null 合体演算子 (??) がある。もちろん、これらの演算子も積極的に使っていくが、関数適用についてのちょうどいい演算子はない。簡単なものを自前で用意しよう。
具体的には、次のように書かれる optional を失敗する可能性のある関数の関数適用に使う。
const identity = <S, T>(value: S, transformer: (value: S) => T) =>
transformer(value);
const optional = <S, T>(value: undefined | S, transformer: (value: S) => undefined | T) =>
value === undefined ? undefined : transformer(value);
・下：optional(v, f)（[×]が失敗を表す）
optional 関数の実装と比較するために identity 関数も書いてみた。identity 関数は第二引数の関数に第一引数の値を適用するだけの高階関数だ。ようは f(v) を identity(v, f) と書ける。それに何の意味があるのかと思うだろうし、実際あんまり意味はない。しいて言えば無名関数の即時実行が書きやすくなるだろうか。たとえば (x => {無名関数の中身})(v) を identity(v, x => {無名関数の中身}) と書けるようになる。・・・うーん。微妙。
その意味のなさげな identity 関数と optional 関数の実装は非常に似ている。optional 関数は、第一引数の値が undefined であれば第二引数の関数へ適用せずに undefined を返す。 identity 関数に、この短絡機能のみを追加したものが optional 関数である。明らかに v === undefined ? undefined : f(v) を optional(v, f) と書けるようになる。言ってみればオプショナルチェーンの関数適用版だ。 identity 関数と一緒でそんなに意味がないように思える。しかし意外と重宝する。
失敗する可能性のある関数をつなぐ関数（chain）
optionalは失敗する可能性のある関数を1回しか適用できない。でも失敗する可能性のあるいくつかの関数を連続で適用したいこともある。そこで、そのような要望に応える関数も用意しておこう。
具体的には、次のように書いた chain を失敗する可能性のあるいくつかの関数の連続的な関数適用に使う。
const chain = <T,>(value: undefined | T, ...transformer: ReadonlyArray<(value: T) => undefined | T>): undefined | T =>
transformer.reduce(optional, value);
これで、optional(optional(optional(v, f), g), h) が chain(v, f, g, h) と書けるようになった。ただ、 f, g, h の引数と戻り値の型は画一的なものに制限される。こういうときにパイプライン演算子がないことの無念さを感じる。パイプライン演算子があれば、もうちょっとキレイに書けそうなのに。fp-ts の pipe 関数の実装 とか筋肉過ぎない？
もっとも、今回に限っては型の制限があったところで平気だったりする。二分木の構造は書き換えても、二分木が持つ値を書き換える操作は書かないからだ。つまり、 Zipper<T> の型引数 T は変わることはないので、chain の制限がほとんど問題にならない。
失敗するまで関数を繰り返し適用する（many）
chain は失敗する可能性のあるいくつかの関数を連続で適用できるが、引数で与えた分の関数しか実行されない。でも必要な適用回数が事前にわかるとは限らない。失敗する直前まで何度でも関数を適用してほしいことがある。そこで、そのような要望に応える関数を用意しておこう。
const many = <T,>(transformer: (value: T) => undefined | T) => (value: T): T => {
let prev = value;
let next = transformer(value);
while (next !== undefined) {
prev = next;
next = transformer(next);
}
return prev;
};
これで、optional( … (optional(optional(v, f), f) … ), f) が many(f)(v) と書けるようになった。ただし、適用した結果が失敗だった場合、繰り返しは停止する。そして失敗直前（停止直前）の成功結果が返ってくる。
この手の処理の分岐と結合の話は下記がわかりやすいと思う。
なお、この記事で反復処理を直接使っているのは chain と many だけだ。他の関数は直接 for 文や while 文、配列のメソッドを使っていない。ましてや再帰もしない。他の関数は chain と many を呼び出すことで反復処理を行っている。もしかすると chain や many には二分探索木の反復における本質が詰まっているのかもしれない。
さて、失敗に関する話はここまでにして、そろそろ Zipperの操作を実装していこう。
左の子に進む（goLeft）
焦点を左の子に移す goLeft を図示すると次のようになる。左の子が存在しなければ処理に失敗し、左の子が存在すれば焦点を移せる。そして、焦点を移す際に矢印を反転させている。
この図を参考にするとTypeScriptでは次のように書ける。実装の詳細は図の通りなので説明はしない。実装するなら図を見ながら書いた方がいい。ただ、direction に'left'を設定することは図から読み取れないかもしれない。この点は注意して実装する必要がある。
const goLeft = <T,>({ focus: { value, left, right }, parent }: Zipper<T>): undefined | Zipper<T> =>
optional(left, left => ({ focus: left, parent: { direction: 'left', value, tree: right, parent } }));ともかく goLeft が手に入ったので早速使ってみる。上で描いた次の操作を実際にやってみよう。
次のように TypeScript上で根から左に移動して頂点の値をコンソールに表示させてみる。
const zipper10: undefined | Zipper<number> = optional(tree10, focus => ({ focus }));
console.log(chain(zipper10, goLeft)?.focus.value); // => 1見事に 1 が表示された。やったね！さらに左にくだれば、0 の頂点に行ける。0 の頂点からさらに左へ行こうとすると想定通り失敗を表す undefined が表示された。完璧だ。
console.log(chain(zipper10, goLeft, goLeft)?.focus.value); // => 0
console.log(chain(zipper10, many(goLeft))?.focus.value); // => 0
console.log(chain(zipper10, goLeft, goLeft, goLeft)); // => undefined
右の子に進む（goRight）
焦点を右の子に移す goRight を図示すると次のようになる。右の子が存在しなければ処理に失敗し、右の子が存在すれば焦点を移せる。そして、焦点を移す際に矢印を反転させている。
この図を参考にするとTypeScriptでは次のように書ける。実装の詳細は図の通りなので説明はしない。実装するなら図を見ながら書いた方がいい。ただ、direction に'right'を設定することは図から読み取れないかもしれない。この点は注意して実装する必要がある。
const goRight = <T,>({ focus: { value, left, right }, parent }: Zipper<T>): undefined | Zipper<T> =>
optional(right, right => ({ focus: right, parent: { direction: 'right', value, tree: left, parent } }));goRight が手に入ったので使ってみる。上で描いた次の操作を実際にやってみよう。
次のように TypeScript上で根から左に移動して、そこから右に移動してから頂点の値をコンソールに表示させてみれば、想定通り 3 が表示される。さらに右に進めば 4 が表示され、さらに右に進もうとすると思った通りに失敗する。大丈夫そうだね。
console.log(chain(zipper10, goLeft, goRight)?.focus.value); // => 3
console.log(chain(zipper10, goLeft, goRight, goRight)?.focus.value); // => 4
console.log(chain(zipper10, goLeft, many(goRight))?.focus.value); // => 4
console.log(chain(zipper10, goLeft, goRight, goRight, goRight)); // => undefined
親へ戻る（goParent）
焦点を親に移す goParent を図示すると次のようになる。親が存在しなければ処理に失敗し、親が存在すれば焦点を移せる。そして、焦点を移す際に矢印を反転させている。
この図を参考にするとTypeScriptでは次のように書ける。実装の詳細は図の通りなので説明はしない。実装するなら図を見ながら書いた方がいい。ただ、焦点が当たっている頂点が左右どちらの子であるかを direction プロパティで判断していることは、図から読み取れないかもしれない。この点は注意して実装する必要がある。
const goParent = <T,>({ focus, parent }: Zipper<T>): undefined | Zipper<T> =>
optional(parent, ({ direction, value, tree, parent }) =>
direction === 'left'
? { focus: { value, left: focus, right: tree }, parent }
: { focus: { value, left: tree, right: focus }, parent });最新のオモチャである goParent が手に入った。使ってみるしかない。毎度のことながら上で描いた操作を実際にやってみる。
TypeScript上で 3 に移動して、そこから親に移動してから値をコンソールに表示させてみれば、想定通り 1 が表示される。さらに親に戻れば 5 が表示され、さらに親に戻ろうとすると思った通りに失敗した。OKっすね。
console.log(chain(zipper10, goLeft, goRight, goParent)?.focus.value); // => 1
console.log(chain(zipper10, goLeft, goRight, goParent, goParent)?.focus.value); // => 5
console.log(chain(zipper10, goLeft, goRight, many(goParent))?.focus.value); // => 5
console.log(chain(zipper10, goLeft, goRight, goParent, goParent, goParent)); // => undefined
親を回転させる（rotParent）
親を回転させる rotParent を図示すると次のようになる。親が存在しなければ処理に失敗し、親が存在すれば回転できる。
この図を参考にするとTypeScriptでは次のように書ける。実装の詳細は図の通りなので説明はしない。実装するなら図を見ながら書いた方がいい。ただ、左右どちらに回転させるかを direction プロパティで判断していることは、図から読み取れないかもしれない。この点は注意して実装する必要がある。
const rotParent = <T,>({ focus: { value, left, right }, parent }: Zipper<T>): undefined | Zipper<T> =>
optional(parent, ({ direction, value: parentValue, tree, parent }) =>
direction === 'left'
? { focus: { value, left, right: { value: parentValue, left: right, right: tree } }, parent }
: { focus: { value, left: { value: parentValue, left: tree, right: left }, right }, parent });新進気鋭の回転操作 rotParent も使ってみたいが、具体例の絵がなかった。先にそっちを用意しよう。下記のように 3 の頂点に焦点が当たっている状態 rotParent すると、親 1 が回転して 3 の子になる。
TypeScript上で 3 に移動して、そこから親を回転させて、焦点の当たっている頂点を根とする部分木をコンソールに表示させてみた。上図の通り、3 が部分木の根で、3 の左に 1、右に 4 がある。さらに 1 の左に 0、 右に 2 があって、正しく回転している。
console.log(JSON.stringify(chain(zipper10, goLeft, goRight, rotParent)?.focus, null, 4));
/*
{
"value": 3,
"left": {
"value": 1,
"left": {
"value": 0
},
"right": {
"value": 2
}
},
"right": {
"value": 4
}
}
*/そこから 1 へ焦点を当て直し、あらためて rotParent すると、木が元の形状に戻る。
TypeScript上でもやってみよう。先ほどの操作に goLeft を追加して 1 に焦点を当て、rotParent で親を回転させる。すると 1 を根とする部分木は図の通り元の形状に戻った。こっちも正しく回転できている。
console.log(JSON.stringify(chain(zipper10, goLeft, goRight, rotParent, goLeft, rotParent)?.focus, null, 4));
/*
{
"value": 1,
"left": {
"value": 0
},
"right": {
"value": 3,
"left": {
"value": 2
},
"right": {
"value": 4
}
}
}
*/さらに 5 へ戻って rotParent すれば、正しく失敗する。最高だね。
console.log(chain(zipper10, goLeft, goRight, rotParent, goLeft, rotParent, goParent, rotParent)); // undefined
ボトムアップスプレーの1ステップ（goSplay）
実は、ここまでの操作を組み合わせるとボトムアップスプレーの1ステップが構成できる。「そもそもスプレー木が何かわからないし、ボトムアップスプレーと言われてもわからない」かもしれない。スプレー木は後で実装するので、ここでのスプレー操作は、焦点を当てている頂点を根に持っていくための不思議な操作ぐらいの扱いでいこう。
スプレー操作の１ステップである goSplay を図示すると次のようになる。親が存在しなければ処理に失敗し、親が根であれば、Zig step と呼ばれる操作を行う。親が根でない、つまり親の親がいる場合は Zig-zag step か Zig-zig step と呼ばれる操作を行う。
Zig step は rotParent と同じ操作で、Zig-zag step は２回連続の rotParent と同じ操作になる。つまり二分木の基本的な操作と同じになる。
一方、Zig-zig step は基本操作の組み合わせで実現できるが、他と比べでやや煩雑である。これは焦点が当たっている頂点の親の親を先に回転させてから親を回転させる必要があるからだ。Zig-zag step も木の回転は２回行うが、親を回転させてから親の親を回転させている。順番に回転させているので単純な操作で済んでいる。Zig-zig step は逆順なので煩雑になっているわけだ。ただしボトムアップで見ると逆順なだけで、トップダウンで見る場合は Zig-zag step の方が逆順になる。
Zig step、Zig-zag step、Zig-zig step によって焦点が当たっている頂点はだんだんと根に近づく。最終的に根まで持ち上げられ、親がいなくなったところで goSplay は失敗する。なぜなら根に居る状態からさらに持ち上げることができないからだ。あるいは、many 関数を停止させるための失敗だと思ってもいい。
ともかく、上記の図を参考にするとTypeScriptでは次のように書ける。
const goSplay = <T,>(zipper: Zipper<T>): undefined | Zipper<T> => {
// Zig step
if (zipper.parent?.parent === undefined)
return rotParent(zipper);
// Zig-zag step
if (zipper.parent.direction !== zipper.parent.parent.direction)
return chain(zipper, rotParent, rotParent);
// Zig-zig step
return zipper.parent.direction === 'left'
? chain(zipper, goParent, rotParent, goLeft, rotParent)
: chain(zipper, goParent, rotParent, goRight, rotParent);
};では、スプレー木の本質である goSplay も使ってみよう。ただ、スプレー操作は1ステップだけ見てもしょうがないので、manyと組み合わせて停止するまで一気にステップを実行する。また、試行に使う二分木は論文（http://www.cs.cmu.edu/~sleator/papers/self-adjusting.pdf）から引用することにした。
最初は zig-zig と zig-zag が混ざった二分木にスプレー操作をしてみよう。
木が低くなって（横に広がって）バランスが良くなったように見える。
TypeScript上で実行したところ、スプレー操作を正しくできていた。ただ、木が大きすぎて改行とインデントを入れて表示すると長くなったので、一行で表示させている。結果を確認したい場合は適当なJSONビューアで見て欲しい。
const zipper_exam1: Zipper<string> = { "focus": { "value": "i", "left": { "value": "h", "left": { "value": "g", "left": { "value": "f", "left": { "value": "A" }, "right": { "value": "e", "left": { "value": "d", "left": { "value": "B" }, "right": { "value": "c", "left": { "value": "C" }, "right": { "value": "b", "left": { "value": "D" }, "right": { "value": "a", "left": { "value": "E" }, "right": { "value": "F" } } } } }, "right": { "value": "G" } } }, "right": { "value": "H" } }, "right": { "value": "I" } }, "right": { "value": "J" } } };
console.log(JSON.stringify(chain(zipper_exam1, goLeft, goLeft, goLeft, goRight, goLeft, goRight, goRight, goRight, many(goSplay)), null, 4));
// => { "focus": { "value": "a", "left": { "value": "f", "left": { "value": "A" }, "right": { "value": "d", "left": { "value": "B" }, "right": { "value": "b", "left": { "value": "c", "left": { "value": "C" }, "right": { "value": "D" } }, "right": { "value": "E" } } } }, "right": { "value": "h", "left": { "value": "g", "left": { "value": "e", "left": { "value": "F" }, "right": { "value": "G" } }, "right": { "value": "H" } }, "right": { "value": "i", "left": { "value": "I" }, "right": { "value": "J" } } } } }次に zig-zig ばかりの二分木にスプレー操作をしてみよう。
こちらも高さが減った。あと、TypeScript上の実行結果は次の通りで、結果を確認したい場合は適当なJSONビューアで見て欲しい。
const zipper_exam2: Zipper<string> = { "focus": { "value": "g", "left": { "value": "f", "left": { "value": "e", "left": { "value": "d", "left": { "value": "c", "left": { "value": "b", "left": { "value": "a", "left": { "value": "A" }, "right": { "value": "B" } }, "right": { "value": "C" } }, "right": { "value": "D" } }, "right": { "value": "E" } }, "right": { "value": "F" } }, "right": { "value": "G" } }, "right": { "value": "H" } } };
console.log(JSON.stringify(chain(zipper_exam2, many(goLeft), goParent, many(goSplay))));
// => { "focus": { "value": "a", "left": { "value": "A" }, "right": { "value": "f", "left": { "value": "d", "left": { "value": "b", "left": { "value": "B" }, "right": { "value": "c", "left": { "value": "C" }, "right": { "value": "D" } } }, "right": { "value": "e", "left": { "value": "E" }, "right": { "value": "F" } } }, "right": { "value": "g", "left": { "value": "G" }, "right": { "value": "H" } } } } }最後に zig-zag ばかりの二分木にスプレー操作をしてみよう。
やはり高さが減った。TypeScript上の実行結果は次の通り。
const zipper_exam3: Zipper<string> = { "focus": { "value": "g", "left": { "value": "f", "left": { "value": "A" }, "right": { "value": "e", "left": { "value": "d", "left": { "value": "B" }, "right": { "value": "c", "left": { "value": "b", "left": { "value": "C" }, "right": { "value": "a", "left": { "value": "D" }, "right": { "value": "E" } } }, "right": { "value": "F" } } }, "right": { "value": "G" } } }, "right": { "value": "H" } } };
console.log(JSON.stringify(chain(zipper_exam3, many(z => chain(z, goLeft, goRight)), many(goSplay))));
// => { "focus": { "value": "a", "left": { "value": "f", "left": { "value": "A" }, "right": { "value": "d", "left": { "value": "B" }, "right": { "value": "b", "left": { "value": "C" }, "right": { "value": "D" } } } }, "right": { "value": "g", "left": { "value": "e", "left": { "value": "c", "left": { "value": "E" }, "right": { "value": "F" } }, "right": { "value": "G" } }, "right": { "value": "H" } } } }論文と同じようにスプレー操作で木のバランスが調整されたので、大丈夫そうだ。しかし、不思議だ。左右のバランスなんて見ていない。なのにバランスが整っていく。不思議だ。焦点を当てた頂点を根に持ち上げていくだけでバランスが取れる。さすがは自己組織化二分木と呼ばれるスプレー木なだけはある。まー、スプレー操作で一時的にバランスが崩れることもあるんだろうけど、厳密な話はあんまり興味が湧かないのでスルーする。
二分探索木の探索の1ステップ（goSearch）
スプレー操作は、スプレー木のための操作だ。スプレー木は二分探索木の一種で、二分探索木は「左の子孫の値 ≦ 焦点を当てている頂点の値 ≦ 右の子孫の値」という条件を満たす二分木である。そして探索木は、その名の通り値を探索するために使う木だ。そんなわけで指定の値が二分探索木のどこの頂点が持っているかを探す操作が必要になる。
やみくもに探してもしょうがないので、二分探索木の大小関係の条件を利用する。焦点を当てている頂点の持つ値が、探索値より大きければ左へ、頂点の値が検索値より小さければ右へ進む。進もうとして、進む先がなかったり、頂点の値が検索値と等しければ探索を失敗（many の停止）させる。
この図を参考にするとTypeScriptでは次のように書ける。要素の大小判定は Compare<T>型の関数 compare で行う。配列の Sort メソッドの比較関数の慣例に従い、 compare は二つの要素を引き数に取り、number型の数値を返す。compare(x, y) ≦ 0 であれば x ≦ y で、compare(x, y) ≧ 0 であれば x ≧ y と判断される。
type Compare<T> = (x: T, y: T) => number;
const goSearch = <T,>(value: T, compare: Compare<T>) => (zipper: Zipper<T>): undefined | Zipper<T> => {
const comp = compare(value, zipper.focus.value);
if (comp === 0)
return undefined;
return comp < 0
? goLeft(zipper)
: goRight(zipper);
};今までの操作と違って、失敗（停止）の条件が３つある。値が見つかった場合、左に行こうとして行けなかった場合、右に行こうとして行けなかった場合の３つだ。この３つの場合は compare 関数の戻り値の 0 と正負の３パターンと一致する。しかし、停止したという情報からは、どの条件に合致して停止したかは判別できない。そのため、必要に応じて goSearch を呼び出した後に、 compare 関数で情報を再取得しなければならない。
もはや見慣れた二分木で 3 や 1.5、11 を探索すると次のようになる。
TypeScript上で 3 や 1.5、11 を探索してみると、それぞれ 3、2、10 の頂点で正しく停止する。イエーイ。
const numSearch = (value: number) => many(goSearch(value, (x, y) => x - y));
console.log(chain(zipper10, numSearch(3))?.focus.value); // => 3
console.log(chain(zipper10, numSearch(1.5))?.focus.value); // => 2
console.log(chain(zipper10, numSearch(11))?.focus.value); // => 10同じ値を複数個持つ二分探索木への対処（goRightIfEquals）
ここまでで扱った二分探索木はすべての値が異なっていた。もしもキーによって大小比較をするような二分探索木であって、同じキーを複数の頂点が持つことを許容する場合、追加の操作が必要になる。たとえば同じキーのうち最も右側にある頂点を見つけたいなら、つぎのように実装される goRightIfEquals が使える。goRightIfEquals は右の子が存在して、右の子の値が引数の値と等しい場合、右に進む。それ以外は失敗（停止）する。
この図を参考にするとTypeScriptでは次のように書ける。
const goRightIfEquals = <T,>(value: T, compare: Compare<T>) => (zipper: Zipper<T>): undefined | Zipper<T> =>
optional(goRight(zipper), zipper => compare(value, zipper.focus.value) !== 0 ? undefined : zipper);5 ばかりの二分探索木で描くと次のようになる。
TypeScript上でも正しく停止する。
const numRightIf = (value: number) => many(goRightIfEquals(value, (x, y) => x - y));
const zipper5_1: Zipper<number> = { focus: { value: 5, left: tree10.left, right: { value: 5, left: { value: 5 }, right: { value: 5, left: { value: 5 } } } } };
console.log(chain(zipper5_1, numRightIf(5))?.focus.value); // => 5
console.log(chain(zipper5_1, numRightIf(5))?.focus.right); // => undefined
console.log(chain(zipper5_1, numRightIf(5))?.focus.left?.value); // => 5
const zipper5_2: Zipper<number> = { focus: { value: 5, left: tree10.left, right: { value: 5, left: { value: 5 }, right: { value: 5, left: { value: 5 }, right: { value: 10 } } } } };
console.log(chain(zipper5_2, numRightIf(5))?.focus.value); // => 5
console.log(chain(zipper5_2, numRightIf(5))?.focus.right?.value); // => 10
console.log(chain(zipper5_2, numRightIf(5))?.focus.left?.value); // => 5接ぎ木（graftLeft, graftRight, graftParent）
ここまで扱ってきた二分木の頂点数は一定だった。もしも二分木の頂点数が変わらないのであれば、バランスを取り直すなんて操作は不要になる。その固定の頂点数に合わせて最適なバランスを１度取ってしまえば済むからだ。こうなったらスプレー操作はお役御免だね。
などということにはならない。値を追加したり削除したりしたい。そうでないと空っぽの二分木からはじめて、いつまでも空っぽの二分木を使うことになる。それは困る。だから二分木の頂点数を変えるような操作も用意しておこう。
とりあえず接ぎ木する操作を描く。左の子を接ぎ木する graftLeft、右の子を接ぎ木する graftRight、親を接ぎ木する graftParent がある。
・右の子の接ぎ木（graftRight）
・親の接ぎ木（graftParent）
この図を参考にするとTypeScriptでは次のように書ける。
const graftLeft = <T,>(left: Tree<T>) =>
({ focus: { value, right }, parent }: Zipper<T>): Zipper<T> =>
({ focus: { value, left, right }, parent });
const graftRight = <T,>(right: Tree<T>) =>
({ focus: { value, left }, parent }: Zipper<T>): Zipper<T> =>
({ focus: { value, left, right }, parent });
const graftParent = <T,>(parent: undefined | Parent<T>) =>
({ focus }: Zipper<T>): Zipper<T> =>
({ focus, parent });親を接ぎ木するという表現はどうなんだという気もするが、焦点を当てている頂点を主体に考えると、親の接ぎ木になる。
根の左の子として、左の左の孫、根の右の子として右の右の孫を接ぎ木すると次のようになる。
console.log(JSON.stringify(chain(zipper10,
graftLeft(chain(zipper10, goLeft, goLeft)?.focus),
graftRight(chain(zipper10, goRight, goRight)?.focus))?.focus));
// { "value": 5, "left": { "value": 0 }, "right": { "value": 9, "left": { "value": 8 }, "right": { "value": 10 } } }あるいは、3 の親を 1 の親で接ぎ木すると次のようになる。
console.log(JSON.stringify(chain(zipper10, goLeft, goRight, graftParent(chain(zipper10, goLeft)?.parent), many(goParent))?.focus));
// { "value": 5, "left": { "value": 3, "left": { "value": 2 }, "right": { "value": 4 } }, "right": { "value": 7, "left": { "value": 6 }, "right": { "value": 9, "left": { "value": 8 }, "right": { "value": 10 } } } }枝刈り（pruneLeft, pruneRight, pruneParent）
木を接ぎ木すれば頂点が増えるかと言うと、必ずしもそうではない。要素を持たない空の木（undefined）を接ぎ木すれば、それはすなわち枝刈りになる。一応絵を描くと次のようになるだろうか。左の子を枝刈りする pruneLeft、右の子を枝刈りする pruneRight、親を枝刈りする pruneParent がある。
・右の子の枝刈り（pruneRight）
・親の枝刈り（pruneParent）
TypeScriptでは次のように書ける。
const pruneLeft: <T>(zipper: Zipper<T>) => Zipper<T> = graftLeft(undefined);
const pruneRight: <T>(zipper: Zipper<T>) => Zipper<T> = graftRight(undefined);
const pruneParent: <T>(zipper: Zipper<T>) => Zipper<T> = graftParent(undefined);左に移動してから、左の子を枝刈りすると次のようになる。
さらに右の子を枝刈りすると次のようになる。
さらに親を枝刈りすると次のようになる。
console.log(JSON.stringify(chain(zipper10, goLeft, pruneLeft, many(goParent))?.focus));
// { "value": 5, "left": { "value": 1, "right": { "value": 3, "left": { "value": 2 }, "right": { "value": 4 } } }, "right": { "value": 7, "left": { "value": 6 }, "right": { "value": 9, "left": { "value": 8 }, "right": { "value": 10 } } } }
console.log(JSON.stringify(chain(zipper10, goLeft, pruneLeft, pruneRight, many(goParent))?.focus));
// { "value": 5, "left": { "value": 1 }, "right": { "value": 7, "left": { "value": 6 }, "right": { "value": 9, "left": { "value": 8 }, "right": { "value": 10 } } } }
console.log(JSON.stringify(chain(zipper10, goLeft, pruneLeft, pruneRight, pruneParent, many(goParent))?.focus));
// { "value": 1 }スプレー木の実装（class SplayTree）
ここまで Zipper の操作がそろい踏めば、素朴なスプレー木はたやすく実装できる。例えば、TypeScript のクラスとして書くと次のようになる。
class SplayTree<T> {
constructor(readonly compare: Compare<T>, readonly tree: Tree<T>) { }
static empty<T>(compare: Compare<T> = (x, y) => x < y ? -1 : x > y ? 1 : 0): SplayTree<T> {
return new SplayTree(compare, undefined);
}
compareRoot(value: T): undefined | number {
return optional(this.tree, tree => this.compare(tree.value, value));
}
chain(...transformer: ReadonlyArray<(zipper: Zipper<T>) => undefined | Zipper<T>>): SplayTree<T> {
const zipper = optional(this.tree, focus => ({ focus }));
const splayed = chain(zipper, ...transformer, many(goSplay));
return new SplayTree(this.compare, splayed?.focus);
}
splay(value: T): SplayTree<T> {
return this.chain(
many(goSearch(value, this.compare)),
many(goRightIfEquals(value, this.compare)));
}
split(value: T): readonly [SplayTree<T>, SplayTree<T>] {
const splayed = this.splay(value);
if ((splayed.compareRoot(value) ?? 0) <= 0) {
const less = splayed.chain(pruneRight);
const greater = splayed.chain(goRight, pruneParent);
return [less, greater];
} else {
const less = splayed.chain(goLeft, pruneParent);
const greater = splayed.chain(pruneLeft);
return [less, greater];
}
}
merge(other: SplayTree<T>): SplayTree<T> {
if (this.tree === undefined)
return other;
return this.chain(many(goRight), graftRight(other.tree));
}
insert(value: T): SplayTree<T> {
const [{ tree: left }, { tree: right }] = this.split(value);
return new SplayTree(this.compare, { value, left, right });
}
delete(value: T): SplayTree<T> {
const splayed = this.splay(value);
if (splayed.compareRoot(value) !== 0)
return splayed;
const left = splayed.chain(goLeft, pruneParent);
const right = splayed.chain(goRight, pruneParent);
return left.merge(right);
}
}見ての通り、参照の付け替えにあたるオブジェクトの生成はほとんど Zipper の操作で表現される。また、繰り返しも chain と many で表現され、表には出てこない。こんなの初見じゃ絶対に意図を読み取れないね。
空のスプレー木（empty）
SplayTree.empty<number>() は SplayTree<number>型の空のスプレー木を作れる。なお、比較関数を引数に渡せる。
const empty = SplayTree.empty<number>((x, y) => x - y);
console.log(empty.tree); // => undefinedスプレー木の根と比較（compareRoot）
splayTree.compareRoot(value) で、compare(root, value) のようにスプレー木の根の値 root と引数で与えられた値 value の大小比較ができる。ただし、スプレー木が空で値を持たない場合、undefined を返す。
const splayTree10 = new SplayTree<number>(empty.compare, tree10);
console.log(splayTree10.compareRoot(5)); // => 0
console.log(splayTree10.compareRoot(7)); // => -2
console.log(splayTree10.compareRoot(1)); // => 4
console.log(empty.compareRoot(5)); // => undefinedスプレー木のチェーン（chain）
splayTree.chain(f, g, h) のように書いて使う。スプレー木 splayTree の二分木を Zipper に変換した後に、Zipperの失敗するかもしれない操作 f, g, h を適用する。最後にスプレー操作（many(goSplay)）をして作られた二分木をスプレー木にして返す。
ただし、Zipper の操作の途中で失敗すると空のスプレー木が返ってくるので注意。undefined をかなり多義的に使っているからこのような注意が必要になる。よろしくない。でも、多義的だから便利なこともある。悩ましい。
スプレー木でスプレー（splay）
splayTree.splay(value) は値 value をスプレー木 splayTree で探索し、スプレー操作を行う。なお、根に持ち上げられた頂点の値が value と等しいかは splayTree.compareRoot(value) === 0 で確認する必要がある。
console.log(JSON.stringify(splayTree10.splay(3)));
// { "tree": { "value": 3, "left": { "value": 1, "left": { "value": 0 }, "right": { "value": 2 } }, "right": { "value": 5, "left": { "value": 4 }, "right": { "value": 7, "left": { "value": 6 }, "right": { "value": 9, "left": { "value": 8 }, "right": { "value": 10 } } } } } }
console.log(JSON.stringify(splayTree10.splay(5.5)));
// { "tree": { "value": 6, "left": { "value": 5, "left": { "value": 1, "left": { "value": 0 }, "right": { "value": 3, "left": { "value": 2 }, "right": { "value": 4 } } } }, "right": { "value": 7, "right": { "value": 9, "left": { "value": 8 }, "right": { "value": 10 } } } } }スプレー木の分割（split）
splayTree.split(value) は値 value でスプレー木 splayTree を２つに分割する。value 以下の値からなるスプレー木と、value より大きい値からなるスプレー木に分割される。
値 value でスプレーしてから splayTree.compareRoot(value) の結果に応じて、右の子か左の子を根と切断するとスプレー木の分割（split）になる。
console.log(JSON.stringify(splayTree10.split(3)));
// [{ "tree": { "value": 3, "left": { "value": 1, "left": { "value": 0 }, "right": { "value": 2 } } } }, { "tree": { "value": 5, "left": { "value": 4 }, "right": { "value": 7, "left": { "value": 6 }, "right": { "value": 9, "left": { "value": 8 }, "right": { "value": 10 } } } } }]
console.log(JSON.stringify(splayTree10.split(5.5)));
// [{ "tree": { "value": 5, "left": { "value": 1, "left": { "value": 0 }, "right": { "value": 3, "left": { "value": 2 }, "right": { "value": 4 } } } } }, { "tree": { "value": 6, "right": { "value": 7, "right": { "value": 9, "left": { "value": 8 }, "right": { "value": 10 } } } } }]スプレー木同士の結合（merge）
splayTreeA.merge(splayTreeB) は splayTreeA と splayTreeB を結合した新しいスプレー木を作る。ただし、splayTreeA のすべての値は splayTreeB のすべての値よりも小さいことを前提としている。この前提を守らないと二分探索木として機能しなくなるので注意。
splayTreeA の一番右の頂点（splayTreeA で一番大きい値を持つ頂点）の右の子として splayTreeB を接ぎ木してからスプレーするとスプレー木同士の結合（merge）になる。
console.log(JSON.stringify(splayTree10.split(3)[0].merge(splayTree10.split(5.5)[1])));
// { "tree": { "value": 3, "left": { "value": 1, "left": { "value": 0 }, "right": { "value": 2 } }, "right": { "value": 6, "right": { "value": 7, "right": { "value": 9, "left": { "value": 8 }, "right": { "value": 10 } } } } } }スプレー木へ値を挿入（insert）
splayTree.insert(value) は 値をスプレー木へ挿入する。
値 value を根とするスプレー木の左右の子を、値 value で分割した結果とすれば、スプレー木への値の挿入（insert）になる。
console.log(JSON.stringify(splayTree10.insert(3)));
// { "tree": { "value": 3, "left": { "value": 3, "left": { "value": 1, "left": { "value": 0 }, "right": { "value": 2 } } }, "right": { "value": 5, "left": { "value": 4 }, "right": { "value": 7, "left": { "value": 6 }, "right": { "value": 9, "left": { "value": 8 }, "right": { "value": 10 } } } } } }
console.log(JSON.stringify(splayTree10.insert(5.5)));
// { "tree": { "value": 5.5, "left": { "value": 5, "left": { "value": 1, "left": { "value": 0 }, "right": { "value": 3, "left": { "value": 2 }, "right": { "value": 4 } } } }, "right": { "value": 6, "right": { "value": 7, "right": { "value": 9, "left": { "value": 8 }, "right": { "value": 10 } } } } } }スプレー木から値を削除（delete）
splayTree.insert(value) は 値をスプレー木から削除する。
値 value でスプレーし、根の値が value と等しければ、根を取り除いてから左右の子を結合 merge すると値の削除（delete）になる。スプレー木に値が存在しなければ、ただのスプレーになる。
console.log(JSON.stringify(splayTree10.delete(3)));
// { "tree": { "value": 2, "left": { "value": 1, "left": { "value": 0 } }, "right": { "value": 5, "left": { "value": 4 }, "right": { "value": 7, "left": { "value": 6 }, "right": { "value": 9, "left": { "value": 8 }, "right": { "value": 10 } } } } } }
console.log(JSON.stringify(splayTree10.delete(5.5)));
// { "tree": { "value": 6, "left": { "value": 5, "left": { "value": 1, "left": { "value": 0 }, "right": { "value": 3, "left": { "value": 2 }, "right": { "value": 4 } } } }, "right": { "value": 7, "right": { "value": 9, "left": { "value": 8 }, "right": { "value": 10 } } } } }スプレー木の永続性と操作時に作成されるオブジェクトの数
スプレー木は実装できた。最後に永続性と操作時に生成されるオブジェクトについて触れる。
上で見た通り、スプレー木は素朴な二分木とその Zipper 、そして Zipper の操作で実装されている。型の定義からして TreeNode型、Zipper型、Parent型のオブジェクトは読み取り専用（Readonly）になっていた。だから一度生成した二分木は（型システムをあざむかない限り）不変で、永続性を持っている。もっとも、Zipper<T> の型引数 T が不変かどうかは使う人次第だけれど。
さて、永続性があったとして、Zipper を書き換えていないのだから、操作のたびに新たな Zipper が生成されていることになる。もしかすると操作のたびに新たな二分木を作っているのだろうか。今まで描いてきた絵も goLeft や goRight の操作前後で別々の木が存在するようにも見える。
そう見えるように描いてはいたが、二分木全体を作り直すなんて非効率的なことはしていない。ほとんどの部分は再利用されている。では、再利用を意識して絵を描き直してみよう。まず、最初の Zipper は、もともとある二分木を参照（再利用）して作れる。作られるのは Zipper型のオブジェクト１つだけだ。
作成した Zipper型のオブジェクトを goLeft で操作してみる。すると新たに Zipper 型のオブジェクトが作成され、1を根とする部分木を参照（再利用）する。そして、新たに作られた Parent 型のオブジェクトを親として参照する。この新しく作られた親は値 5 を保持し、さらに根の右の子であった 7 を参照（再利用）する。作られるのは Zipper型のオブジェクト１つと、Parent型のオブジェクト１つだけだ。
ところで、この新たに作られた Zipper は親としての 5 （黒丸）は参照できるが、根としての 5 （図の灰色の箇所）は参照できなくなっている。随分上の方で「一度でも子に降りたら親に戻れないじゃないか」というツッコミを書いたが、これは正しいツッコミだったわけだ。このツッコミに対する Zipper の返しは「戻れなくても再構築できればよくない？」である。この再構築については後で見よう。
とりあえず続けて goRight で操作する。また新たな Zipper 型のオブジェクトが作成され、3 を根とする部分木を参照（再利用）する。そして、新たに作られた Parent 型のオブジェクトを親として参照する。この新しく作られた親は値 1 を保持し、左の子であった 0 を参照（再利用）し、先ほど作られた 5 を親として参照（再利用）している。作られるのは Zipper 型のオブジェクト１つと、Parent 型のオブジェクト１つだけだ。
ここから goParent で親を再構築してみよう。新たなZipper 型のオブジェクトが作成され、5 を親として参照（再利用）する。そして新たに作成された TreeNode 型のオブジェクトを焦点として参照する。この新しく作られた焦点は値 1 を保持し、左の子として 0 を参照（再利用）し、右の子として 3 を参照（再利用）している。作られるのは Zipper 型のオブジェクト１つと、TreeNode 型のオブジェクト１つだけだ。
さらに親を再構築してみよう。新たなZipper 型のオブジェクトが作成さる。そして新たに作成された TreeNode 型のオブジェクトを焦点として参照する。この新しく作られた焦点は値 5 を保持し、左の子として先ほど作成されあた 1 を参照（再利用）し、右の子として 7 を参照（再利用）する。作られるのは Zipper 型のオブジェクト１つと、TreeNode 型のオブジェクト１つだけだ。
ここまで絵で見てきたように、左に移動して、右に移動して、親に戻って、親に戻った後の最終的な状態は下記のようになる。ほとんどの部分は元の二分木と共有している。
新たに作られたオブジェクトが二分木になっているかわかりにくいので頂点の位置を調整してみよう。確かに二分木だ。
一回の操作が二分木全体を作り直さないことはわかった。だとしても many で操作を繰り返し適用した場合はどうなるのだろうか。
それは少し視点をずらすとわかるかもしれない。下図の黒丸の中の数字に目をつぶれば、3, 0, 7のそれぞれを頂点を根とする部分木の片方向線形リストにも見えてくる。
片方向線形リストはスタックで、木構造とスタックと言えば深さ優先探索（depth-first search, DFS）だ。深さ優先探索のスタックとして Zipper を眺めてみると、スプレー木の操作については、探索でたどった木の高さに比例したオブジェクトが生成されることがわかる。そのためスプレー木が極端にバランスを崩していない限り、many で操作を繰り返し適用した場合であっても、二分木全体が作り直されることはない。
補足
ちなみに、スプレー木の高さは償却的に考えるが、バランスが崩れている時のスプレー木を何度も操作されると、償却計算量の前提が崩れる。そのため、スプレー木を永続データ構造として扱うのは、あまり適切ではなさそうだ。
あと、Zipper の基本操作を使って二分木を走査（トラバース）すると、元の二分木をそっくりコピーした二分木ができてしまう。これは律儀に木を再構築することで生成される。そのため、もう訪問する予定のない子を枝刈りしながら走査したほうがいい。そうすれば、ガベージコレクションの気が向いたタイミングで参照されなくなった残骸が回収される。
以上、備忘録。終わり。
すべてのプログラマーが試すべき挑戦的なアルゴリズムとデータ構造
全てのプログラマーが試すべき挑戦的なアルゴリズムとデータ構造（6選）
— lotz (@lotz84_) December 29, 2022
・トポロジカルソート
・再帰下降構文解析
・Myersアルゴリズム（差分検出）
・ブルームフィルター
・Piece Table
・スプレー木
年末年始でじっくり調べると楽しそうhttps://t.co/HyPhyXEKHG
トポロジカルソートはやったので、後は何をやろうかな。