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

[Chris Eidhof]

Hey Matt,

On 27 jul 2008, at 12:57, Quergle Quergle wrote:
> Thanks for pointing me at foldTree. I'm afraid the best I was able to
> come up with is the rather clunky:
>
>> updateTree'' :: Tree a -> Path -> a -> Tree a
>> updateTree'' tree = (foldTree leaf node tree) True
>>  where leaf currentValue True [] newValue = Leaf newValue
>>        leaf currentValue True path@(_:_) newValue = error ("Invalid  
>> path at leaf -- still has elements: " ++ show path)
>>        leaf currentValue False _ newValue = Leaf currentValue
>>        node left right True (GoLeft:ps) newValue = Node (left True  
>> ps newValue) (right False ps newValue)
>>        node left right True (GoRight:ps) newValue = Node (left  
>> False ps newValue) (right True ps newValue)
>>        node _ _  True [] _ = error "Invalid path at node -- no  
>> elements left"
>>        node left right False (p:ps) newValue = Node (left False ps  
>> newValue) (right False ps newValue)
>>        node left right False [] newValue = Node (left False []  
>> newValue) (right False [] newValue)

The version I came up with was basically the same. Here are some minor  
things of your code:

path@(_:_) can be rewritten as path, because you already know it's not  
an empty list.

The last two lines of node can be merged into one line, because as  
soon as we are at a False, we don't care about the path anymore:
node left right False _ newValue = Node (left False [] newValue)  
(right False [] newValue)

> I guess one downside to using foldTree is that it seems I'm obliged to
> visit every node in the tree, so the updated tree I get back is a deep
> copy of the one passed in, whereas ideally it'd share as much of the
> tree as is unchanged by the update.

Yes, indeed. However, folds are a nice way to factor out recursion and  
can make life a whole lot easier. For example, it is easy to define  
map and filter (functions that work on a list) in terms of fold (which  
also works on a list). Similarly, it isn't too hard to define  
mapTree :: Tree a -> Tree b in terms of foldTree. In a way, folding is  
a really essential traversal of a data structure, so it can be seen as  
a primitive.

A really nice exercise is to try and define filter, map and sum in  
terms of fold, and compare those with the versions that have explicit  
recursion. If you take, for example, map and sum:

map f [] = []
map f (x:xs) = f x : map f xs

sum [] = 0
sum (x:xs) = x + sum xs

You'll see that they have almost the same structure (visually). If you  
factor out the differing bits, you'll probably come up with the  
definition of fold!

Have fun,
-chris