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

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

(Nodea型和BinaryTreea型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