「学习笔记-Haskell」Chapter 15 ZIPPERS

Chapter 15 ZIPPERS

In this chapter, you’ll see how to take some data structure and equip it with something called a zipper to focus on a part of the data structure in a way that makes changing its elements easy and walking around it effi- cient.

Table of Contents1 Taking a Walk1.1 A Trail of Breadcrumbs1.2 Going Back Up1.3 Manipulating Trees Under Focus1.4 Going Straight to the Top,Where the Air Is Fresh and Clean!2 Focusing on Lists3 A Very Simple Filesystem3.1 Making a Zipper for Our Filesystem3.2 Manipulating a Filesystem4 Watch Your Step

As you learned in biology class, there are many different kinds of trees, so let’s pick a seed that we will use to plant ours. Here it is:

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

Here’s a fine example of such a tree

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

Notice that W in the tree there? Say we want to change it into a P. How would we go about doing that? Well, one way would be to pattern match on our tree until we find the element, by first going right and then left.

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)  

Yuck! Not only is this rather ugly, it’s also kind of confusing. We pattern match on our tree,but with the subtree that contained the 'W' at its root now having a 'P'

Is there a better way of doing this? How about if we make our function take a tree along with a list of directions.

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  

To avoid printing out the whole tree, let’s make a function that takes a list of directions and tells us the element at the destination:

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  

Test our functions:

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

This seems to work. In these functions, the list of directions acts as a sort of focus, because it pinpoints one exact subtree of our tree.

While this technique may seem cool, it can be rather inefficient, espe- cially if we want to repeatedly change elements.

In the next section, we’ll find a better way of focusing on a subtree—one that allows us to efficiently switch focus to subtrees that are nearby.

For focusing on a subtree, we want something better than just a list of directions that we always follow from the root of our tree. Would it help if we started at the root of the tree and moved either left or right one step at a time, leaving “breadcrumbs” along the way? Using this approach, when we go left, we remember that we went left, and when we go right, we remember that we went right. Let’s try it.

To represent our breadcrumbs, we’ll also use a list of direction values we’ll call it Breadcrumbs, because our directions will now be reversed as we leave them while going down our tree

type Breadcrumbs = [Direction]

Here’s a function that takes a tree and some breadcrumbs and moves to the left subtree while adding L to the head of the list that represents our breadcrumbs:

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

We ignore the element at the root and the right subtree, and just return the left subtree along with the old breadcrumbs with L as the head.

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

Test it!

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

To make walking along our tree clearer, we can use the -: function

x -: f = f x

This allows us to apply functions to values by first writing the value, then a -:, and then the function.

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

What if we want to go back up in our tree? The breadcrumbs don’t tell us enough about the parent of the current subtree for us to be able to go up in the tree. It would seem that apart from the direction that we took, a single breadcrumb should also contain all the other data we need to go back up.

Let’s modify our breadcrumbs so that they also contain information about everything that we previously ignored when moving left and right. Instead of Direction, we’ll make a new data type:

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

These breadcrumbs now contain all the data needed to re-create the tree that we walked through.

In essence, every breadcrumb is now like a tree node with a hole in it. When we move deeper into a tree, the breadcrumb carries all the infor- mation that the node that we moved away from carried, except the subtree on which we chose to focus. It also needs to note where the hole is. In the case of a LeftCrumb, we know that we moved left, so the missing subtree is the left one. Let’s also change our Breadcrumbs type synonym to reflect this:

type Breadcrumbs a = [Crumb a]

Next up, we need to modify the goLeft and goRight functions to store in- formation about the paths that we didn’t take in our breadcrumbs, instead of ignoring that information as they did before. Here’s goLeft:

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

You can see that it’s very similar to our previous goLeft, but instead of just adding a L to the head of our list of breadcrumbs, we add a LeftCrumb to signify that we went left. We also equip our LeftCrumb with the element in the node that we moved from (that’s the x) and the right subtree that we chose not to visit.

goRight is similar:

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

We were previously able to go left and right. What we have now is the ability to actually go back up by remembering stuff about the parent nodes and the paths that we didn’t visit. Here’s the goUp function

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)

Note that this function causes an error if we’re already at the top of a tree and we want to move up. Later on, we’ll use the Maybe monad to repre- sent possible failure when moving focus.

A pair that contains a focused part of a data structure and its surround- ings is called a zipper, because moving our focus up and down the data struc- ture resembles the operation of a zipper on a pair of pants. So, it’s cool to make a type synonym as such:

type Zipper a = (Tree a, Breadcrumbs a)

Now that we can move up and down, let’s make a function that modifies the element in the root of the subtree on which the zipper is focusing:

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

Test it!

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

This reads even better if we use -::

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

We can then move up if we want and replace an element with a mysteri- ous 'X':

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

Or we can write it with -::

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

Each node has two subtrees, even if those subtrees are empty. So, if we’re focusing on an empty subtree, one thing we can do is to replace it with a nonempty subtree, thus attaching a tree to a leaf node.

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

We take a tree and a zipper, and return a new zipper that has its focus replaced with the supplied tree. Not only can we extend trees this way by replacing empty subtrees with new trees, but we can also replace existing subtrees.

Making a function that walks all the way to the top of the tree, regardless of what we’re focusing on, is really easy.

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

Zippers can be used with pretty much any data structure, so it’s no surprise that they work with sublists of lists.

Let’s make a zipper for lists. Because a single breadcrumb here is just the element, we don’t really need to put it inside a data type, as we did when we made the Crumb data type for tree zippers.

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

The first list represents the list that we’re focusing on, and the second list is the list of breadcrumbs. Let’s make functions that go forward and backward in lists:

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

Here are these two functions in action:

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

If you were making a text editor, you could use a list of strings to rep- resent the lines of text that are currently opened, and you could then use a zipper so that you know on which line the cursor is currently focused. Using a zipper would also make it easier to insert new lines anywhere in the text or delete existing ones.

To demonstrate how zippers work, let’s use trees to represent a very simple filesystem. Then we can make a zipper for that filesystem, which will allow us to move between folders, just as we do when jumping around a real file- system. Here’s a data type for this and some type synonyms, so we know what’s what:

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

Here’s a folder with some files and subfolders

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

Now that we have a filesystem, all we need is a zipper so we can zip and zoom around it, and add, modify, and remove files and folders.

If we’re focusing on the folder "root", and we then focus on the file "dijonpoupon.doc", what should the breadcrumb that we leave look like? Well, it should contain the name of its parent folder along with the items that come before and after the file on which we’re focusing. So, all we need is a Name and two lists of items. By keeping separate lists for the items that come before the item that we’re focusing on and for the items that come af- ter it, we know exactly where to place it once we move back up. That way, we know the location of the hole. Here’s our breadcrumb type for the filesystem:

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

And here’s a type synonym for our zipper:

type FSZipper = (FSItem, [FSCrumb])

Going back up in the hierarchy is very simple. We just take the latest breadcrumb and assemble a new focus from the current focus and bread- crumb, like so

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

Because our breadcrumb knew the parent folder’s name, as well as the items that came before our focused item in the folder (that’s ls) and the items that came after (that’s rs), moving up was easy.

How about going deeper into the filesystem?

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 takes a Name and a FSZipper and returns a new FSZipper that focuses on the file with the given name. That file must be in the current focused folder.

First, we use break to break the list of items in a folder into those that precede the file that we’re searching for and those that come after it. break takes a predicate and a list and returns a pair of lists. The first list in the pair holds items for which the predicate returns False. Then, once the predicate returns True for an item, it places that item and the rest of the list in the second item of the pair. We made an auxiliary function called nameIs, which takes a name and a filesystem item and returns True if the names match.

Now ls is a list that contains the items that precede the item that we’re searching for, item is that very item, and rs is the list of items that come after it in its folder.

So, we can move up and down our filesystem. Let’s start at the root and walk to the file "skullman(scary).bmp":

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

newFocus is now a zipper that’s focused on the "skullman(scary).bmp" file.

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

Let’s move up and focus on its neighboring file "watermelonsmash.gif"

ghci>let newFocus2 = newFocus -: fsUp -: fsTo "watermelon_smash.gif"ghci>fst newFocusFile "skull_man(scary).bmp" "Yikes!"

Now that we can navigate our filesystem, manipulating it is easy. Here’s a function that renames the currently focused file or folder:

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

Let’s rename our "pics" folder to "cspi":

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

How about a function that makes a new item in the current folder?

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

Let’s add a file to our "pics" folder, and then move back up to the root

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

So far, while walking through our data structures—whether they were binary trees, lists, or filesystems—we didn’t really care if we took a step too far and fell off.For instance, our goLeft function:

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

But what if the tree we’re stepping off from is an empty tree? What if it’s not a Node, but an Empty? In this case, we would get a runtime error, because the pattern match would fail, and we have not made a pattern to handle an empty tree, which doesn’t have any subtrees.

In other words, any move can result in a success, but it can also result in a failure. Does that remind you of something? Of course: monads! More specifically, the Maybe monad, which adds a context of possible failure to normal values.

First, let’s take care of possible failure in goLeft and goRight.

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  

Now, if we try to take a step to the left of an empty tree, we get a Nothing!

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

Let’s modify goUp to fail gracefully:

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  

Before, these functions took zippers and returned zippers, which meant that we could chain them like this to walk around:

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

But now, instead of returning Zipper a, they return Maybe (Zipper a), and chaining functions like this won’t work. We had a similar problem when we were dealing with our tightrope walker in Chapter 13. So just like our tightrope walker, we’re going to trade in all our -: operators for >>= opera- tors. Then we will be able to chain our functions again! Watch how it works:

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

Now we’ve equipped our trees with a safety net that will catch us should we fall off.