在Haskell中计算树中的元素

Question

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

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

所以我可以像这样定义一个Ints树:

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,不够通用.

Answer 2

看你最后一句:看左边Node x y z,看,是什么类型的y？是否size y有意义？