[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)
xs)
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?
Cheers,
-- 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