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?
Your
(Tnode x [tree])
only matches if the node has exactly one subtree. You should match any value of sublistlist, so:here the
…
should create a list of the sums of the children of the node. You thus should make a mapping for each element intrees
. I leave this as an exercise. You might want to look atmap :: (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 theDeriveFoldable
extension to let Haskell derive aFoldable
instance for you:The
sum :: (Foldable f, Num a) => f a -> a
is defined on anyFoldable
, so we can then sum with: