• Choose a category
• All
• Classic-Fiction

type Breadcrumbs a = [Crumb a]

Next up, we need to modify the goLeft and goRight functions to store information 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.

Note that this function assumes that the current tree that’s under focus isn’t Empty. An empty tree doesn’t have any subtrees, so if we try to go left from an empty tree, an error will occur. This is because the pattern match on Node won’t succeed, and there’s no pattern that takes care of Empty.

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)

We’re focusing on the tree t, and we check the latest Crumb. If it’s a LeftCrumb, we construct a new tree using our tree t as the left subtree and using the information about the right subtree and element that we didn’t visit to fill out the rest of the Node. Because we “moved back” and picked up the last breadcrumb, then used it to re-create the parent tree, the new list doesn’t contain that breadcrumb.

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 represent possible failure when moving focus.

With a pair of Tree a and Breadcrumbs a, we have all the information we need to rebuild the whole tree, and we also have a focus on a subtree. This scheme enables us to easily move up, left, and right.

A pair that contains a focused part of a data structure and its surroundings is called a zipper, because moving our focus up and down the data structure 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)

I would prefer naming the type synonym Focus, because that makes it clearer that we’re focusing on a part of a data structure. But since the name Zipper is more widely used to describe such a setup, we’ll stick with it.

Manipulating Trees Under Focus

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 a

modify f (Node x l r, bs) = (Node (f x) l r, bs)

modify f (Empty, bs) = (Empty, bs)

If we’re focusing on a node, we modify its root element with the function f. If we’re focusing on an empty tree, we leave it as is. Now we can start off with a tree, move to anywhere we want, and modify an element, all while keeping focus on that element so that we can easily move further up or down. Here’s an example:

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

We go left, then right, and then modify the root element by replacing it with a 'P'. 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 mysterious 'X':

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

Or we can write it with -::

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

Moving up is easy because the breadcrumbs that we leave form the part of the data structure that we’re not focusing on, but it’s inverted,