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

[Quergle Quergle]

Hi Chris,

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.

<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