Learn You a Haskell for Great Good! - Miran Lipovaca [160]
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. The code for this is simple:
attach :: Tree a -> Zipper a -> Zipper a
attach 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. Let’s attach a tree to the far left of our freeTree:
ghci> let farLeft = (freeTree, []) -: goLeft -: goLeft -: goLeft -: goLeft
ghci> let newFocus = farLeft -: attach (Node 'Z' Empty Empty)
newFocus is now focused on the tree that we just attached, and the rest of the tree lies inverted in the breadcrumbs. If we were to use goUp to walk all the way to the top of the tree, it would be the same tree as freeTree, but with an additional 'Z' on its far left.
Going Straight to the Top, Where the Air Is Fresh and Clean!
Making a function that walks all the way to the top of the tree, regardless of what we’re focusing on, is really easy. Here it is:
topMost :: Zipper a -> Zipper a
topMost (t, []) = (t, [])
topMost z = topMost (goUp z)
If our trail of beefed-up breadcrumbs is empty, that means we’re already at the root of our tree, so we just return the current focus. Otherwise, we go up to get the focus of the parent node, and then recursively apply topMost to that.
So, now we can walk around our tree, going left, right, and up, applying modify and attach as we travel. Then, when we’re finished with our modifications, we use topMost to focus on the root of our tree and see the changes that we’ve made in proper perspective.
Focusing on Lists
Zippers can be used with pretty much any data structure, so it’s no surprise that they work with sublists of lists. After all, lists are pretty much like trees, except where a node in a tree has an element (or not) and several subtrees, a node in a list has an element and only a single sublist. When we implemented our own lists in Chapter 7, we defined our data type like so:
data List a = Empty | Cons a (List a) deriving (Show, Read, Eq, Ord)
Compare this with the definition of our binary tree, and it’s easy to see how lists can be viewed as trees where each node has only one subtree.
A list like [1,2,3] can be written as 1:2:3:[]. It consists of the head of the list, which is 1, and then the list’s tail, which is 2:3:[]. 2:3:[] also has a head, which is 2, and a tail, which is 3:[]. With 3:[], the 3 is the head, and the tail is the empty list [].
Let’s make a zipper for lists. To change the focus on sublists of a list, we move either forward or back (whereas with trees, we move up, left, or right). The focused part will be a subtree, and along with that, we’ll leave breadcrumbs as we move forward.
Now, what would a single breadcrumb for a list consist of? When we were dealing with binary trees, the breadcrumb needed to hold the element in the root of the parent node along with all the subtrees that we didn’t choose. It also had to remember if we went left or right. So, it needed to have all the information that a node has, except for the subtree on which we chose to focus.
Lists are simpler than trees. We don’t need to remember if we went left or right, because there’s only one way to go deeper into a list. Because there’s only one subtree to each node, we don’t need to remember the paths that we didn’t take either. It seems that all we must remember is the previous element. If we have a list like [3,4,5] and we know that the previous element was 2, we can go back by just putting that element at the head of our list, getting [2,3,4,5].
Because a single breadcrumb here is just the element, we don’t really