我对二叉搜索树成员资格的功能测试有什么问题？

Question

假设我有以下数据类型：

data BinaryTree a = EmptyTree | Node a (BinaryTree a) (BinaryTree a) deriving (Eq, Ord, Show)

和以下函数

  member a EmptyTree = False
  member a (Node x l r)
    | a < x = member a l
    | a > x = member a r
    | a == x = True

这个功能有效。

正在检查 Node 的类型：

:t Node
Node :: a -> BinaryTree a -> BinaryTree a -> BinaryTree a

但是，如果给成员函数签名： member :: Node a -> BinaryTree a -> Bool

(Node 类型 a 和 BinaryTree 类型 a 产生 a Bool)

它出错了：

Not in scope: type constructor or class ‘Node’
A data constructor of that name is in scope; did you mean DataKinds?

这是为什么？我如何定义一个接受（并比较）任意类型的节点和树的函数？

Answer 1

Node 不是类型；这是一个：

两者实际上是同一个意思，但在两种不同的上下文中实现外观可能会有所帮助，即模式匹配和构造。

您的 member 函数很可能应该只获取元素以检查其是否存在：

member :: a -> BinaryTree a -> Bool

如果你需要对 a 的额外约束（在二叉树的情况下，它将是 Ord 和 Eq，很可能你必须把它们还有。

member :: (Ord a, Eq a) => a -> BinaryTree a -> Bool

What is wrong with my function testing for membership in a binary search tree?