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
iscount (Node 1 [Leaf 2, Leaf 3])
.Node 1 [Leaf 2, Leaf 3]
doesn’t match the first patternLeaf a
, so we skip the first clause.Node 1 [Leaf 2, Leaf 3]
matches the second patternNode l r
, so we take the second clause.l
is1
of typeInt
.r
is[Leaf 2, Leaf 3]
of type[Tree Int]
.1 count l count r
is1 count 1 count [Leaf 2, Leaf 3]
.
Now there are two inconsistencies:
In
count l
,Int
doesn’t matchTree a
. This can be solved by removingcount l
from the summation altogether, because the1
already represents counting theNode
.In
count r
,[Tree a]
doesn’t matchTree a
. This can be solved by usingmap
to count all of the subtrees’ sizes, andsum
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.