Summing an Integer Tree (Haskell)

Question

I'm trying to make a function that sums up the values of a non-binary integer tree.

-- datastructures.hs    
data Tree a = Empty | Node a [Tree a] deriving (Eq, Show)

myNums :: (Num a) => Tree a
myNums = Node 1 [ 
           Node 2 [ 
             Node 4 [Empty], Node 5 [Empty]
           ], 
           Node 3 [
             Node 6 [Empty], Node 7 [Empty], Node 8 [Empty] 
           ]
        ]

addNums :: (Num a) => Tree a -> a
addNums Empty = 0
addNums (Node n [Empty]) = n
addNums (Node n (x:xs)) = n + (addNums x) + (addNums xs)

Ideally, I would like addNums myNums to be 36, but this produces an error:

datastructures.hs:20:54:
    Couldn't match expected type ‘Tree a’ with actual type ‘[Tree a]’
    Relevant bindings include
      xs :: [Tree a] (bound at datastructures.hs:20:20)
      x :: Tree a (bound at datastructures.hs:20:18)
      n :: a (bound at datastructures.hs:20:15)
      addNums :: Tree a -> a (bound at datastructures.hs:18:1)
    In the first argument of ‘addNums’, namely ‘xs’
    In the second argument of ‘(+)’, namely ‘(addNums xs)’

How do I counter this, and what are the best practices?

EDIT: Best practices seem to omit Empty altogether! I forgot that [] is a valid instance of type [Tree a]. So the best way to implement this is:

data Tree a = Node a [Tree a] deriving (Eq, Show)

addNums :: (Num a) => Tree a -> a
addNums (Node n []) = n
addNums (Node n (x:xs)) = n + (addNums x) + addNums (Node 0 xs)

`(addNum x) + (addNum xs)`. Can't work. `x` and `xs` are of different types here. — n. m. could be an AI, Dec 20 '15 at 05:40
This doesn't work either though: `addNums (Node n (x:xs)) = n + (addNums x) + foldl1 (\ acc t -> acc + addNums t) xs` — Mark Karavan, Dec 20 '15 at 05:46
Also note that your tree has redundant representation. `Node 1 []` and `Node 1 [Empty]` and `Node 1 [Empty,Empty,Empty]` all represent the same tree. Perhaps you want to change that, or at least handle the `[]` case. — n. m. could be an AI, Dec 20 '15 at 05:57
Oh wow, you're right. I don't even need `Empty` as a constructor at all. — Mark Karavan, Dec 20 '15 at 06:07
@MarkKaravan Note that if you remove `Empty`, every tree has to include at least one element `n`. — chi, Dec 20 '15 at 09:05

score 5 · Answer 1 · answered Dec 20 '15 at 09:13

5

Just derive Foldable and use the existing sum:

{-# LANGUAGE DeriveFoldable #-}

data Tree a = Empty | Node a [Tree a] deriving (Eq, Show, Foldable)

myNums :: (Num a) => Tree a
myNums = ...

main = print $ sum myNums

answered Dec 20 '15 at 09:13

effectfully

12,325
2
17
40

1

@Mark Karavan, [yes](http://osa1.net/posts/2015-11-13-data-repr-1.html), as well as in the other answers, it leaks. You can use `fasterSum = foldl' (+) 0` (`foldl'` comes with `Foldable` as well), but I wouldn't be suprised if it leaks too. You can open another question about efficient summing of numbers in a tree. – effectfully Dec 21 '15 at 21:32

score 4 · Answer 2 · answered Dec 20 '15 at 09:02

A possible solution:

addNums :: (Num a) => Tree a -> a
addNums Empty = 0
addNums (Node n xs) = n + sum (map addNums xs)

In the recursive case, we have a list of trees xs. We can use addNums on each of those trees, obtaining a list of numbers. Then, we simply sum them up, and add the root n.

score 2 · Accepted Answer · answered Dec 20 '15 at 05:46

2

The problem is in the last two lines of your addNums definition. You have to check for the empty base case, not when the list contains a single element with Empty inside it. Something like this should work:

addNums :: (Num a) => Tree a -> a
addNums Empty = 0
addNums (Node n []) = n
addNums (Node n (x:xs)) = n + (addNums x) + addNums (Node 0 xs)

Note that for an empty list you are just returning n. And when the list has more than one elements, you recursively sum it untill it reaches the bae case (i.e the list becomes empty).

Demo in ghci:

λ> addNums myNums
36

answered Dec 20 '15 at 05:46

Sibi

47,472
16
95
163

It took me a minute to understand why you needed that `[]` pattern (since any `[Tree a]` has to contain at least an `Empty`, but now I see you are evaluating it against your own `Node 0`. This seems awkward; is there a best practice for this kind of tree? – Mark Karavan Dec 20 '15 at 06:01
2

@MarkKaravan Even then you have to check for `[]` case or else your pattern match will be non exhaustive. You can abstract the entire thing using `foldl` as user2407038 has demonstrated. – Sibi Dec 20 '15 at 06:10

Summing an Integer Tree (Haskell)

3 Answers3

Linked