对Haskell中树中的元素进行计数

Question

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

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

所以我可以像这样定义一个Int树：

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

从技术上讲，之所以会出现错误，是因为只有当y是一棵可以计算其大小的树时，术语size y才有意义。因此，这个子句的类型将被推断为Tree (Tree a) -> Int，这与实际的Tree a -> Int相比，不够通用。

Answer 2

看看你的最后一个子句:看左边，在Node x y z，y的类型是什么？size y有意义吗？