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

Quergle Quergle quergle at googlemail.com
Thu Jul 24 14:29:23 EDT 2008

Hello all,

This is a really helpful list: I've learned half a dozen new things just by
reading this month's traffic. Anyway...I have the following bit of code that
updates a tree structure given a route to a leaf:

data Tree a = Leaf a | Node (Tree a) (Tree a)
              deriving (Show, Eq)
data PathSelector = GoLeft | GoRight
                    deriving (Show, Eq)
type Path = [PathSelector]

selectChild (Node left _) GoLeft = left
selectChild (Node  _ right ) GoRight = right

updateNode (Node _ right) GoLeft newLeft = Node newLeft right
updateNode (Node left _) GoRight newRight = Node left newRight

updateLeaf new (Leaf previous) = Leaf new

updateTree :: Tree a -> Path -> a -> Tree a
updateTree tree path newValue = case path of
                                 [] -> updateLeaf newValue tree
                                 (p:ps) -> updateNode tree p (updateTree'
(selectChild tree p) ps newValue)

I wanted to rewrite updateTree without using explicit recursion.
Unfortunately, the best I could come up with is:

upDownRecurse :: (a -> b -> a) -> (a -> c) -> (a -> b -> c -> c) -> a -> [b]
-> c
upDownRecurse down bottoming up = upDownRecurse'
    where upDownRecurse' acc [] = bottoming acc
          upDownRecurse' acc (x:xs) = up acc x (upDownRecurse' (down acc x)

updateTree' :: Tree a -> Path -> a -> Tree a
updateTree' tree path newValue = upDownRecurse selectChild (updateLeaf
newValue) updateNode tree path

So what's the sexier way of doing this?


-- Matt
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://www.haskell.org/pipermail/beginners/attachments/20080724/8a1b753f/attachment.htm

More information about the Beginners mailing list