Zippers 数据结构

尽管 Haskell 的纯粹性质带来很多好处,但他让一些在非纯粹语言很容易处理的一些事情变得要用另一种方法解决。由于 referential transparency,同样一件事在 Haskell 中是没有分别的。所以如果我们有一个装满 5 的树,而我们希望把其中一个换成 6,那我们必须要知道我们究竟是想改变哪个 5。我们也必须知道我们身处在这棵树的哪里。但在 Haskell 中,每个 5 都长得一样,我们并不能因为他们在内存中的地址不同就把他们区分开来。我们也不能改变任何状态,当我们想要改变一棵树的时候,我们实际上是说我们要一棵新的树,只是他长得很像旧的。一种解决方式是记住一条从根节点到现在这个节点的路径。我们可以这样表达:给定一棵树,先往左走,再往右走,再往左走,然后改变你走到的元素。虽然这是可行的,但这非常没有效率。如果我们想接连改变一个在附近的节点,我们必须再从根节点走一次。在这个章节中,我们会看到我们可以集中注意在某个数据结构上,这样让改变数据结构跟遍历的动作非常有效率。
我们在生物课中学过,树有非常多种。所以我们来自己发明 棵树吧!
data Tree a = Empty | Node a (Tree a) (Tree a) deriving (Show)
这边我们的树不是空的就是有两棵子树。来看看一个范例:
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)
)
)
画成图的话就是像这样:

注意到
W
这个节点了吗?如果我们想要把他变成 P
。我们会怎么做呢?一种方式是用 pattern match 的方式做,直到我们找到那个节点为止。要先往右走再往左走,再改变元素内容,像是这样:changeToP :: Tree Char -> Tree Char
changeToP (Node x l (Node y (Node _ m n) r)) = Node x l (Node y (Node 'P' m n) r)
这不只看起来很丑,而且很不容易阅读。这到底是怎么回事?我们使用 pattern match 来拆开我们的树,我们把 root 绑定成
x
,把左子树绑定成 l
。对于右子树我们继续使用 pattern match。直到我们碰到一个子树他的 root 是 'W'
。到此为止我们再重建整棵树,新的树只差在把 'W'
改成了 'P'
。有没有比较好的作法呢?有一种作法是我们写一个函数,他接受一个树跟一串 list,里面包含有行走整个树时的方向。方向可以是
L
或是 R
,分别代表向左走或向右走。我们只要跟随指令就可以走达指定的位置:data Direction = L | R deriving (Show)
type Directions = [Direction]
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
如果在 list 中的第一个元素是
L
,我们会建构一个左子树变成 'P'
的新树。当我们递归地调用 changeToP
,我们只会传给他剩下的部份,因为前面的部份已经看过了。对于 R
的 case 也一样。如果 list 已经消耗完了 ,那表示我们已经走到我们的目的地,所以我们就回传一个新的树,他的 root 被修改成 'P'
。要避免印出整棵树,我们要写一个函数告诉我们目的地究竟是什么元素。
elemAt :: Directions -> Tree a -> a
elemAt (L:ds) (Node _ l _) = elemAt ds l
elemAt (R:ds) (Node _ _ r) = elemAt ds r
elemAt [] (Node x _ _) = x
这函数跟
changeToP
很像,只是他不会记下沿路上的信息,他只会记住目的地是什么。我们把 'W'
变成 'P'
,然后用他来查看。ghci> let newTree = changeToP [R,L] freeTree
ghci> elemAt [R,L] newTree
'P'
看起来运作正常。在这些函数里面,包含方向的 list 比较像是一种"focus",因为他特别指出了一棵子树。一个像
[R]
这样的 list 是聚焦在 root 的右子树。一个空的 list 代表的是主树本身。这个技巧看起来酷炫,但却不太有效率,特别是在我们想要重复地改变内容的时候。假如我们有一个非常大的树以及非常长的一串包含方向的 list。我们需要沿着方向从 root 一直走到树的底部。如果我们想要改变一个邻近的元素,我们仍需要从 root 开始走到树的底部。这实在不太令人满意。
在下一个章节,我们会介绍一个比较好的方法,让我们可以有效率地改变我们的 focus。

我们需要一个比包含一串方向的 list 更好的聚焦的方法。如果我们能够在从 root 走到指定地点的沿路上撒下些面包屑,来纪录我们的足迹呢?当我们往左走,我们便记住我们选择了左边,当我们往右走,便记住我们选择了右边。
要找个东西来代表我们的面包屑,就用一串
Direction
(他可以是 L
或者是 R
),只是我们叫他 BreadCrumb
而不叫 Direction
。这是因为现在我们把这串 direction 反过来看了:type Breadcrumbs = [Direction]
这边有一个函数,他接受一棵树跟一些面包屑,并在我们往左走时在 list 的前头加上
L
goLeft :: (Tree a, Breadcrumbs) -> (Tree a, Breadcrumbs)
goLeft (Node _ l _, bs) = (l, L:bs)
我们忽略 root 跟右子树,直接回传左子树以及面包屑,只是在现有的面包屑前面加上
L
。再来看看往右走的函数:goRight :: (Tree a, Breadcrumbs) -> (Tree a, Breadcrumbs)
goRight (Node _ _ r, bs) = (r, R:bs)
几乎是一模一样。我们再来做一个先往右走再往左走的函数,让他来走我们的
freeTree
ghci> goLeft (goRight (freeTree, []))
(Node 'W' (Node 'C' Empty Empty) (Node 'R' Empty Empty),[L,R])

现在我们有了一棵树,他的 root 是
'W'
,而他的左子树的 root 是 'C'
,右子树的 root 是 'R'
。而由于我们先往右走再往左走,所以面包屑是 [L,R]
。要再表示得更清楚些,我们能用定义一个
-:
x -: f = f x
他让我们可以将值喂给函数这件事反过来写,先写值,再来是
-:
,最后是函数。所以我们可以写成 (freeTree, []) -: goRight
而不是 goRight (freeTree, [])
。我们便可以把上面的例子改写地更清楚。ghci> (freeTree, []) -: goRight -: goLeft
(Node 'W' (Node 'C' Empty Empty) (Node 'R' Empty Empty),[L,R])
如果我们想要往回上走回我们原来的路径呢?根据留下的面包屑,我们知道现在的树是他父亲的左子树,而他的父亲是祖父的右子树。这些信息并不足够我们往回走。看起来要达到这件事情,我们除了单纯纪录方向之外,还必须把其他的数据都记录下来。在这个案例中,也就是他的父亲以及他的右子树。
一般来说,单单一个面包屑有足够的信息让我们重建父亲的节点。所以他应该要包含所有我们没有选择的路径的信息,并且他应该要纪录我们沿路走的方向。同时他不应该包含我们现在锁定的子树。因为那棵子树已经在 tuple 的第一个部份中,如果我们也把他纪录在面包屑里,那就会有重复的信息。
我们来修改一下我们面包屑的定义,让他包含我们之前丢掉的信息。我们定义一个新的型态,而不用
Direction
:data Crumb a = LeftCrumb a (Tree a) | RightCrumb a (Tree a) deriving (Show)
我们用
LeftCrumb
来包含我们没有走的右子树,而不仅仅只写个 L
。我们用 RightCrumb
来包含我们没有走的左子树,而不仅仅只写个 R
。这些面包屑包含了所有重建树所需要的信息。他们像是软碟一样存了许多我们的足迹,而不仅仅只是方向而已。
大致上可以把每个面包屑想像成一个树的节点,树的节点有一个洞。当我们往树的更深层走,面包屑携带有我们所有走过得所有信息,只除了目前我们锁定的子树。他也必须纪录洞在哪里。在
LeftCrumb
的案例中,我们知道我们是向左走,所以我们缺少的便是左子树。我们也要把
Breadcrumbs
的 type synonym 改掉:type Breadcrumbs a = [Crumb a]
接着我们修改
goLeft
跟 goRight
来纪录一些我们没走过的路径的信息。不像我们之前选择忽略他。goLeft
像是这样:goLeft :: (Tree a, Breadcrumbs a) -> (Tree a, Breadcrumbs a)
goLeft (Node x l r, bs) = (l, LeftCrumb x r:bs)
你可以看到跟之前版本的
goLeft
很像,不只是将 L
推到 list 的最前端,我们还加入 LeftCrumb
来表示我们选择向左走。而且我们在 LeftCrumb
里面塞有我们之前走的节点,以及我们选择不走的右子树的信息。要注意这个函数会假设我们锁定的子树并不是
Empty
。一个空的树并没有任何子树,所以如果我们选择在一个空的树中向左走,就会因为我们对 Node
做模式匹配而产生错误。我们没有处理 Empty
的情况。goRight
也是类似:goRight :: (Tree a, Breadcrumbs a) -> (Tree a, Breadcrumbs a)
goRight (Node x l r, bs) = (r, RightCrumb x l:bs)
在之前我们只能向左或向右走,现在我们由于纪录了关于父节点的信息以及我们选择不走的路的信息,而获得向上走的能力。来看看
goUp
函数: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)

我们锁定了
t
这棵树并检查最新的 Crumb
。如果他是 LeftCrumb
,那我们就建立一棵新的树,其中 t
是他的左子树并用关于我们没走过得右子树的信息来填写其他 Node
的信息。由于我们使用了面包屑的信息来建立父子树,所以新的 list 移除了我们的面包屑。如果我们已经在树的顶端并使用这个函数的话,他会引发错误。等一会我们会用
Maybe
来表达可能失败的情况。有了
Tree a
跟 Breadcrumbs a
,我们就有足够的 信息来重建整棵树,并且锁定其中一棵子树。这种方式让我们可以轻松的往上,往左,往右走。这样成对的数据结构我们叫做 Zipper,因为当我们改变锁定的时候,他表现得很像是拉链一样。所以我们便定义一个 type synonym:type Zipper a = (Tree a, Breadcrumbs a)
我个人是比较倾向于命名成
Focus
,这样可以清楚强调我们是锁定在其中一部分, 至于 Zipper 被更广泛地使用,所以这边仍维持叫他做 Zipper
。现在我们具备了移动的能力,我们再来写一个改变元素的函数,他能改变我们目前锁定的子树的 root。
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)
如果我们锁定一个节点,我们用
f
改变他的 root。如果我们锁定一棵空的树,那就什么也不做。我们可以移来移去并走到我们想要改变的节点,改变元素后并锁定在那个节点,之后我们可以很方便的移上移下。ghci> let newFocus = modify (\_ -> 'P') (goRight (goLeft (freeTree,[])))
我们往左走,然后往右走并将 root 取代为
'P'
,用 -:
来表达的话就是:ghci> let newFocus = (freeTree,[]) -: goLeft -: goRight -: modify (\_ -> 'P')
我们也能往上走并置换节点为
'X'
:ghci> let newFocus2 = modify (\_ -> 'X') (goUp newFocus)
如果我们用
-:
表达的话:ghci> let newFocus2 = newFocus -: goUp -: modify (\_ -> 'X')
往上走很简单,毕竟面包屑中含有我们没走过的路径的信息,只是里面的信息是相反的,这有点像是要把袜子反过来才能用一样。有了这些信息,我们就不用再从 root 开始走一遍,我们只要把反过来的树翻过来就好,然后锁定他。
每个节点有两棵子树,即使子树是空的也是视作有树。所以如果我们锁定的是一棵空的子树我们可以做的事就是把他变成非空的,也就是叶节点。
attach :: Tree a -> Zipper a -> Zipper a
attach t (_, bs) = (t, bs)
我们接受一棵树跟一个 zipper,回传一个新的 zipper,锁定的目标被换成了提供的树。我们不只可以用这招把空的树换成新的树,我们也能把现有的子树给换掉。让我们来用一棵树换掉我们
freeTree
的最左边:ghci> let farLeft = (freeTree,[]) -: goLeft -: goLeft -: goLeft -: goLeft
ghci> let newFocus = farLeft -: attach (Node 'Z' Empty Empty)
newFocus
现在锁定在我们刚刚接上的树上,剩下部份的信息都放在面包屑里。如果我们用 goUp
走到树的最上层,就会得到跟原来 freeTree
很像的树,只差在最左边多了 'Z'
。写一个函数走到树的最顶端是很简单的:
topMost :: Zipper a -> Zipper a
topMost (t,[]) = (t,[])
topMost z = topMost (goUp z)
如果我们的面包屑都没了,就表示我们已经在树的 root,我们便回传目前的锁定目标。晡然,我们便往上走来锁定到父节点,然后递归地调用
topMost
。我们现在可以在我们的树上四处移动,调用 modify
或 attach
进行我们要的修改。我们用 topMost
来锁定到 root,便可以满意地欣赏我们的成果。Zippers 几乎可以套用在任何数据结构上,所以听到他可以被套用在 list 上可别太惊讶。毕竟,list 就是树,只是节点只有一个儿子,当我们实作我们自己的 list 的时候,我们定义了下面的型态:
data List a = Empty | Cons a (List a) deriving (Show, Read, Eq, Ord)

跟我们二元树的定义比较,我们就可以看出我们把 list 看作树的原则是正确的。
一串 list 像是
[1,2,3]
可以被写作 1:2:3:[]
。他由 list 的 head1
以及 list 的 tail 2:3:[]
组成。而 2:3:[]
又由 2
跟 3:[]
组成。至于 3:[]
,3
是 head 而 tail 是 []
。我们来帮 list 做个 zipper。list 改变锁定的方式分为往前跟往后(tree 分为往上,往左跟往右)。在树的情形中,锁定的部份是一棵子树跟留下的面包屑。那究竟对于一个 list 而言一个面包屑是什么?当我们处理二元树的时候,我们说面包屑必须代表 root 的父节点跟其他未走过的子树。他也必须记得我们是往左或往右走。所以必须要有除了锁定的子树以外的所有信息。
list 比 tree 要简单,所以我们不需要记住我们是往左或往右,因为我们只有一种方式可以往 list 的更深层走。我们也不需要哪些路径我们没有走过的信息。似乎我们所需要的信息只有前一个元素。如果我们的 list 是像
[3,4,5]
,而且我们知道前一个元素是 2
,我们可以把 2
摆回 list 的 head,成为 [2,3,4,5]