[Haskell-beginners] recursion and pattern matching

[Brent Yorgey]

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':
> 
> 
> 
> <Test.hs>
> 
> 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) 
> 
> </Test.hs>
> 
> 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