純粋関数的なデータ構造に対する計算量の分析方法

　今回紹介したSeq型のような「副作用のない関数による操作のみを使って定義されるデータ構造」では，そのデータ構造に対する操作の計算量の分析に特殊な方法を使います。

　まず，計算量を分析するための基本的な方法として，最悪時の処理に対するコストを最悪時以外の処理に平均する（ならす）ことで算出する「ならし解析（amortized analysys，償却解析）」を使います。ここで用いるならし解析は「アルゴリズムイントロダクション第2巻 - アルゴリズムの設計と解析手法」などの教科書で説明しているような一般的なものではなく，Haskellが持つグラフ簡約やメモ化といった遅延評価の機能に適合するよう改良したものです。

　この特殊な計算量の分析方法を具体的に知りたい方は，「Purely Functional Data Structures」の5章と6章を読んでください。普通のならし解析について理解している人であれば，この本の基になった論文の3章を直接読んでもかまいません。この本は「遅延評価をうまく利用して副作用なしで効率的なデータ型を作る研究」の総まとめと位置付けられているだけあって，遅延評価向けのならし解析を懇切丁寧に解説しています。


著者紹介 shelarcy

　Seqの実装に使われているfinger treeは，この木のHaskellによる実装を記した論文「Finger Trees: A Simple General-purpose Data Structure」により一躍有名になりました。ただし，「高速にアクセスするための指を持つ木」というアイデアは最近になって発明されたものではなく，1977年時点の論文ですでに公開されており，その後，改良が加えられてきました（参考リンク）。

　Wikipediaによると，オリジナルのfinger treeは遅延評価を利用するものではなく，AVL木を改良したものだそうです。2分木の要素を探索する際には，処理のコストが最悪にならないよう，木の構成や木の要素の挿入などの操作に対して条件を付けることがあります。こうした条件を付けた木を平衡木（balanced tree）と呼びます。AVLは平衡木の一種で，「木の各節において，左部分木と右部分木の高さが最大でも1しか異ならない」よう調整したものです。この木の考案者のGeorgy Maximovich Adelson-Velsky氏とYevgeniy Mikhailovich Landis氏にちなんでAVL木と呼ばれています。詳しく知りたい方は，英語版WikipediaのAVL木の項目やAVL木について解説している記事を見てください。

　遅延評価以外にも木の再構成の際の性能悪化を防ぐ方法はあります。上の囲み記事で紹介した「Purely Functional Data Structures」の8章にこうした方法が説明されています。遅延評価を使ったHaskellの美しいデータ構造はそれはそれで魅力的ですが，Haskellでのfinger treeの実装は，あくまで「変数の再代入を行わない」というHaskell固有の事情に合わせたものであることを忘れないでください。他の言語を使うときには，その言語なりの最適な実装があるはずです。