I am 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 to addNums myNumsbe 36, but this causes 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 don't seem to be accepted at all Empty! I forgot what []is a valid type instance [Tree a]. Therefore, 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)
source
share