CODEWITHSUNDEEP
haskelldata-structurestree
Mark Karavan
Mark Karavan

Reputation: 2674

Summing an Integer Tree (Haskell)

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)

Upvotes: 4

Views: 2133

Answers (3)

effectfully
effectfully

Reputation: 12715

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

Upvotes: 5

chi
chi

Reputation: 116139

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.

Upvotes: 4

Sibi
Sibi

Reputation: 48654

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

Upvotes: 2

Related Questions