I am running into this error of definition, not sure of why exactly.

Definition:

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

Function:

count :: Tree a -> Integer
count (Leaf a) = 0
count (Node l r) = 1   count l   count r

Error:

Couldn't match expected type ‘Tree a2’
              with actual type ‘[Tree a]’
• In the first argument of ‘count’, namely ‘r’
  In the second argument of ‘( )’, namely ‘count r’
  In the expression: 1   count l   count r
• Relevant bindings include
    r :: [Tree a]

CodePudding user response：

The error message is pretty clear: You are trying to apply the count function to a value of [Tree a]. But it expects a value of Tree a (just a single tree, not a list of trees).

To make it compile you need to deal with the list somehow. You could use the Data.List.foldl function like this:

count :: Tree a -> Integer
count (Leaf a) = 0
count (Node l r) = 1   count l   foldl (\i t -> i   count t) 0 r

CodePudding user response：

count :: Tree a -> Integer
count (Leaf a) = 0
count (Node l r) = 1   count l   count r

Consider what would happen when evaluating this function on a simple test input.

-- | A small example tree:
--
-- > 1
-- > ├ 2
-- > └ 3
--
smallExample :: Tree Int
smallExample = Node 1 [Leaf 2, Leaf 3]

• count smallExample is count (Node 1 [Leaf 2, Leaf 3]).
• Node 1 [Leaf 2, Leaf 3] doesn’t match the first pattern Leaf a, so we skip the first clause.
• Node 1 [Leaf 2, Leaf 3] matches the second pattern Node l r, so we take the second clause.
  • l is 1 of type Int.
  • r is [Leaf 2, Leaf 3] of type [Tree Int].
  • 1 count l count r is 1 count 1 count [Leaf 2, Leaf 3].

Now there are two inconsistencies:

1. In count l, Int doesn’t match Tree a. This can be solved by removing count l from the summation altogether, because the 1 already represents counting the Node.

2. In count r, [Tree a] doesn’t match Tree a. This can be solved by using map to count all of the subtrees’ sizes, and sum to add them up.

   count (Node l r) = 1   sum (map count r)
   

A few improvements are possible. l and r are not very helpful names. l seems like a left subtree, but it’s an element in the tree; r seems like a right subtree, but it’s a list of subtrees.

count (Leaf _value) = 0
count (Node _value subtrees) = 1   sum (map count subtrees)

Now this works on a more complex example.

largerExample :: Tree Int
largerExample
  = Node 1      --  1
    [ Node 2    --  1
      [ Leaf 4  --  0
      ]
    , Node 3    --  1
      [ Leaf 5  --  0
      , Leaf 6  --  0
      ]
    ]

count largerExample is 3.