On Tue, Oct 18, 2011 at 01:34:14AM -0700, Alia wrote:
I have a question about what's the idiomatic way to walk a tree where there is also a requirement for pattern-matching to draw variables out of the Node 'container':
module Test
where
data Tree a b = EmptyTree | Node a b [Tree a b] deriving (Show, Read, Eq) t = Node "goal" 1.0 [ Node "c1" 0.5 [ Node "c3" 3.0 [ Node "c5" 1.0 [] ] ], Node "c2" 0.5 [ Node "c4" 2.0 [] ] ]
sumTree :: (Num b) => Tree a b -> b sumTree EmptyTree = 0 sumTree (Node _ value []) = value sumTree (Node _ value [x]) = value + sumTree x sumTree (Node name value (x:xs)) = value + sumTree x + sumTree (Node name 0 xs)
depth :: Tree a b -> Int depth EmptyTree = 0 depth (Node _ _ []) = 1 depth (Node _ _ [x]) = 1 + depth x depth (Node n v (x:xs)) = 1 + depth (Node n v xs)
Interactively:
*Test> sumTree t 8.0 *Test> depth t 4 *Test>
This seems to work, but I have a sense that one should use folds and fmap and that there is a better and cleaner what to do this.
Your sense is absolutely right! =) You are not taking advantage of the fact that [] is a functor and can be folded over, etc. -- you have essentially hardcoded a list fold into your sumTree and depth functions. First let's rewrite sumTree. We use 'map' to call 'sumTree' recursively on all the child trees, then sum the results: sumTree :: (Num b) => Tree a b -> b sumTree EmptyTree = 0 sumTree (Node _ value children) = value + sum (map sumTree children) Tada! We handled all those list cases (empty, single element, or cons) at once, in a general way. By the way, your implementation of 'depth' seems to be wrong: it only cares about the depth of the last child. I would think the idea would be to take the maximum depth of all the children and add one to that. I leave the rest for you: (1) rewrite depth in a similar way to sumTree, being sure to find the maximum depth of all the children (2) generalize both sumTree and depth to a treeFold function: treeFold :: c -> (a -> b -> [c] -> c) -> Tree a b -> c The first argument says what to do with EmptyTree, and the second argument says what to do with a Node. Once you have implemented treeFold you should be able to implement both sumTree and depth in terms of treeFold. Hope this helps. Let us know if you get stuck or have more questions! -Brent