data.finger-tree: フィンガーツリー

(このエントリは Clojure Contrib Library Advent Calendar 13日目の記事です。)

はじめに

今回はdata.finger-treeについてです。data.finger-treeは名前が示すとおり,フィンガーツリーの実装を提供します。Wikipediaによれば,フィンガーツリーは以下のようなデータ構造です:

2-3フィンガーツリー(2-3 finger tree、または単にfinger tree)とは、列を表す永続データ構造の一種であり、償却定数時間で両端への追加・削除が可能であり、対数時間で連結・分割・挿入が可能である。また、分割演算を変更すると優先度つきキューや探索木などを実装できる。

2-3 フィンガーツリー - Wikipedia

data.finger-treeでは,先頭と末尾に定数時間でアクセス可能な「ダブルリスト」と呼ぶデータ構造とその亜種,およびフィンガーツリーを使って独自のデータ構造を作るためのインタフェースが提供されています。
今回は,ダブルリストとその亜種の使い方について見てみます。

インストール

data.finger-treeを使うには,Leiningenのproject.cljへ依存ライブラリとして以下を追加します。

[org.clojure/data.finger-tree "0.0.1"]

使い方

以下は各データ構造に関する特徴的な関数です。

  • double-list
    • (double-list & args): 引数に与えられた値を要素にもつダブルリストを生成します
    • (consl s a): ダブルリストの先頭に要素を追加します
    • (conjr s a): ダブルリストの末尾に要素を追加します
    • (ft-concat t1 t2): 2つのダブルリストを連結します
  • counted-double-list (定数時間のcountをサポートしたダブルリスト)
    • (counted-double-list & args): 引数に与えられた値を要素にもつcounted double listを生成します
    • (ft-split-at o k): ダブルリストをインデックスkの位置で分割します
  • counted-sorted-set (counted double listに似たsorted set)
    • (counted-sorted-set & args): 引数に与えられた値を要素にもつcounted sorted setを生成します

以下,実際の使用例です。

user=> (use 'clojure.data.finger-tree)
nil
user=> (def xs (double-list 1 2 3))
#'user/xs
; conslで先頭に要素を追加できる
user=> (consl xs 0)
(0 1 2 3)
; conjrで末尾に要素を追加できる
user=> (conjr xs 4)
(1 2 3 4)
; ft-concatで2つのダブルリストを連結できる
user=> (ft-concat xs xs)
(1 2 3 1 2 3)
user=> (def ys (counted-double-list 1 2 3))
#'user/ys
; counted double listは定数時間のcountをサポート
user=> (count ys)
3
; ダブルリストと同様に,consl, conjr, ft-concatも適用できる
user=> (consl ys 0)
(0 1 2 3)
user=> (conjr ys 4)
(1 2 3 4)
user=> (ft-concat ys ys)
(1 2 3 1 2 3)
; ft-split-atでリストを分割できる
user=> (ft-split-at ys 1)
[(1) 2 (3)]
user=> 

おわりに

今回はdata.finger-treeが提供する種々のデータ構造について見てみました。
フィンガーツリー自体について,詳しく知りたい場合は以下が参考になります。

次回は,さらにデータ構造つながりでdata.priority-mapについて書きます。