[Haskell-begin] Looking for cunning ways to update a tree

[Chris Eidhof]

Hey Matt,

On 24 jul 2008, at 20:29, Quergle Quergle wrote:

> Hello all,
>
> This is a really helpful list: I've learned half a dozen new things  
> just by reading this month's traffic. Anyway...I have the following  
> bit of code that updates a tree structure given a route to a leaf:
>
> [...]
>
> I wanted to rewrite updateTree without using explicit recursion.  
> Unfortunately, the best I could come up with is:
>
> [...]
>
> So what's the sexier way of doing this?

The trick here is to define a fold for a tree. A fold is a function  
that does all the recursion, and you can then define other functions  
in terms of that fold. The type of the fold function is based on the  
structure of your data.

So, for the fold of the tree, you basically first have to take two  
functions:

 > leaf :: a -> r
 > node :: r -> r -> r

The leaf function will act on Leaf's, and take a value of type a and  
turn it into a result. The node function will first compute the result  
for the recursive parts (so this is where the recursion happens), and  
then needs to combine those results. The full type of our function  
foldTree looks like this:

 > foldTree :: (a -> r) -> (r -> r -> r) -> Tree a -> r

And the implementation looks like this:

 > foldTree leaf node (Leaf a) = leaf a
 > foldTree leaf node (Node a b) = node (foldTree leaf node a)  
(foldTree leaf node b)

Now, to find a value in the tree using your Path type, we want the  
following type:

 > findTree :: Tree a -> Path -> a

So suppose we give our foldTree two arguments to handle both the Node  
and the Leaf, we will end up with a function that has type:

 > Tree a -> r

Now, what will we choose for r? Of course, it has to be Path a -> a!

We now need a function (a -> Path a -> a) and a function (Path a -> a)  
-> (Path a -> a) -> (Path a -> a). When we remove unnecessary  
parentheses, the type is (Path a -> a) -> (Path a -> a) -> Path a -> a

The first one is easy, we just ignore the second argument:

 > findLeaf a _ = a

The second one takes three arguments: the left value, the right value  
and the path. Based on the path we need to choose wheter to choose the  
left or the right value:

 > findNode left right (p:ps) = case p of
 >   GoLeft  -> left ps
 >   GoRight -> right ps

Now we can take these parts and compose them into the findTree function:

 > findTree t p = foldTree findLeaf findNode t p

And because Haskell will save us from unnecessary typing, we could  
also write it shorter:

 > findTree = foldTree const findNode

Note that we didn't use any recursion in our findTree! It would be  
cool if you could try to come up with a definition of updateTree in  
terms of foldTree.

Have fun,
-chris

P.S.: Here's the full code:

 > foldTree :: (a -> r) -> (r -> r -> r) -> Tree a -> r
 > foldTree leaf node (Leaf a)   = leaf a
 > foldTree leaf node (Node a b) = node (rec a) (rec b)
 >  where rec = foldTree leaf node
 >
 > findTree :: Tree a -> Path -> a
 > findTree = foldTree const findNode
 >  where findNode left right (p:ps) = case p of
 >          GoLeft  -> left  ps
 >          GoRight -> right ps