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

Question

假设我有以下数据类型:

数据二叉树 a = 空树 |节点a(BinaryTree a)(BinaryTree a)推导(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

此功能有效。

检查节点的类型:

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

但是，如果成员函数被赋予签名:member::Node a -> BinaryTree a -> Bool

(a 类型的 Node 和 a 类型的 BinaryTree 生成 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 不是类型；这是一个:

• 完全应用时 BinaryTree 类型的值
• 此类值的数据构造函数 (a -> BinaryTree a -> BinaryTree a -> BinaryTree a)

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

您的 member 函数很可能应该只使用该元素来检查其是否存在:

member :: a -> BinaryTree a -> Bool

如果您需要对 a 进行额外约束(对于二叉树，它将是 Ord 和 Eq，大多数也许，你也必须把它们放在那里。

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