• Choose a category
• All
• Classic-Fiction

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. What is actually happening here? Well, we pattern match on our tree and name its root element x (that becomes the 'P' in the root) and its left subtree l. Instead of giving a name to its right subtree, we further pattern match on it. We continue this pattern matching until we reach the subtree whose root is our 'W'. Once we’ve made the match, we rebuild the 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. The directions will be either L or R, representing left or right, respectively, and we’ll change the element that we arrive at by following the supplied directions. Check it out:

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

If the first element in the list of directions is L, we construct a new tree that’s like the old tree, but its left subtree has an element changed to 'P'. When we recursively call changeToP, we give it only the tail of the list of directions, because we already took a left. We do the same thing in the case of an R. If the list of directions is empty, that means that we’re at our destination, so we return a tree that’s like the one supplied, except that it has 'P' as its root element.

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

This function is actually quite similar to changeToP. The difference is that instead of remembering stuff along the way and reconstructing the tree, it ignores everything except its destination. Here, we change the 'W' to a 'P' and see if the change in our new tree sticks:

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. A direction list of [R] focuses on the subtree that’s to the right of the root, for example. An empty direction list focuses on the main tree itself.

While this technique may seem cool, it can be rather inefficient, especially if we want to repeatedly change elements. Say we have a really huge tree and a long direction list that points to some element all the way at the bottom of the tree. We use the direction list to take a walk along the tree and change an element at the bottom. If we want to change another element that’s close to the element that we just changed, we need to start from the root of the tree and walk all the way to the bottom again. What a drag!

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.

A Trail of Breadcrumbs

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 (L and R values), but instead of calling it Directions, 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