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