第十四章 Haskell Zippers 數(shù)據(jù)結(jié)構(gòu)

Zippers 數(shù)據(jù)結(jié)構(gòu)

盡管 Haskell 的純粹性質(zhì)帶來(lái)很多好處，但他讓一些在非純粹語(yǔ)言很容易處理的一些事情變得要用另一種方法解決。由于 referential transparency，同樣一件事在 Haskell 中是沒(méi)有分別的。所以如果我們有一個(gè)裝滿 5 的樹(shù)，而我們希望把其中一個(gè)換成 6，那我們必須要知道我們究竟是想改變哪個(gè) 5。我們也必須知道我們身處在這棵樹(shù)的哪里。但在 Haskell 中，每個(gè) 5 都長(zhǎng)得一樣，我們并不能因?yàn)樗麄冊(cè)趦?nèi)存中的地址不同就把他們區(qū)分開(kāi)來(lái)。我們也不能改變?nèi)魏螤顟B(tài)，當(dāng)我們想要改變一棵樹(shù)的時(shí)候，我們實(shí)際上是說(shuō)我們要一棵新的樹(shù)，只是他長(zhǎng)得很像舊的。一種解決方式是記住一條從根節(jié)點(diǎn)到現(xiàn)在這個(gè)節(jié)點(diǎn)的路徑。我們可以這樣表達(dá)：給定一棵樹(shù)，先往左走，再往右走，再往左走，然后改變你走到的元素。雖然這是可行的，但這非常沒(méi)有效率。如果我們想接連改變一個(gè)在附近的節(jié)點(diǎn)，我們必須再?gòu)母?jié)點(diǎn)走一次。在這個(gè)章節(jié)中，我們會(huì)看到我們可以集中注意在某個(gè)數(shù)據(jù)結(jié)構(gòu)上，這樣讓改變數(shù)據(jù)結(jié)構(gòu)跟遍歷的動(dòng)作非常有效率。

來(lái)走二元樹(shù)吧!

我們?cè)谏镎n中學(xué)過(guò)，樹(shù)有非常多種。所以我們來(lái)自己發(fā)明棵樹(shù)吧！

data Tree a = Empty | Node a (Tree a) (Tree a) deriving (Show)      

這邊我們的樹(shù)不是空的就是有兩棵子樹(shù)。來(lái)看看一個(gè)范例：

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)  
             )  
        )  

畫(huà)成圖的話就是像這樣：

注意到 W 這個(gè)節(jié)點(diǎn)了嗎？如果我們想要把他變成 P。我們會(huì)怎么做呢？一種方式是用 pattern match 的方式做，直到我們找到那個(gè)節(jié)點(diǎn)為止。要先往右走再往左走，再改變?cè)貎?nèi)容，像是這樣：

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)  

這不只看起來(lái)很丑，而且很不容易閱讀。這到底是怎么回事？我們使用 pattern match 來(lái)拆開(kāi)我們的樹(shù)，我們把 root 綁定成 x，把左子樹(shù)綁定成 l。對(duì)于右子樹(shù)我們繼續(xù)使用 pattern match。直到我們碰到一個(gè)子樹(shù)他的 root 是 'W'。到此為止我們?cè)僦亟ㄕ脴?shù)，新的樹(shù)只差在把 'W' 改成了 'P'。

有沒(méi)有比較好的作法呢？有一種作法是我們寫一個(gè)函數(shù)，他接受一個(gè)樹(shù)跟一串 list，里面包含有行走整個(gè)樹(shù)時(shí)的方向。方向可以是 L 或是 R，分別代表向左走或向右走。我們只要跟隨指令就可以走達(dá)指定的位置：

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 中的第一個(gè)元素是 L，我們會(huì)建構(gòu)一個(gè)左子樹(shù)變成 'P' 的新樹(shù)。當(dāng)我們遞歸地調(diào)用 changeToP，我們只會(huì)傳給他剩下的部份，因?yàn)榍懊娴牟糠菀呀?jīng)看過(guò)了。對(duì)于 R 的 case 也一樣。如果 list 已經(jīng)消耗完了，那表示我們已經(jīng)走到我們的目的地，所以我們就回傳一個(gè)新的樹(shù)，他的 root 被修改成 'P'。

要避免印出整棵樹(shù)，我們要寫一個(gè)函數(shù)告訴我們目的地究竟是什么元素。

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  

這函數(shù)跟 changeToP 很像，只是他不會(huì)記下沿路上的信息，他只會(huì)記住目的地是什么。我們把 'W' 變成 'P'，然后用他來(lái)查看。

ghci> let newTree = changeToP [R,L] freeTree  
ghci> elemAt [R,L] newTree  
'P' 

看起來(lái)運(yùn)作正常。在這些函數(shù)里面，包含方向的 list 比較像是一種"focus"，因?yàn)樗貏e指出了一棵子樹(shù)。一個(gè)像 [R] 這樣的 list 是聚焦在 root 的右子樹(shù)。一個(gè)空的 list 代表的是主樹(shù)本身。

這個(gè)技巧看起來(lái)酷炫，但卻不太有效率，特別是在我們想要重復(fù)地改變內(nèi)容的時(shí)候。假如我們有一個(gè)非常大的樹(shù)以及非常長(zhǎng)的一串包含方向的 list。我們需要沿著方向從 root 一直走到樹(shù)的底部。如果我們想要改變一個(gè)鄰近的元素，我們?nèi)孕枰獜?root 開(kāi)始走到樹(shù)的底部。這實(shí)在不太令人滿意。

在下一個(gè)章節(jié)，我們會(huì)介紹一個(gè)比較好的方法，讓我們可以有效率地改變我們的 focus。

凡走過(guò)必留下痕跡

我們需要一個(gè)比包含一串方向的 list 更好的聚焦的方法。如果我們能夠在從 root 走到指定地點(diǎn)的沿路上撒下些面包屑，來(lái)紀(jì)錄我們的足跡呢？當(dāng)我們往左走，我們便記住我們選擇了左邊，當(dāng)我們往右走，便記住我們選擇了右邊。

要找個(gè)東西來(lái)代表我們的面包屑，就用一串 Direction (他可以是 L 或者是 R)，只是我們叫他 BreadCrumb 而不叫 Direction。這是因?yàn)楝F(xiàn)在我們把這串 direction 反過(guò)來(lái)看了：

type Breadcrumbs = [Direction]

這邊有一個(gè)函數(shù)，他接受一棵樹(shù)跟一些面包屑，并在我們往左走時(shí)在 list 的前頭加上 L

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

我們忽略 root 跟右子樹(shù)，直接回傳左子樹(shù)以及面包屑，只是在現(xiàn)有的面包屑前面加上 L。再來(lái)看看往右走的函數(shù)：

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

幾乎是一模一樣。我們?cè)賮?lái)做一個(gè)先往右走再往左走的函數(shù)，讓他來(lái)走我們的 freeTree

ghci> goLeft (goRight (freeTree, []))  
(Node 'W' (Node 'C' Empty Empty) (Node 'R' Empty Empty),[L,R])  

現(xiàn)在我們有了一棵樹(shù)，他的 root 是 'W'，而他的左子樹(shù)的 root 是 'C'，右子樹(shù)的 root 是 'R'。而由于我們先往右走再往左走，所以面包屑是 [L,R]。

要再表示得更清楚些，我們能用定義一個(gè) -:

x -: f = f x

他讓我們可以將值喂給函數(shù)這件事反過(guò)來(lái)寫，先寫值，再來(lái)是 -:，最后是函數(shù)。所以我們可以寫成 (freeTree, []) -: goRight 而不是 goRight (freeTree, [])。我們便可以把上面的例子改寫地更清楚。

ghci> (freeTree, []) -: goRight -: goLeft  
(Node 'W' (Node 'C' Empty Empty) (Node 'R' Empty Empty),[L,R])  

Going back up

如果我們想要往回上走回我們?cè)瓉?lái)的路徑呢？根據(jù)留下的面包屑，我們知道現(xiàn)在的樹(shù)是他父親的左子樹(shù)，而他的父親是祖父的右子樹(shù)。這些信息并不足夠我們往回走。看起來(lái)要達(dá)到這件事情，我們除了單純紀(jì)錄方向之外，還必須把其他的數(shù)據(jù)都記錄下來(lái)。在這個(gè)案例中，也就是他的父親以及他的右子樹(shù)。

一般來(lái)說(shuō)，單單一個(gè)面包屑有足夠的信息讓我們重建父親的節(jié)點(diǎn)。所以他應(yīng)該要包含所有我們沒(méi)有選擇的路徑的信息，并且他應(yīng)該要紀(jì)錄我們沿路走的方向。同時(shí)他不應(yīng)該包含我們現(xiàn)在鎖定的子樹(shù)。因?yàn)槟强米訕?shù)已經(jīng)在 tuple 的第一個(gè)部份中，如果我們也把他紀(jì)錄在面包屑里，那就會(huì)有重復(fù)的信息。

我們來(lái)修改一下我們面包屑的定義，讓他包含我們之前丟掉的信息。我們定義一個(gè)新的型態(tài)，而不用 Direction：

data Crumb a = LeftCrumb a (Tree a) | RightCrumb a (Tree a) deriving (Show)

我們用 LeftCrumb 來(lái)包含我們沒(méi)有走的右子樹(shù)，而不僅僅只寫個(gè) L。我們用 RightCrumb 來(lái)包含我們沒(méi)有走的左子樹(shù)，而不僅僅只寫個(gè) R。

這些面包屑包含了所有重建樹(shù)所需要的信息。他們像是軟碟一樣存了許多我們的足跡，而不僅僅只是方向而已。

大致上可以把每個(gè)面包屑想像成一個(gè)樹(shù)的節(jié)點(diǎn)，樹(shù)的節(jié)點(diǎn)有一個(gè)洞。當(dāng)我們往樹(shù)的更深層走，面包屑攜帶有我們所有走過(guò)得所有信息，只除了目前我們鎖定的子樹(shù)。他也必須紀(jì)錄洞在哪里。在 LeftCrumb 的案例中，我們知道我們是向左走，所以我們?nèi)鄙俚谋闶亲笞訕?shù)。

我們也要把 Breadcrumbs 的 type synonym 改掉：

type Breadcrumbs a = [Crumb a]

接著我們修改 goLeft 跟 goRight 來(lái)紀(jì)錄一些我們沒(méi)走過(guò)的路徑的信息。不像我們之前選擇忽略他。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 來(lái)表示我們選擇向左走。而且我們?cè)?nbsp;LeftCrumb 里面塞有我們之前走的節(jié)點(diǎn)，以及我們選擇不走的右子樹(shù)的信息。

要注意這個(gè)函數(shù)會(huì)假設(shè)我們鎖定的子樹(shù)并不是 Empty。一個(gè)空的樹(shù)并沒(méi)有任何子樹(shù)，所以如果我們選擇在一個(gè)空的樹(shù)中向左走，就會(huì)因?yàn)槲覀儗?duì) Node 做模式匹配而產(chǎn)生錯(cuò)誤。我們沒(méi)有處理 Empty 的情況。

goRight 也是類似：

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

在之前我們只能向左或向右走，現(xiàn)在我們由于紀(jì)錄了關(guān)于父節(jié)點(diǎn)的信息以及我們選擇不走的路的信息，而獲得向上走的能力。來(lái)看看 goUp 函數(shù)：

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 這棵樹(shù)并檢查最新的 Crumb。如果他是 LeftCrumb，那我們就建立一棵新的樹(shù)，其中 t 是他的左子樹(shù)并用關(guān)于我們沒(méi)走過(guò)得右子樹(shù)的信息來(lái)填寫其他 Node 的信息。由于我們使用了面包屑的信息來(lái)建立父子樹(shù)，所以新的 list 移除了我們的面包屑。

如果我們已經(jīng)在樹(shù)的頂端并使用這個(gè)函數(shù)的話，他會(huì)引發(fā)錯(cuò)誤。等一會(huì)我們會(huì)用 Maybe 來(lái)表達(dá)可能失敗的情況。

有了 Tree a 跟 Breadcrumbs a，我們就有足夠的信息來(lái)重建整棵樹(shù)，并且鎖定其中一棵子樹(shù)。這種方式讓我們可以輕松的往上，往左，往右走。這樣成對(duì)的數(shù)據(jù)結(jié)構(gòu)我們叫做 Zipper，因?yàn)楫?dāng)我們改變鎖定的時(shí)候，他表現(xiàn)得很像是拉鏈一樣。所以我們便定義一個(gè) type synonym:

type Zipper a = (Tree a, Breadcrumbs a)

我個(gè)人是比較傾向于命名成 Focus，這樣可以清楚強(qiáng)調(diào)我們是鎖定在其中一部分， 至于 Zipper 被更廣泛地使用，所以這邊仍維持叫他做 Zipper。

Manipulating trees under focus

現(xiàn)在我們具備了移動(dòng)的能力，我們?cè)賮?lái)寫一個(gè)改變?cè)氐暮瘮?shù)，他能改變我們目前鎖定的子樹(shù)的 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) 

如果我們鎖定一個(gè)節(jié)點(diǎn)，我們用 f 改變他的 root。如果我們鎖定一棵空的樹(shù)，那就什么也不做。我們可以移來(lái)移去并走到我們想要改變的節(jié)點(diǎn)，改變?cè)睾蟛㈡i定在那個(gè)節(jié)點(diǎn)，之后我們可以很方便的移上移下。

ghci> let newFocus = modify (\_ -> 'P') (goRight (goLeft (freeTree,[])))

我們往左走，然后往右走并將 root 取代為 'P'，用 -: 來(lái)表達(dá)的話就是：

ghci> let newFocus = (freeTree,[]) -: goLeft -: goRight -: modify (\_ -> 'P')

我們也能往上走并置換節(jié)點(diǎn)為 'X'：

ghci> let newFocus2 = modify (\_ -> 'X') (goUp newFocus)

如果我們用 -: 表達(dá)的話：

ghci> let newFocus2 = newFocus -: goUp -: modify (\_ -> 'X')

往上走很簡(jiǎn)單，畢竟面包屑中含有我們沒(méi)走過(guò)的路徑的信息，只是里面的信息是相反的，這有點(diǎn)像是要把襪子反過(guò)來(lái)才能用一樣。有了這些信息，我們就不用再?gòu)?root 開(kāi)始走一遍，我們只要把反過(guò)來(lái)的樹(shù)翻過(guò)來(lái)就好，然后鎖定他。

每個(gè)節(jié)點(diǎn)有兩棵子樹(shù)，即使子樹(shù)是空的也是視作有樹(shù)。所以如果我們鎖定的是一棵空的子樹(shù)我們可以做的事就是把他變成非空的，也就是葉節(jié)點(diǎn)。

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

我們接受一棵樹(shù)跟一個(gè) zipper，回傳一個(gè)新的 zipper，鎖定的目標(biāo)被換成了提供的樹(shù)。我們不只可以用這招把空的樹(shù)換成新的樹(shù)，我們也能把現(xiàn)有的子樹(shù)給換掉。讓我們來(lái)用一棵樹(shù)換掉我們 freeTree 的最左邊：

ghci> let farLeft = (freeTree,[]) -: goLeft -: goLeft -: goLeft -: goLeft  
ghci> let newFocus = farLeft -: attach (Node 'Z' Empty Empty)  

newFocus 現(xiàn)在鎖定在我們剛剛接上的樹(shù)上，剩下部份的信息都放在面包屑里。如果我們用 goUp 走到樹(shù)的最上層，就會(huì)得到跟原來(lái) freeTree 很像的樹(shù)，只差在最左邊多了 'Z'。

I'm going straight to top, oh yeah, up where the air is fresh and clean!

寫一個(gè)函數(shù)走到樹(shù)的最頂端是很簡(jiǎn)單的：

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

如果我們的面包屑都沒(méi)了，就表示我們已經(jīng)在樹(shù)的 root，我們便回傳目前的鎖定目標(biāo)。晡然，我們便往上走來(lái)鎖定到父節(jié)點(diǎn)，然后遞歸地調(diào)用 topMost。我們現(xiàn)在可以在我們的樹(shù)上四處移動(dòng)，調(diào)用 modify 或 attach 進(jìn)行我們要的修改。我們用 topMost 來(lái)鎖定到 root，便可以滿意地欣賞我們的成果。

來(lái)看串列

Zippers 幾乎可以套用在任何數(shù)據(jù)結(jié)構(gòu)上，所以聽(tīng)到他可以被套用在 list 上可別太驚訝。畢竟，list 就是樹(shù)，只是節(jié)點(diǎn)只有一個(gè)兒子，當(dāng)我們實(shí)作我們自己的 list 的時(shí)候，我們定義了下面的型態(tài)：

data List a = Empty | Cons a (List a) deriving (Show, Read, Eq, Ord)

跟我們二元樹(shù)的定義比較，我們就可以看出我們把 list 看作樹(shù)的原則是正確的。

一串 list 像是 [1,2,3] 可以被寫作 1:2:3:[]。他由 list 的 head1 以及 list 的 tail 2:3:[] 組成。而 2:3:[] 又由 2 跟 3:[] 組成。至于 3:[]，3 是 head 而 tail 是 []。

我們來(lái)幫 list 做個(gè) zipper。list 改變鎖定的方式分為往前跟往后（tree 分為往上，往左跟往右）。在樹(shù)的情形中，鎖定的部份是一棵子樹(shù)跟留下的面包屑。那究竟對(duì)于一個(gè) list 而言一個(gè)面包屑是什么？當(dāng)我們處理二元樹(shù)的時(shí)候，我們說(shuō)面包屑必須代表 root 的父節(jié)點(diǎn)跟其他未走過(guò)的子樹(shù)。他也必須記得我們是往左或往右走。所以必須要有除了鎖定的子樹(shù)以外的所有信息。

list 比 tree 要簡(jiǎn)單，所以我們不需要記住我們是往左或往右，因?yàn)槲覀冎挥幸环N方式可以往 list 的更深層走。我們也不需要哪些路徑我們沒(méi)有走過(guò)的信息。似乎我們所需要的信息只有前一個(gè)元素。如果我們的 list 是像 [3,4,5]，而且我們知道前一個(gè)元素是 2，我們可以把 2 擺回 list 的 head，成為 [2,3,4,5]。

由于一個(gè)單一的面包屑只是一個(gè)元素，我們不需要把他擺進(jìn)一個(gè)型態(tài)里面，就像我們?cè)谧?tree zippers 時(shí)一樣擺進(jìn) Crumb：

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

第一個(gè) list 代表現(xiàn)在鎖定的 list，而第二個(gè)代表面包屑。讓我們寫一下往前跟往后走的函數(shù)：

goForward :: ListZipper a -> ListZipper a  
goForward (x:xs, bs) = (xs, x:bs)  
  
goBack :: ListZipper a -> ListZipper a  
goBack (xs, b:bs) = (b:xs, bs)  

當(dāng)往前走的時(shí)候，我們鎖定了 list 的 tail，而把 head 當(dāng)作是面包屑。當(dāng)我們往回走，我們把最近的面包屑?xì)H來(lái)然后擺到 list 的最前頭。

來(lái)看看兩個(gè)函數(shù)如何運(yùn)作：

ghci> let xs = [1,2,3,4]  
ghci> goForward (xs,[])  
([2,3,4],[1])  
ghci> goForward ([2,3,4],[1])  
([3,4],[2,1])  
ghci> goForward ([3,4],[2,1])  
([4],[3,2,1])  
ghci> goBack ([4],[3,2,1])  
([3,4],[2,1])  

我們看到在這個(gè)案例中面包屑只不過(guò)是一部分反過(guò)來(lái)的 list。所有我們走過(guò)的元素都被丟進(jìn)面包屑里面，所以要往回走很容易，只要把信息從面包屑里面撿回來(lái)就好。

這樣的形式也比較容易看出我們?yōu)槭裁捶Q呼他為 Zipper，因?yàn)樗娴木拖袷抢溡话恪?/p>

如果你正在寫一個(gè)文本編輯器，那你可以用一個(gè)裝滿字串的 list 來(lái)表達(dá)每一行文本。你也可以加一個(gè) Zipper 以便知道現(xiàn)在光標(biāo)移動(dòng)到那一行。有了 Zipper 你就很容易的可以添加或刪除現(xiàn)有的每一行。

陽(yáng)春的文件系統(tǒng)

理解了 Zipper 是如何運(yùn)作之后，我們來(lái)用一棵樹(shù)來(lái)表達(dá)一個(gè)簡(jiǎn)單的文件系統(tǒng)，然后用一個(gè) Zipper 來(lái)增強(qiáng)他的功能。讓我們可以在文件夾間移動(dòng)，就像我們平常對(duì)文件系統(tǒng)的操作一般。

這邊我們采用一個(gè)比較簡(jiǎn)化的版本，文件系統(tǒng)只有文件跟文件夾。文件是數(shù)據(jù)的基本單位，只是他有一個(gè)名字。而文件夾就是用來(lái)讓這些文件比較有結(jié)構(gòu)，并且能包含其他文件夾與文件。所以說(shuō)文件系統(tǒng)中的組件不是一個(gè)文件就是一個(gè)文件夾，所以我們便用如下的方法定義型態(tài)：

type Name = String  
type Data = String  
data FSItem = File Name Data | Folder Name [FSItem] deriving (Show)  

一個(gè)文件是由兩個(gè)字串組成，代表他的名字跟他的內(nèi)容。一個(gè)文件夾由一個(gè)字串跟一個(gè) list 組成，字串代表名字，而 list 是裝有的組件，如果 list 是空的，就代表他是一個(gè)空的文件夾。

這邊是一個(gè)裝有些文件與文件夾的文件夾：

myDisk :: FSItem  
    myDisk = 
        Folder "root"   
            [ File "goat_yelling_like_man.wmv" "baaaaaa"  
            , File "pope_time.avi" "god bless"  
            , Folder "pics"  
                [ File "ape_throwing_up.jpg" "bleargh"  
                , File "watermelon_smash.gif" "smash!!"  
                , File "skull_man(scary).bmp" "Yikes!"  
                ]  
            , File "dijon_poupon.doc" "best mustard"  
            , Folder "programs"  
                [ File "fartwizard.exe" "10gotofart"  
                , File "owl_bandit.dmg" "mov eax, h00t"  
                , File "not_a_virus.exe" "really not a virus"  
                , Folder "source code"  
                    [ File "best_hs_prog.hs" "main = print (fix error)"  
                    , File "random.hs" "main = print 4"  
                    ]  
                ]  
            ]  

這就是目前我的磁盤的內(nèi)容。

A zipper for our file system

我們有了一個(gè)文件系統(tǒng)，我們需要一個(gè) Zipper 來(lái)讓我們可以四處走動(dòng)，并且增加、修改或移除文件跟文件夾。就像二元樹(shù)或 list，我們會(huì)用面包屑留下我們未走過(guò)路徑的信息。正如我們說(shuō)的，一個(gè)面包屑就像是一個(gè)節(jié)點(diǎn)，只是他包含所有除了我們現(xiàn)在正鎖定的子樹(shù)的信息。

在這個(gè)案例中，一個(gè)面包屑應(yīng)該要像文件夾一樣，只差在他缺少了我們目前鎖定的文件夾的信息。為什么要像文件夾而不是文件呢？因?yàn)槿绻覀冩i定了一個(gè)文件，我們就沒(méi)辦法往下走了，所以要留下信息說(shuō)我們是從一個(gè)文件走過(guò)來(lái)的并沒(méi)有道理。一個(gè)文件就像是一棵空的樹(shù)一樣。

如果我們鎖定在文件夾 "root"，然后鎖定在文件 "dijon_poupon.doc"，那面包屑里的信息會(huì)是什么樣子呢？他應(yīng)該要包含上一層文件夾的名字，以及在這個(gè)文件前及之后的所有項(xiàng)目。我們要的就是一個(gè) Name 跟兩串 list。借由兩串 list 來(lái)表達(dá)之前跟之后的元素，我們就完全可以知道我們目前鎖定在哪。

來(lái)看看我們面包屑的型態(tài)：

data FSCrumb = FSCrumb Name [FSItem] [FSItem] deriving (Show)      

這是我們 Zipper 的 type synonym：

type FSZipper = (FSItem, [FSCrumb])      

要往上走是很容易的事。我們只要拿現(xiàn)有的面包屑來(lái)組出現(xiàn)有的鎖定跟面包屑：

fsUp :: FSZipper -> FSZipper  
fsUp (item, FSCrumb name ls rs:bs) = (Folder name (ls ++ [item] ++ rs), bs) 

由于我們的面包屑有上一層文件夾的名字，跟文件夾中之前跟之后的元素，要往上走不費(fèi)吹灰之力。

至于要往更深層走呢？如果我們現(xiàn)在在 "root"，而我們希望走到 "dijon_poupon.doc"，那我們會(huì)在面包屑中留下 "root"，在 "dijon_poupon.doc" 之前的元素，以及在他之后的元素。

這邊有一個(gè)函數(shù)，給他一個(gè)名字，他會(huì)鎖定在在現(xiàn)有文件夾中的一個(gè)文件：

import Data.List (break)  
  
fsTo :: Name -> FSZipper -> FSZipper  
fsTo name (Folder folderName items, bs) =   
  let (ls, item:rs) = break (nameIs name) items  
  in  (item, FSCrumb folderName ls rs:bs)  
    
nameIs :: Name -> FSItem -> Bool  
nameIs name (Folder folderName _) = name == folderName  
nameIs name (File fileName _) = name == fileName  

fsTo 接受一個(gè) Name 跟 FSZipper，回傳一個(gè)新的 FSZipper 鎖定在某個(gè)文件上。那個(gè)文件必須在現(xiàn)在身處的文件夾才行。這函數(shù)不會(huì)四處找尋這文件，他只會(huì)看現(xiàn)在的文件夾。

首先我們用 break 來(lái)把身處文件夾中的文件們分成在我們要找的文件前的，跟之后的。如果記性好，break 會(huì)接受一個(gè) predicate 跟一個(gè) list，并回傳兩個(gè) list 組成的 pair。第一個(gè) list 裝有 predicate 會(huì)回傳 False 的元素，而一旦碰到一個(gè)元素回傳 True，他就把剩下的所有元素都放進(jìn)第二個(gè) list 中。我們用了一個(gè)輔助函數(shù)叫做 nameIs，他接受一個(gè)名字跟一個(gè)文件系統(tǒng)的元素，如果名字相符的話他就會(huì)回傳 True。

現(xiàn)在 ls 一個(gè)包含我們要找的元素之前元素的 list。item 就是我們要找的元素，而 rs 是剩下的部份。有了這些，我們不過(guò)就是把 break 傳回來(lái)的東西當(dāng)作鎖定的目標(biāo)，來(lái)建造一個(gè)面包屑來(lái)包含所有必須的信息。

如果我們要找的元素不在文件夾中，那 item:rs 這個(gè)模式會(huì)符合到一個(gè)空的 list，便會(huì)造成錯(cuò)誤。如果我們現(xiàn)在的鎖定不是一個(gè)文件夾而是一個(gè)文件，我們也會(huì)造成一個(gè)錯(cuò)誤而讓程序當(dāng)?shù)簟?/p>

現(xiàn)在我們有能力在我們的文件系統(tǒng)中移上移下，我們就來(lái)嘗試從 root 走到 "skull_man(scary).bmp" 這個(gè)文件吧：

ghci> let newFocus = (myDisk,[]) -: fsTo "pics" -: fsTo "skull_man(scary).bmp"      

newFocus 現(xiàn)在是一個(gè)鎖定在 "skull_man(scary).bmp" 的 Zipper。我們把 zipper 的第一個(gè)部份拿出來(lái)看看：

ghci> fst newFocus  
File "skull_man(scary).bmp" "Yikes!"  

我們接著往上移動(dòng)并鎖定在一個(gè)鄰近的文件 "watermelon_smash.gif"：

ghci> let newFocus2 = newFocus -: fsUp -: fsTo "watermelon_smash.gif"  
ghci> fst newFocus2  
File "watermelon_smash.gif" "smash!!"  

Manipulating our file system

現(xiàn)在我們知道如何遍歷我們的文件系統(tǒng)，因此操作也并不是難事。這邊便來(lái)寫個(gè)重命名目前鎖定文件或文件夾的函數(shù)：

fsRename :: Name -> FSZipper -> FSZipper  
fsRename newName (Folder name items, bs) = (Folder newName items, bs)  
fsRename newName (File name dat, bs) = (File newName dat, bs)  

我們可以重命名 "pics" 文件夾為 "cspi"：

ghci> let newFocus = (myDisk,[]) -: fsTo "pics" -: fsRename "cspi" -: fsUp      

我們走到 "pics" 這個(gè)文件夾，重命名他然后再往回走。

那寫一個(gè)新的元素在我們目前的文件夾呢？

fsNewFile :: FSItem -> FSZipper -> FSZipper  
fsNewFile item (Folder folderName items, bs) =   
    (Folder folderName (item:items), bs)  

注意這個(gè)函數(shù)會(huì)沒(méi)辦法處理當(dāng)我們?cè)阪i定在一個(gè)文件卻要添加元素的情況。

現(xiàn)在要在 "pics" 文件夾中加一個(gè)文件然后走回 root：

ghci> let newFocus = (myDisk,[]) -: fsTo "pics" -: fsNewFile (File "heh.jpg" "lol") -: fsUp      

當(dāng)我們修改我們的文件系統(tǒng)，他不會(huì)真的修改原本的文件系統(tǒng)，而是回傳一份新的文件系統(tǒng)。這樣我們就可以訪問(wèn)我們舊有的系統(tǒng)（也就是 myDisk）跟新的系統(tǒng)（newFocus 的第一個(gè)部份）使用一個(gè) Zippers，我們就能自動(dòng)獲得版本控制，代表我們能訪問(wèn)到舊的數(shù)據(jù)結(jié)構(gòu)。這也不僅限于 Zippers，也是由于 Haskell 的數(shù)據(jù)結(jié)構(gòu)有 immutable 的特性。但有了 Zipper，對(duì)于操作會(huì)變得更容易，我們可以自由地在數(shù)據(jù)結(jié)構(gòu)中走動(dòng)。

小心每一步

到目前為止，我們并沒(méi)有特別留意我們?cè)谧邉?dòng)時(shí)是否會(huì)超出界線。不論數(shù)據(jù)結(jié)構(gòu)是二元樹(shù)，List 或文件系統(tǒng)。舉例來(lái)說(shuō)，我們的 goLeft 函數(shù)接受一個(gè)二元樹(shù)的 Zipper 并鎖定到他的左子樹(shù)：

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

但如果我們走的樹(shù)其實(shí)是空的樹(shù)呢？也就是說(shuō)，如果他不是 Node 而是 Empty？再這情況，我們會(huì)因?yàn)槟Ｊ狡ヅ洳坏綎|西而造成 runtime error。我們沒(méi)有處理空的樹(shù)的情形，也就是沒(méi)有子樹(shù)的情形。到目前為止，我們并沒(méi)有試著在左子樹(shù)不存在的情形下鎖定左子樹(shù)。但要走到一棵空的樹(shù)的左子樹(shù)并不合理，只是到目前為止我們視而不見(jiàn)而已。

如果我們已經(jīng)在樹(shù)的 root 但仍舊試著往上走呢？這種情形也同樣會(huì)造成錯(cuò)誤。。用了 Zipper 讓我們每一步都好像是我們的最后一步一樣。也就是說(shuō)每一步都有可能會(huì)失敗。這讓你想起什么嗎？沒(méi)錯(cuò)，就是 Monad。更正確的說(shuō)是 Maybe monad，也就是有可能失敗的 context。

我們用 Maybe monad 來(lái)加入可能失敗的 context。我們要把原本接受 Zipper 的函數(shù)都改成 monadic 的版本。首先，我們來(lái)處理 goLeft 跟 goRight。函數(shù)的失敗有可能反應(yīng)在他們的結(jié)果，這個(gè)情況也不利外。所以來(lái)看下面的版本：

goLeft :: Zipper a -> Maybe (Zipper a)  
goLeft (Node x l r, bs) = Just (l, LeftCrumb x r:bs)  
goLeft (Empty, _) = Nothing  
  
goRight :: Zipper a -> Maybe (Zipper a)  
goRight (Node x l r, bs) = Just (r, RightCrumb x l:bs)  
goRight (Empty, _) = Nothing  

然后我們?cè)囍谝豢每盏臉?shù)往左走，我們會(huì)得到 Nothing:

ghci> goLeft (Empty, [])  
Nothing  
ghci> goLeft (Node 'A' Empty Empty, [])  
Just (Empty,[LeftCrumb 'A' Empty])  

看起來(lái)不錯(cuò)。之前的問(wèn)題是我們?cè)诿姘加猛甑那樾蜗孪胪献撸谴砦覀円呀?jīng)在樹(shù)的 root。如果我們不注意的話那 goUp 函數(shù)就會(huì)丟出錯(cuò)誤。

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

我們改一改讓他可以失敗得好看些：

goUp :: Zipper a -> Maybe (Zipper a)  
goUp (t, LeftCrumb x r:bs) = Just (Node x t r, bs)  
goUp (t, RightCrumb x l:bs) = Just (Node x l t, bs)  
goUp (_, []) = Nothing  

如果我們有面包屑，那我們就能成功鎖定新的節(jié)點(diǎn)，如果沒(méi)有，就造成一個(gè)失敗。

之前這些函數(shù)是接受 Zipper 并回傳 Zipper，這代表我們可以這樣操作：

gchi> let newFocus = (freeTree,[]) -: goLeft -: goRight

但現(xiàn)在我們不回傳 Zipper a 而回傳 Maybe (Zipper a)。所以沒(méi)辦法像上面串起來(lái)。我們?cè)谥罢鹿?jié)也有類似的問(wèn)題。他是每次走一步，而他的每一步都有可能失敗。

幸運(yùn)的是我們可以從之前的經(jīng)驗(yàn)中學(xué)習(xí)，也就是使用 >>=，他接受一個(gè)有 context 的值（也就是 Maybe (Zipper a)），會(huì)把值喂進(jìn)函數(shù)并保持其他 context 的。所以就像之前的例子，我們把 -: 換成 >>=。

ghci> let coolTree = Node 1 Empty (Node 3 Empty Empty)  
ghci> return (coolTree,[]) >>= goRight  
Just (Node 3 Empty Empty,[RightCrumb 1 Empty])  
ghci> return (coolTree,[]) >>= goRight >>= goRight  
Just (Empty,[RightCrumb 3 Empty,RightCrumb 1 Empty])  
ghci> return (coolTree,[]) >>= goRight >>= goRight >>= goRight  
Nothing  

我們用 return 來(lái)把 Zipper 放到一個(gè) Just 里面。然后用 >>= 來(lái)喂到 goRight 的函數(shù)中。首先我們做了一棵樹(shù)他的左子樹(shù)是空的，而右邊是有兩顆空子樹(shù)的一個(gè)節(jié)點(diǎn)。當(dāng)我們嘗試往右走一步，便會(huì)得到成功的結(jié)果。往右走兩步也還可以，只是會(huì)鎖定在一棵空的子樹(shù)上。但往右走三步就沒(méi)辦法了，因?yàn)槲覀儾荒茉谝豢每兆訕?shù)上往右走，這也是為什么結(jié)果會(huì)是 Nothing。

現(xiàn)在我們具備了安全網(wǎng)，能夠在出錯(cuò)的時(shí)候通知我們。

我們的文件系統(tǒng)仍有許多情況會(huì)造成錯(cuò)誤，例如試著鎖定一個(gè)文件，或是不存在的文件夾。剩下的就留作習(xí)題。