[Haskell-beginners] Re: [Haskell-begin] Looking for cunning ways to
update a tree
Chris Eidhof
chris at eidhof.nl
Mon Jul 28 06:12:38 EDT 2008
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
More information about the Beginners
mailing list