カーソルモデルは、XML 処理に関する比較的新しい手法の一つである。このモデルでは、 「カーソル」を前後に動かすことでXML 文書中の要素を選択し、選択した要素に対する 局所的な操作を通して文書の編集を行う。C やJava など一般的な手続き型言語では、 このモデルは部分木を指すポインタをカーソルとして扱うことで容易に実現可能である。 しかしながら、ポインタによる部分木の書き換えは参照透過性の原理と相容れないため、 この簡単な方法によっては完全な作用型言語でカーソルモデルを記述することはできない。
本論文では、作用的な方法でカーソルを効率的に実現するために、関数型データ構造 “Slit”を提案する。Slit は、Huet により提案されたデータ構造Zipper に、 可変個の子要素を持つ木構造を扱う際の効率及び表現力の面で改良を加えたものである。 このSlit を用いてカーソルモデルに基づくXML 処理の枠組みの実装を行い、またさらに この枠組みを一般化することで、単純な変換規則の指定により非XML データをXML と して操作する方法を示す。
@misc{kinaba04,
author = {Kazuhiro Inaba},
title = {Purely Applicative {XML} Cursor},
year = {2004},
month = {Mar},
}
要は何がやりたかったかというと、C++のiteratorを、 関数型言語の中で実現したかったのでした。Zipper 無しの関数型言語と、 コンテナの中を動き回って必要な要素を見つけるfind操作のアルゴリズムと、 見つけた先の要素に対する操作（データ読み取り/書き換え/削除） の間が不可分になってしまう。
let rec find_and_delete lst =
match lst with [] -> []
| h::t -> if (h satisfies a condtion) then t else find_and_delete t
let rec find_and_replace lst e =
match lst with [] -> []
| h::t -> if (h satisfies a condtion) then e:t else find_and_delete t e
せいいっぱい頑張っても、こうだろう。
let rec find_and_dosomething lst f =
match lst with [] -> []
| h::t -> if (h satisfies a condtion) then ... what ?
操作関数 f の型はどうするの？ f に何を渡せばいい？ 確かに delete と replace くらいなら、f には t を渡せばいいでしょう。 でも、「この find_and_dosomething で見つけた要素の直前の要素を削除したい」 という要求が来たら？ t を渡されても f 側では何もできない。 find_and_dosomething_to_1_prev という、 同じようなことをする別の関数が必要になってしまうのです。 Zipperを使って書いていれば、ZipperをうけとってZipperを返すfindを作れば、 全て解決。返値に対して好きなZipper操作を呼び出し側が加えればOK。
…で。iteratorをリストの上だけを走らせるのはつまんないよね？というのが Slit の動機。リストが解決したら、次はツリーだ。２分木はすでに Zipper で解決されてるから、N分木、unranked-tree を扱えるように拡張してみよう！ と考えてできたのが Slit です。
なぜ XML の話になっちゃったかというと、Slit を思いついたときがたまたま XML.com のCurosrモデルの記事を読んだ直後だったから。
ちなみに、OCamlによる手抜き実装には最初、libHensel という名前がついてました。 ヘンゼルとグレーテルのヘンゼル。たどって元に帰れるように、パン屑 (slitのlist) を残してdownしていくヘンゼル。
presented by k.inaba (kiki .a.t. kmonos.net) under