计算Haskell中树中的元素

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

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

有东西在这里我不应该这样做？

来源

2010-02-07 benwad

我认为，当你写

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,相比不是通用的足够的。

来源

2010-02-07 17:21:32 Dario

难道不是'size x + 1 + size z'？由于他在计算元素，每个节点都包含一个元素。 – BaroqueBobcat 2010-02-07 17:26:14

@BaroqueBobcat：Argh ... Yep;） – Dario 2010-02-07 17:31:14

实际上，所写的'size'类型将是无限类型'Tree（Tree（Tree ...））） - > Int'。在这些情况下，一个好的方法是始终忽略违规类型签名，让编译器告诉你它认为应该是什么类型。在这种情况下，GHC告诉我，它试图构建一个无限类型... – yatima2975 2010-02-07 18:05:13

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

来源

2010-02-07 17:21:08 MtnViewMark

计算Haskell中树中的元素

回答

相关问题