Learn You a Haskell for Great Good! - Miran Lipovaca [158]
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.
Here’s a function to go right:
goRight :: (Tree a, Breadcrumbs) -> (Tree a, Breadcrumbs)
goRight (Node _ _ r, bs) = (r, R:bs)
It works the same way as the one to go left.
Let’s use these functions to take our freeTree and go right and then left.
ghci> goLeft (goRight (freeTree, []))
(Node 'W' (Node 'C' Empty Empty) (Node 'R' Empty Empty),[L,R])
Now we have a tree that has 'W' in its root, 'C' in the root of its left subtree, and 'R' in the root of its right subtree. The breadcrumbs are [L,R], because we first went right and then went left.
To make walking along our tree clearer, we can use the -: function from Chapter 13 that we defined like so:
x -: f = f x
This allows us to apply functions to values by first writing the value, then a -:, and then the function. So, instead of goRight (freeTree, []), we can write (freeTree, []) -: goRight. Using this form, we can rewrite the preceding example so that it’s more apparent that we’re going right and then left:
ghci> (freeTree, []) -: goRight -: goLeft
(Node 'W' (Node 'C' Empty Empty) (Node 'R' Empty Empty),[L,R])
Going Back Up
What if we want to go back up in our tree? From our breadcrumbs, we know that the current tree is the left subtree of its parent and that it is the right subtree of its parent, and that’s all we know. 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. In this case, that’s the element in the parent tree along with its right subtree.
In general, a single breadcrumb should contain all the data needed to reconstruct the parent node. So, it should have the information from all the paths that we didn’t take, and it should also know the direction that we did take. However, it must not contain the subtree on which we’re currently focusing. That’s because we already have that subtree in the first component of the tuple. If we also had it in the breadcrumb, we would have duplicate information.
We don’t want duplicate information because if we were to change some elements in the subtree that we’re focusing on, the existing information in the breadcrumbs would be inconsistent with the changes that we made. The duplicate information becomes outdated as soon as we change something in our focus. It can also hog a lot of memory if our tree contains a lot of elements.
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)
Now, instead of just L, we have a LeftCrumb, which also contains the element in the node that we moved from and the right tree that we didn’t visit. Instead of R, we have RightCrumb, which contains the element in the node that we moved from and the left tree that we didn’t visit.
These breadcrumbs now contain all the data needed to re-create the tree that we walked through. So, instead of just being normal breadcrumbs, they’re more like floppy disks that we leave as we go along, because they contain a lot more information than just the direction that we took.
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 information 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