--/--/--

スポンサーサイト

上記の広告は1ヶ月以上更新のないブログに表示されています。
新しい記事を書く事で広告が消せます。

2008/07/04

zipper

xmonad とかにも使われてる、破壊的代入を行わずに更新、削除、追加などの操作が可能なデータ構造。

仕組みは単純。現在の位置、現在の位置より左側にある要素のリスト、現在の位置より右側にある要素のリストを管理する。更新する場合には、現在の位置と置き換える。削除する場合には左側と右側をくっつけ、右側の先頭を現在の位置とする。追加する場合には、現在の位置を左側の末尾に追加し、現在の位置を追加された要素に置き換える。言葉だとなんか難しく見えてしまうな。

現在の位置を移動するには、それ用の関数を用いる。

肝心なのは、現在の位置より左側にある要素のリストを、逆順に保持する点。こうすることで、後戻りが楽になる。

本当はリストじゃなくてツリーのものが正式らしい(元の論文ではツリーを紹介してあった)んだけど、zipper の肝としてはリストでも十分だと思う。ツリーの場合は左右に加えて上下にも移動できるようになる。

以下は haskell での実装。

type Zipper a = ([a],[a])

makeZipper :: [a] -> Zipper a
makeZipper xs = ([],xs)

prev :: Zipper a -> Zipper a
prev (l:ls,rs) = (ls,l:rs)
prev ([],_) = error "not found."

next :: Zipper a -> Zipper a
next (ls,r:rs) = (r:ls, rs)
next (_,[]) = error "not found."

get :: Zipper a -> a
get (_,e:_) = e
get (_,[]) = error "not found."

set :: a -> Zipper a -> Zipper a
set e (ls,_:rs) = (ls,e:rs)
set e (_,[]) = error "not found."

insert :: a -> Zipper a -> Zipper a
insert e (ls,rs) = (ls,e:rs)

remove :: Zipper a -> Zipper a
remove (ls,_:rs) = (ls,rs)
remove (_,[]) = error "not found."
スポンサーサイト

comment

post




上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。