[Haskell-begin] Looking for cunning ways to update a tree
quergle at googlemail.com
Sun Jul 27 06:57:20 EDT 2008
On Fri, Jul 25, 2008 at 12:44 AM, Chris Eidhof <chris at eidhof.nl> wrote:
> 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.
> 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.
More information about the Beginners