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

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

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

來走二元樹吧!

我們在生物課中學過，樹有非常多種。所以我們來自己發(fā)明棵樹吧！

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 這個節(jié)點了嗎？如果我們想要把他變成 P。我們會怎么做呢？一種方式是用 pattern match 的方式做，直到我們找到那個節(jié)點為止。要先往右走再往左走，再改變元素內(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)  

這不只看起來很丑，而且很不容易閱讀。這到底是怎么回事？我們使用 pattern match 來拆開我們的樹，我們把 root 綁定成 x，把左子樹綁定成 l。對于右子樹我們繼續(xù)使用 pattern match。直到我們碰到一個子樹他的 root 是 'W'。到此為止我們再重建整棵樹，新的樹只差在把 'W' 改成了 'P'。

有沒有比較好的作法呢？有一種作法是我們寫一個函數(shù)，他接受一個樹跟一串 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，我們會建構(gòu)一個左子樹變成 'P' 的新樹。當我們遞歸地調(diào)用 changeToP，我們只會傳給他剩下的部份，因為前面的部份已經(jīng)看過了。對于 R 的 case 也一樣。如果 list 已經(jīng)消耗完了，那表示我們已經(jīng)走到我們的目的地，所以我們就回傳一個新的樹，他的 root 被修改成 'P'。

要避免印出整棵樹，我們要寫一個函數(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 很像，只是他不會記下沿路上的信息，他只會記住目的地是什么。我們把 'W' 變成 'P'，然后用他來查看。

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

看起來運作正常。在這些函數(shù)里面，包含方向的 list 比較像是一種"focus"，因為他特別指出了一棵子樹。一個像 [R] 這樣的 list 是聚焦在 root 的右子樹。一個空的 list 代表的是主樹本身。

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

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

凡走過必留下痕跡

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

要找個東西來代表我們的面包屑，就用一串 Direction (他可以是 L 或者是 R)，只是我們叫他 BreadCrumb 而不叫 Direction。這是因為現(xiàn)在我們把這串 direction 反過來看了：

type Breadcrumbs = [Direction]

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

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

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

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

幾乎是一模一樣。我們再來做一個先往右走再往左走的函數(shù)，讓他來走我們的 freeTree

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

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

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

x -: f = f x

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

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

Going back up

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

一般來說，單單一個面包屑有足夠的信息讓我們重建父親的節(jié)點。所以他應該要包含所有我們沒有選擇的路徑的信息，并且他應該要紀錄我們沿路走的方向。同時他不應該包含我們現(xiàn)在鎖定的子樹。因為那棵子樹已經(jīng)在 tuple 的第一個部份中，如果我們也把他紀錄在面包屑里，那就會有重復的信息。

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

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

我們用 LeftCrumb 來包含我們沒有走的右子樹，而不僅僅只寫個 L。我們用 RightCrumb 來包含我們沒有走的左子樹，而不僅僅只寫個 R。

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

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

我們也要把 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 里面塞有我們之前走的節(jié)點，以及我們選擇不走的右子樹的信息。

要注意這個函數(shù)會假設我們鎖定的子樹并不是 Empty。一個空的樹并沒有任何子樹，所以如果我們選擇在一個空的樹中向左走，就會因為我們對 Node 做模式匹配而產(chǎn)生錯誤。我們沒有處理 Empty 的情況。

goRight 也是類似：

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

在之前我們只能向左或向右走，現(xiàn)在我們由于紀錄了關于父節(jié)點的信息以及我們選擇不走的路的信息，而獲得向上走的能力。來看看 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 這棵樹并檢查最新的 Crumb。如果他是 LeftCrumb，那我們就建立一棵新的樹，其中 t 是他的左子樹并用關于我們沒走過得右子樹的信息來填寫其他 Node 的信息。由于我們使用了面包屑的信息來建立父子樹，所以新的 list 移除了我們的面包屑。

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

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

type Zipper a = (Tree a, Breadcrumbs a)

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

Manipulating trees under focus

現(xiàn)在我們具備了移動的能力，我們再來寫一個改變元素的函數(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) 

如果我們鎖定一個節(jié)點，我們用 f 改變他的 root。如果我們鎖定一棵空的樹，那就什么也不做。我們可以移來移去并走到我們想要改變的節(jié)點，改變元素后并鎖定在那個節(jié)點，之后我們可以很方便的移上移下。

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

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

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

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

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

如果我們用 -: 表達的話：

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

往上走很簡單，畢竟面包屑中含有我們沒走過的路徑的信息，只是里面的信息是相反的，這有點像是要把襪子反過來才能用一樣。有了這些信息，我們就不用再從 root 開始走一遍，我們只要把反過來的樹翻過來就好，然后鎖定他。

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

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

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

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

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

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

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

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

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

來看串列

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

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 的父節(jié)點跟其他未走過的子樹。他也必須記得我們是往左或往右走。所以必須要有除了鎖定的子樹以外的所有信息。

list 比 tree 要簡單，所以我們不需要記住我們是往左或往右，因為我們只有一種方式可以往 list 的更深層走。我們也不需要哪些路徑我們沒有走過的信息。似乎我們所需要的信息只有前一個元素。如果我們的 list 是像 [3,4,5]，而且我們知道前一個元素是 2，我們可以把 2 擺回 list 的 head，成為 [2,3,4,5]。

由于一個單一的面包屑只是一個元素，我們不需要把他擺進一個型態(tài)里面，就像我們在做 tree zippers 時一樣擺進 Crumb：

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

第一個 list 代表現(xiàn)在鎖定的 list，而第二個代表面包屑。讓我們寫一下往前跟往后走的函數(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)  

當往前走的時候，我們鎖定了 list 的 tail，而把 head 當作是面包屑。當我們往回走，我們把最近的面包屑欻來然后擺到 list 的最前頭。

來看看兩個函數(shù)如何運作：

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

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

這樣的形式也比較容易看出我們?yōu)槭裁捶Q呼他為 Zipper，因為他真的就像是拉鏈一般。

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

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

理解了 Zipper 是如何運作之后，我們來用一棵樹來表達一個簡單的文件系統(tǒng)，然后用一個 Zipper 來增強他的功能。讓我們可以在文件夾間移動，就像我們平常對文件系統(tǒng)的操作一般。

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

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

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

這邊是一個裝有些文件與文件夾的文件夾：

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

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

在這個案例中，一個面包屑應該要像文件夾一樣，只差在他缺少了我們目前鎖定的文件夾的信息。為什么要像文件夾而不是文件呢？因為如果我們鎖定了一個文件，我們就沒辦法往下走了，所以要留下信息說我們是從一個文件走過來的并沒有道理。一個文件就像是一棵空的樹一樣。

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

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

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

這是我們 Zipper 的 type synonym：

type FSZipper = (FSItem, [FSCrumb])      

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

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

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

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

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

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 接受一個 Name 跟 FSZipper，回傳一個新的 FSZipper 鎖定在某個文件上。那個文件必須在現(xiàn)在身處的文件夾才行。這函數(shù)不會四處找尋這文件，他只會看現(xiàn)在的文件夾。

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

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

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

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

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

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

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

我們接著往上移動并鎖定在一個鄰近的文件 "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)，因此操作也并不是難事。這邊便來寫個重命名目前鎖定文件或文件夾的函數(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" 這個文件夾，重命名他然后再往回走。

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

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

注意這個函數(shù)會沒辦法處理當我們在鎖定在一個文件卻要添加元素的情況。

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

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

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

小心每一步

到目前為止，我們并沒有特別留意我們在走動時是否會超出界線。不論數(shù)據(jù)結(jié)構(gòu)是二元樹，List 或文件系統(tǒng)。舉例來說，我們的 goLeft 函數(shù)接受一個二元樹的 Zipper 并鎖定到他的左子樹：

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

但如果我們走的樹其實是空的樹呢？也就是說，如果他不是 Node 而是 Empty？再這情況，我們會因為模式匹配不到東西而造成 runtime error。我們沒有處理空的樹的情形，也就是沒有子樹的情形。到目前為止，我們并沒有試著在左子樹不存在的情形下鎖定左子樹。但要走到一棵空的樹的左子樹并不合理，只是到目前為止我們視而不見而已。

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

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

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  

然后我們試著在一棵空的樹往左走，我們會得到 Nothing:

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

看起來不錯。之前的問題是我們在面包屑用完的情形下想往上走，那代表我們已經(jīng)在樹的 root。如果我們不注意的話那 goUp 函數(shù)就會丟出錯誤。

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é)點，如果沒有，就造成一個失敗。

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

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

但現(xiàn)在我們不回傳 Zipper a 而回傳 Maybe (Zipper a)。所以沒辦法像上面串起來。我們在之前章節(jié)也有類似的問題。他是每次走一步，而他的每一步都有可能失敗。

幸運的是我們可以從之前的經(jīng)驗中學習，也就是使用 >>=，他接受一個有 context 的值（也就是 Maybe (Zipper a)），會把值喂進函數(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 來把 Zipper 放到一個 Just 里面。然后用 >>= 來喂到 goRight 的函數(shù)中。首先我們做了一棵樹他的左子樹是空的，而右邊是有兩顆空子樹的一個節(jié)點。當我們嘗試往右走一步，便會得到成功的結(jié)果。往右走兩步也還可以，只是會鎖定在一棵空的子樹上。但往右走三步就沒辦法了，因為我們不能在一棵空子樹上往右走，這也是為什么結(jié)果會是 Nothing。

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

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