haskell 无法将预期的型别'Tree a3'与实际型别'a'相符,'' '是由的型别签章所系结的固定型别变数

velaa5lx  于 2022-11-14  发布在  其他
关注(0)|答案(2)|浏览(126)

我遇到了这个定义的错误,不知道为什么。

定义:

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

功能:

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

错误:

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]
llycmphe

llycmphe1#

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

考虑在一个简单的测试输入上评估这个函数时会发生什么。

-- | A small example tree:
--
-- > 1
-- > ├ 2
-- > └ 3
--
smallExample :: Tree Int
smallExample = Node 1 [Leaf 2, Leaf 3]
  • 是的。
  • Node 1 [Leaf 2, Leaf 3]与第一个模式Leaf a不匹配,因此我们跳过第一个子句。
  • Node 1 [Leaf 2, Leaf 3]与第二个模式Node l r匹配,因此我们采用第二个子句。
  • l是类型为Int1
  • r是类型为[Tree Int][Leaf 2, Leaf 3]
  • 就是1 + count 1 + count [Leaf 2, Leaf 3]

现在有两个矛盾:
1.在count l中,IntTree a不匹配,这可以通过从求和中完全移除count l来解决,因为1已经代表了对Node的计数。
1.在count r中,[Tree a]Tree a不匹配。这可以通过使用map来计算所有子树的大小,并使用sum将它们相加来解决。

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

一些改进是可能的。lr不是很有用的名字。l看起来像一个左子树,但它是树中的元素; r看起来像一个右子树,但它是一个子树列表。

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

现在,这在一个更复杂的例子中起作用。

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

count largerExample是3。

7gcisfzg

7gcisfzg2#

错误消息非常清楚:您正在尝试将count函数应用于[Tree a]值,但它需要Tree a值(只是一棵树,而不是树列表)。
要使它编译,你需要以某种方式处理这个列表。你可以像这样使用Data.List.foldl函数:

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

相关问题