Zipper

Zipper は、データ構造の要素を更新を簡単にし、データ構造をたどるという操作を効率的にしてくれる。
Generics.MultiRec.Zipper モジュールがすでにあるものの、今回はこれを自作する形になる。

ある部分木の更新や要素の検索

この二つの関数では、方向リストが与えられた木の特定の部分木、いわば注目点を指定する役割をしている。例えばDirections における [R] はルートの右側の部分木を、[] は木全体を表している。

data Direction = L | R deriving (Show)
type Directions = [Direction]
data Tree a = Empty | Node a (Tree a) (Tree a) deriving (Show)

changeTop :: Directions -> Tree Char -> Tree Char
changeTop (L:ds) (Node x l r)   = Node x (changeTop ds l) r
changeTop (R:ds) (Node x l r)   = Node x l (changeTop ds r) 
changeTop [] (Node _ l r)       = Node 'P' l r

elemAt :: Directions -> Tree Char -> Char
elemAt (L:ds) (Node _ l _)      = elemAt ds l
elemAt (R:ds) (Node _ _ r)      = elemAt ds r
elemAt [] (Node x _ _)          = x

freeTree :: Tree Char
freeTree = 
    Node 'P'
        (Node 'O'
            (Node 'L'
                (Node 'N' Empty Empty)
                (Node 'T' Empty Empty)
            )
            (Node 'Y'
                (Node 'S' Empty Empty)
                (Node 'A' Empty Empty)
            )
        )
        (Node 'L'
            (Node 'W' 
                (Node 'C' Empty Empty)
                (Node 'R' Empty Empty)
            )
            (Node 'A'
                (Node 'A' Empty Empty)
                (Node 'C' Empty Empty)
            )
        )

この操作だと、要素の更新を何度もしたいような場合、例えば木の末端の要素を更新する必要が何度もあるような場合では、効率が悪くなってしまう。

どちらの部分木に進んだのか履歴をとる

注目したい部分木と、ルートからその部分木までの道のりを記録したタプルを使う。

-- | パンくずリスト
type Breadcrumbs = [Direction]

goLeft :: (Tree a, Breadcrumbs) -> (Tree a, Breadcrumbs)
goLeft ((Node _ l _), bs) = (l, L:bs)

goRight :: (Tree a, Breadcrumbs) -> (Tree a, Breadcrumbs)
goRight ((Node _ _ r), bs) = (r, R:bs)

-- | 関数のチェーンを見やすくするための演算子を定義
-- | x -: f -: f -: ..
(-:) :: a -> (a -> b) -> b
(-:) x f = f x

*Main Data.List Control.Monad> (freeTree ,[]) -: goRight -: goRight -: goRight 
(Node 'C' Empty Empty,[R,R,R])

これでルートからどのように進んだのかがわかるようになった。しかし、このままでは戻ろうと思っても親の情報やたどる可能性があった他方の情報がないので、木を再構築することができない。

パンくず（履歴情報）には、親ノードを構築するために必要な全てを蓄えておく必要がある。かつ、今注目している部分木の情報は含まないことが重要となる。これは注目している部分木の情報は fst に既出だからであり、snd に蓄える情報と重複すると、もし注目している部分木を更新した場合に、履歴との整合性がとれなくなり、リストの一貫性が壊れてしまうからである。

後から親ノードを辿れるようにする

-- | 型定義：値コンストラクタ 親ノードの要素 選ばなかった部分木 
data Crumb a    =    LeftCrumb a (Tree a)
                |   RightCrumb a (Tree a)
                deriving(Show)
-- | 新しいパンくずリスト
type Breadcrumbs a = [Crumb a]

goLeft :: (Tree a, Breadcrumbs a) -> (Tree a, Breadcrumbs a)
goLeft ((Node x l r), bs)   = (l, LeftCrumb x r:bs)

goRight :: (Tree a, Breadcrumbs a) -> (Tree a, Breadcrumbs a)
goRight ((Node x l r), bs)   = (r, RightCrumb x l:bs)

goUp :: (Tree a, Breadcrumbs a) -> (Tree a, Breadcrumbs a)
goUp (t, LeftCrumb x r:bs)      = (Node x t r, bs)
goUp (t, RightCrumb x l:bs)     = (Node x l t, bs)

-- 上記の関数は、パターンマッチに失敗すると実行時エラーが出てしまう。
-- 自作：goUpについて、空のパンくずが与えられてもエラーにならないように、Maybeモナドを使うならこのようにする
goUp' :: (Tree a, Breadcrumbs a) -> Maybe (Tree a, Breadcrumbs a)
goUp' (t, []) = Nothing
goUp' (t, LeftCrumb x r:bs)      = return (Node x t r, bs)
goUp' (t, RightCrumb x l:bs)     = return (Node x l t, bs)

この Treea と Breadcrumbs のペアは、元の木全体を復元するのに必要な情報に加えて、ある部分木に注目した状態というのを表現している。このスキームなら、木の中を上、左、右へと自由自在に移動できる。

あるデータ構造の注目点、および周辺の情報を含んでいるデータ構造は Zipper と呼ばれる。注目点をデータ構造に沿って上下させる操作は、スボンのジッパーを上下させる操作に似ているからである。

type Zipper a = (Treea, Breadcrumbs a)

注目している木を操る

注目している木の要素を変える関数を作る。

modify :: (a -> a) -> Zipper a -> Zipper a
modify f ((Node x l r), bs) = (Node (f x) l r, bs)
modify f (Empty, bs)        = (Empty, bs)

上、左、右に移動する操作と、要素を変える操作を組み合わせて、元の木を自由に変更できるようになった。

*Main> (freeTree, []) -: goLeft -: goRight -: goUp -: modify toLower 

# 先頭の要素が小文字になっている
(Node 'o' (Node 'L' (Node 'N' Empty Empty) (Node 'T' Empty Empty)) (Node 'Y' (Node 'S' Empty Empty) (Node 'A' Empty Empty)),[LeftCrumb 'P' (Node 'L' (Node 'W' (Node 'C' Empty Empty) (Node 'R' Empty Empty)) (Node 'A' (Node 'A' Empty Empty) (Node 'C' Empty Empty)))])

このように簡単に移動できるようになったのは、パンくずリストが データ構造のうち現在注目していない点を構成していて、かつ逆向きになっているから である。だからこそ、上に移動するときにもルートから延々と下へたどり直す必要がなくなる。

今注目している木を、別の木に置き換えたり、木のてっぺんまで移動する関数も簡単に作ることができる。

attach :: Tree a -> Zipper a -> Zipper a
attach t (_, bs)    = (t, bs) 

topmost :: Zipper a -> Zipper a
topMost (t, [])     = t
topMost z           = topMost (goUp z)

実行サンプル

*Main > (freeTree, []) -: goRight -: goLeft -: goUp -: modify toLower -: topMost 

(Node 'P' (Node 'O' (Node 'L' (Node 'N' Empty Empty) (Node 'T' Empty Empty)) (Node 'Y' (Node 'S' Empty Empty) (Node 'A' Empty Empty))) (Node 'l' (Node 'W' (Node 'C' Empty Empty) (Node 'R' Empty Empty)) (Node 'A' (Node 'A' Empty Empty) (Node 'C' Empty Empty))),[])

何もしなくてもバージョン管理

最初に束縛した freeTree は、modify 関数の操作の後でも変わりなくアクセスすることができる。これはHaskellのデータ構造が immutable だからであり、データ構造自体に更新をかけているわけではない。関数から新しいデータ構造が返ってくる。
言い方を換えれば、データ構造自体をバージョン管理しているようにも見える。

Zipperという機能