分割の一般化

ウィキペディア小見出し辞書

分割の一般化

出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2021/05/15 07:59 UTC 版)

「2-3 フィンガーツリー」の記事における「分割の一般化」の解説

前述した分割演算では各ノードのサイズを計算してキャッシュし、位置がiとなる要素を探し、そこで分割した。これをさらに一般化すると様々なデータ構造を実装できる。 まず各ノードについて、サイズではなく実装するデータ構造に応じた値を計算し、キャッシュできるようにする。値は例えば通常の列を実装するのであればノードのサイズを計算し、優先順位付きキューを実装するのであればノード内の最大の優先順位を計算する。より詳しい例は#応用で示す。値はどのような値でもよいが、部分木の値からより大きな木の値を計算できるようにモノイドである必要がある。つまり結合則を満たす二項演算⊕とその単位元eを持っている必要がある。 次に、分割点となる要素を探すための述語が必要となる。列の例では「位置がiより大きい」という述語が使われる。分割演算ではこの述語が偽から真に変化する要素を探す。 列の例では分割する位置iを減少させながら再帰呼び出ししたが、一般化した状態ではモノイドを使うため減算はできない。そこでアキュムレータを用意し、再帰呼び出しに入る前に左側の部分木の値を累積していき、基準値と比べる。 述語pはアキュムレータの初期値では偽となり、木全体に対しては真となる必要がある。列の例では初期値として単位元0を使うので、この制限は「iは0以上、木のサイズ未満である」という制限となる。 以上の条件の元で、一般化した分割演算は次のように書ける。ここでmeasureはノードから値へ変換する関数である。初期値xから始めて値を累積しながらpを満たす要素を探していく。 splitTreeAt p x (Single a) = (Empty, a, Empty) splitTreeAt p x (Deep pr m sf) | p (x ⊕ measure pr) = let (pr1, a, pr2) = splitDigitAt p x pr in (pr1, a, Deep pr2 m sf) | p (x ⊕ measure pr ⊕ measure m) = let (sf1, a, sf2) = splitDigitAt p (i ⊕ measure pr ⊕ measure m) sf in (Deep pr m sf1, a, pr2) | otherwise = let -- m1とm3はFingerTree、m2はNode。 (ml, xs, mr) = splitTreeAt p (i ⊕ measure pr) m -- lとrはMaybe (Digit a)とする。 (l, a, r) = splitNodeAt p (i ⊕ measure pr ⊕ measure ml) xs in -- deepR, deepLは、lやrがNothingの場合に繰り下がり処理をしてFingerTreeを作る関数 (deepR pr ml l, a, deepL r mr sf) 通常はある要素までは述語は常に偽となり、それより先の要素では述語は常に真となるようにする。しかし述語の真偽は途中で何度も切り替わってもよい。その場合、このアルゴリズムは述語が偽から真に切り変わる要素のうち適当な1つで分割する。