CODEWITHSUNDEEP
haskellcountfunctional-programmingtreenodes
simplesystems
simplesystems

Reputation: 849

Haskell: Count Nodes of a Tree

I have a custom Datatype:

data Tree a = Node a [Tree a]

an example tree:

tree1 = Node 3 [Node 4 [Node 3 [], Node 2 []], Node 5 []]

and I am struggling while trying to create a function to count the Nodes of the tree.

I have a function:

numNodes :: Num p => Tree a -> p
numNodes(Node a []) = 0
numNodes(Node a b) = 1 + numNodes b

But that is not really working, where am I wrong?

Edit: Compiler output:

   • Couldn't match type ‘Tree a’ with ‘[Tree a]’
      Expected type: [Tree a] -> p
        Actual type: Tree a -> p

   • Relevant bindings include
        numNodes :: [Tree a] -> p (bound at tree.hs:28:1)


28 | numNodes(Node a []) = 0

Upvotes: 0

Views: 829

Answers (1)

chepner
chepner

Reputation: 530950

First, you can't represent an empty tree with your data type; you can only represent a tree with a single node with no subtrees.

numNodes (Node a []) = 1

Second, each node as 0 or more substrees as children. You need to use map to compute the number of nodes in each subtree, then sum up the counts for each children.

numNodes (Node a b) = 1 + sum (map numNodes b)

Because sum [] == 0 by definition, you don't actually need the base case, as sum (map numNodes b) will return the correct count whether or not b is non-empty.

Upvotes: 3

Related Questions