Tree traversal confusion?

Question

I have the following data type (source: http://learnyouahaskell.com/zippers):

data Tree a = Empty | Node a (Tree a) (Tree a) deriving (Show, Eq, Ord)

I then have the following function, that traverses the tree and replaces a Node based on directional instructions:

data Direction = L | R deriving (Show, Eq, Ord)
type Directions = [Direction]

changeNode :: Directions -> Tree Char -> Tree Char
changeNode (L : ds) (Node x l r) = Node x (changeNode ds l) r
changeNode (R : ds) (Node x l r) = Node x l (changeNode ds r)
changeNode [] (Node _ l r) = Node 'P' r l

However I don't understand this aspect of the function:

changeNode (L : ds) (Node x l r) = Node x (changeNode ds l) r

I see that this is using recursion (changeNode ds l), but I don't understand why this is using recursion.

Does anyone have a simple explanation?

Answer 1

This may not be the simple explanation you were hoping for, but it may help to try working through a short example. Read the following with pencil and paper handy and try to verify everything for yourself:

changeNode [L,R]
  (Node 'A' (Node 'B' Empty (Node 'C' Empty Empty)) (Node 'D' Empty Empty))

I assume you'll agree that this should go left into the Node 'B' branch and then right into the Node 'C' branch, eventually replacing the 'C' with a 'P', right?

How does it do this? Well, the above expression matches the first pattern for changeNode, the one right after its type declaration. Specifically, it matches with variable assignments: ds=[R], x='A', l=the whole Node 'B' branch, and r=the whole Node 'D' branch. Therefore, we can rewrite it using the right hand side corresponding to that matching pattern. The right hand side for the pattern is:

Node x (changeNode ds l) r

and substituting the matched variables gives:

Node 'A' (changeNode [R] (Node 'B' Empty (Node 'C' Empty Empty)))
         (Node 'D' Empty Empty)    -- (1)

Now do you see what's happened? The first pattern for changeNode operates by "consuming" the first letter of the direction list (which has changed from [L,R] to [R]) and sort of pushing the changeNode call down into the left branch.

Now, concentrate on the value of this recursive changeNode call. This time it matches the second pattern for changeNode (with ds=[], x='B', l=Empty, and r=(Node 'C' Empty Empty)). The RHS for this pattern is:

Node x l (changeNode ds r)

which becomes (with the appropriate subtitutions):

Node 'B' Empty (changeNode [] (Node 'C' Empty Empty))

and substituting this value back into line (1), we get:

Node 'A' (Node 'B' Empty (changeNode [] (Node 'C' Empty Empty)))
         (Node 'D' Empty Empty)   -- (2)

Again, see how this second call has consumed the 'R' from the direction vector and pushed the changeNode call into the right branch of Node 'B'. Finally, what's the value of this last recursive changeNode call? Well, it matches the third pattern with l=Empty and r=Empty giving the RHS value:

Node 'P' Empty Empty

and substituting in to line (2), we get:

Node 'A' (Node 'B' Empty (Node 'P' Empty Empty)) (Node 'D' Empty Empty)

which was exactly what we wanted.

Contrast all this to what would have happened if the definition had been non-recursive:

changeNode' :: Directions -> Tree Char -> Tree Char
changeNode' (L : ds) (Node x l r) = Node x l r
changeNode' (R : ds) (Node x l r) = Node x l r
changeNode' [] (Node _ l r) = Node 'P' r l

In this case, our simple example would have matched the first pattern, again, with ds=[R], x='A', l=all of Node 'B' branch, r=all of Node 'D' branch, but instead of line (1), we would have used the non-recursive right hand side "Node x l r" to get the following in place of line (1):

Node 'A' (Node 'B' Empty (Node 'C' Empty Empty)) (Node 'D' Empty Empty)

See? Without the recursive call, after changeNode' consumes the 'L', it's finished. It returns the original tree with no further processing. The recursive call is needed to keep the process moving along until the direction vector is empty and the third pattern (the only one that actually changes a node) can be applied at the right place in the tree.

So, the short explanation (which doesn't really make sense until you've worked through the above example) is that the first two, recursive patterns for changeNode are used to move the changeNode call through the tree structure to the final target node where the final pattern is applied to change the node value.