1

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?

John
  • 135
  • 6
  • the answer you are looking for is [this one](https://stackoverflow.com/a/14897649/849891) in the duplicate. – Will Ness Oct 09 '20 at 06:27

1 Answers1

2

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
Willem Van Onsem
  • 443,496
  • 30
  • 428
  • 555
  • 1
    i am confused about the DeriveFoldable extension, can the problem being solved without it? – John Oct 09 '20 at 01:38
  • @JohnTang: yes, the first section describes what the problem is, with the `...` left as exercise. – Willem Van Onsem Oct 09 '20 at 01:43
  • i have a question,is it sum(..) or sum[..],because when i type >sum (1,4) it gives 4 ,which is really confusing, but sum [1,4] works fine. – John Oct 09 '20 at 01:49
  • @JohnTang: that is because you work with a tuple, and you thus use the `Foldable` instance of a 2-tuple, but the `(...)` in the code should *generate* a list. If you however work with `[ x ]` you create a *singleton* list, a list containing one element. So you should simply look for an expression that generates a list. – Willem Van Onsem Oct 09 '20 at 01:50