Hi Chris,
On Fri, Jul 25, 2008 at 12:44 AM, Chris Eidhof
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.
<snip>
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.
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)
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. Cheers, -- Matt