この章では、木構造のデータ型を操作する例として、Zipperを紹介しています。
Zipperが解決する問題は、木構造のデータ型の要素を効率よく参照、更新することです。 特に、近接する複数の要素に対する操作について、より効果を発揮します。
序文の説明は、Haskellが参照透明性をもつために生じる話です。
オブジェクト指向言語等では、例えば、5という値をもつInt型のインスタンスが複数存在する場合があり、 それぞれが識別子(実装上はメモリアドレス等)を持つため「どの5か」を区別することができます。
しかしHaskellでは、5という値は唯一つしか存在しません。 そのため、木構造の中で5を持つ要素に辿り着きたい際には「どの5か」を、木の位置で示す必要があります。
また、データの変更を行うこともできません。 データの変更とは、実際には変更後のデータを新たに作成することです。
まずは、二分木の操作を取り上げています。
最初の関数changeToPは、目的の要素に辿りつくために、パターンマッチのハードコーディングでおこなっています。
この方法では、データ型の実装がもろに表に出てくるので、見づらい上に、データ型の実装が変われば、経路を指定するコードを総取替えです。
と言うことで、データ型Directionを定義して、目的の要素までの経路をリストで与えるようにしたのが、次のchangeToPです。これならば、経路に指定方法と、データ型の実装と分離されているので、実装が変わっても安心です。
次に解決するのは、ある要素を参照する度に、ルートから始めないといけない問題です。
本章では、その解決手段として、経路の履歴を記録する手段ととっています。
そして、その履歴を逆に辿ることが出来れば、ルートから始めずに、最終位置の相対で次の要素に辿り着くことができます。
本節では、その履歴をDirectionのリストとして記録することにしています。そのリストに対して、Breadcrumbsという型シノニムを与えています。
また、経路を辿りつつ履歴を取る関数goLeftとgoRightを定義してます。利用者が経路を辿る際には、goLeftとgoRightの連鎖で行うようになります。
第13章で定義した、演算子:-を用いれば、よりコードが視覚的になります。
なお、存在しない経路を指定した場合にランタイムエラーになる問題については、とりあえず先延ばし…。
※あれ、:-で連鎖って、なんだか>>=っぽいですよね…?
履歴を取る仕組みは前節で出来たので、今度は実際に戻る仕組みの定義です。
「一つ前に戻る」とは、言い換えれば「一つ前の部分木を再現する」と言うことです。なので、履歴を記録する際には、移動後の部分木以外のデータ(移動元の要素と辿らなかった側の部分木)も
記録しておく必要があります。
そこで、Directionに代えて、それらも記録するデータ型Crumbを定義しています。Crumbが表しているものを例えて言えば「注目点に穴が開いた、一つ前の部分木」ですね。 なお、
goLeft (Node x l r, bs) = (l, LeftCrumb x r:bs)は
goLeft (Node x l r, bs) = (l, (LeftCrumb x r):bs)であって
goLeft (Node x l r, bs) = (l, LeftCrumb x (r:bs))では無いことに注意してください。
※最初、勘違いして意味がわかりませんでした…。
また、Crumbを用いて、一つ前に戻る関数goUpを定義しています。goUpが行っているのは、前述の通り「一つ前の部分木の再現」です。
ここまで、木構造内の移動が効率よく行えるようになりました。
次は、要素の変更を行う関数を定義しています。
関数modifyは、ノードの値を変更し、関数attachは、部分木を置換します。
関数topMostは、再帰を用いて、一気にルートまで駆け上がる関数です。
Zipperの目的は「木構造のデータを効率良く変更する」であり、最終的にユーザが欲しいのは「変更後の木全体」です。なので、短い本節ですが、木全体を返すためには、実はtopMostが重要だったりします。
リストを、部分木が片側のみの二分木=一分木とみなせば、リストのZipperが定義できます。
リストの場合は、進むか戻るかしかないので、辿った方向を記録しておく必要がありません。
また「一つ前の部分木の再現」についても、直前の要素さえ記録しておけば可能です。
と言うことで、リスト版のZipperであるListZipperは、部分リストと、直前の要素を蓄積したリストの2つで構成されています。
また、関数goForwardと関数goBackが、指定の要素に辿り着くための関数です。
折角ですので、リストの先頭に戻る関数goHead(topMostに対応)と、ListZipper版の関数modify/attachを定義してみましょう。
本節では、ファイルシステムという例を通じて、より一般的な木構造に対するZipperについて考察しています。
Zipperを考える際に重要なのは、「どうすれば一つ前の部分木(親フォルダ)を再現できるか」という点です。 或いは二分木のCrumbのように「注目点に穴が開いた、一つ前の部分木(親フォルダ)」とは何か、ということです。
穴が開いている位置を特定するために、ファイルシステム版のCrumbでは「穴の左側の要素リスト」と「穴の右側の要素リスト」を持つことにします。注目点を、この2つのリストで挟み込めば、一つ前の部分木(親フォルダ)が再現できます。それが型FSCrumbです。
ファイルシステム版のZipperである型FSZipper自体は、構造は二分木版のZipperと同じですね。
これを元に、親フォルダに戻る関数fsUpを定義しています。
上述の通り、注目点を左側の要素リストと右側の要素リストで挟み込んで、親フォルダを再構築しています。
一方、フォルダ内の要素に注目する関数fsToですが、今回は名前を指定してその要素に辿り着くようにします。
履歴に残すために、フォルダ内の要素を注目点の左側と右側に分割する必要があります。
そのためにちょうどいい関数breakが、標準ライブラリに存在します。
http://hackage.haskell.org/package/base-4.8.0.0/docs/Prelude.html#v:break
break :: (a -> Bool) -> [a] -> ([a], [a])breakに与える述語として、関数nameIsを定義しています。これらによって、指定した名前でリストを分割できるようになります。
あとは、分割したリストを用いてFSCrumbを作り上げます。指定した名前の要素は、右側のリストの先頭になるので、
let (ls, item:rs) = break (nameIs name) itemsというように、右側のリストの先頭をitemとして切り出しています。
それでは、二分木版のtopMostのように、ファイルシステムのルートまで一気に駆け上がる関数fsRootを定義してみましょう。
あとは、ファイルシステムを操作する関数を定義していくだけです。
関数fsRenameは名前の変更、関数fsNewFileは新規ファイルの作成です。二分木のときとそんなに変わらないですね。
それでは、指定された名前のファイル/フォルダを削除する関数fsDeleteFileを定義してみましょう。
fsDeleteFile :: Name -> FSZipper -> FSZipperさて、ずっと先延ばしにしていた、存在しない経路を指定した場合の対策を考えます。
失敗を表す、といえばMaybeです。存在しない経路を指定した場合にはNothingを返すようにします。
新しいgoLeft/goRight/goUpをそのように定義しています。
さらに、Maybeがモナドであることを利用して、今までの-:の代わりに>>=で操作を連鎖させれば、
一連の操作のどこかで失敗した場合は、全体を失敗として扱うことも容易になります。
それでは、Maybe版のmodify/attach/topMostも定義してみましょう。
また、リストとファイルシステムのZipperについても、Maybeで失敗を扱えるように定義してみましょう。