haskellbinary-treenon-exhaustive-patterns

Haskell Data Declaration : Find sum of Leaves in a binary Tree

Here is a binary tree, and i am trying to calculate the sum of the leaves

             -1
            /   \
          -5     10
          / \   
        -4  30  
        / \
       13  17

The data declaration is given.

data Tree = TNode Int [ Tree ] | TLeaf Int

and here is my code

let t = TNode (-1) [TNode (-5)  [  TNode (-4) [ Tleaf 13, Tleaf 17] ,  Tleaf 30 ] ,Tleaf 10 ]

sumLeaves (Tleaf x)= x
sumLeaves (TNode x [tree])=  sum[sumLeaves tree]

When i run the program sumLeaves t,it shows that there is non-exhaustive patterns in the function sumLeaves.I think the problem is the programm can't count,when there is a node with two leaves,but i don't know how to solve it.A little help is really appreciated.

Edited : test1:

 sumLeaves1 (Tleaf x)= [x]
    sumLeaves1 (TNode x [Tleaf y])=[y]
    sumLeaves1 (TNode x (y:ys))= sum ( (sumLeaves1 y) ++ (sumLeaves1 (TNode x ys)) )

test 2:

 sumLeaves (Tleaf x)= x
    sumLeaves (TNode x [Tleaf y])=y
    sumLeaves (TNode x (y:ys))= (sumLeaves y) + sumLeaves (TNode x ys)

test 2 works fine,but test 1 gives error, when i remove the sum(),it gives a list [13,17,30,10] ,which is the correct list, but >sum ( [13,17,30,10]) works in programm.How can i overcome it?

Solution

  • Your (Tnode x [tree]) only matches if the node has exactly one subtree. You should match any value of sublistlist, so:

    sumLeaves :: Tree -> Int
sumLeaves (Tleaf x) = x
sumLeaves (TNode x trees) = sum (…)

    here the … should create a list of the sums of the children of the node. You thus should make a mapping for each element in trees. I leave this as an exercise. You might want to look at map :: (a -> b) -> [a] -> [b].

    That being said, you do not have to sum the elements yourself. You can lift the Tree data type and make use of the DeriveFoldable extension to let Haskell derive a Foldable instance for you:

    {-# LANGUAGE DeriveFoldable #-}

data Tree a = TNode a [ Tree a ] | TLeaf a deriving Foldable

    The sum :: (Foldable f, Num a) => f a -> a is defined on any Foldable, so we can then sum with:

    Prelude> sum (TNode (-1) [TNode (-5)  [  TNode (-4) [ TLeaf 13, TLeaf 17] ,  TLeaf 30 ] ,TLeaf 10 ])
60