haskell - 在 Haskell 中计算树中的元素

Question

基本上我已经创建了一个多态树数据类型，并且我需要一种计算给定树中元素数量的方法。这是我的 Tree 数据类型的声明:

data Tree a = Empty
| Leaf a
| Node (Tree a) a (Tree a)
deriving (Eq, Ord, Show)

所以我可以像这样定义一棵整数树:

t :: Tree Int
t = Node (Leaf 5) 7 (Node (Leaf 2) 3 (Leaf 7))

但是，我需要一个函数来计算这些列表之一中的元素数量。我已经定义了这个递归函数，但收到错误“推断的类型不够通用”:

size :: Tree a -> Int
size Empty   = 0
size (Leaf n)    = 1
size (Node x y z)    = size x + size y + size z

这里有什么我不应该做的事情吗？

Answer 1

我认为这只是你写的时候的错字

size (Node x y z) = size x + size y + size z

应该是这样

size (Node x y z) = size x + size z + 1

因为 y 不是子树，而只是存储的元素。

或者让它更清楚

size (Node left elem right) = size left + size right + 1

<小时/>

从技术上讲，发生错误是因为术语 size y 仅当 y 再次是大小可计算的树时才有意义。因此，该子句的类型将被推断为 Tree (Tree a) -> Int，即与实际的 Tree a -> Int 相比，不是一般的够了。