类型树应该是类型类Eq的一个实例

Question

我有以下数据结构，并希望它是类型类Eq.的实例

data Tree n l
= Node n (Tree n l) (Tree n l)
| Leaf l

我试着用下面的方法

instance Eq => (Tree n l) where
(Node a b c) == (Node d e f) = a == d
(Leaf a) == (Leaf b) = a == b

但是有一条错误信息

'=='不是类'Tree'的(可见(方法

Answer 1

这里有两个问题：

1. 您没有指定将Tree n l作为实例的类型；以及
2. 为了检查在给定的定义下，n和l都需要是作为Eq类型类实例的类型

所以你可以用来实现

instance(Eq n, Eq l)=>Eq(Tree n l) where
(Node a b c) == (Node d e f) = a == d
(Leaf a) == (Leaf b) = a == b

请注意，现在它将进行编译，但仍然存在一个问题：如果检查Node … … …是否等于Leaf …，则会引发错误，反之亦然。你可以为此添加一个额外的规则：

instance (Eq n, Eq l) => Eq (Tree n l) where
(Node a b c) == (Node d e f) = a == d
(Leaf a) == (Leaf b) = a == b
_ == _ = False

然而，在这里，您将认为两个Node … … …是相同的，从它们包装相同值的那一刻起。所以你不用看子树。为了解决这个问题，您需要执行递归。我把它当作练习。

Answer 2

我不确定您是否想要为树实现平等检查。

让

a = Node 2 (Leaf 1) (Leaf 2)
b = Node 2 (Leaf 100) (Leaf 200)

对于这两个树，您将得到a == b作为True，因为Nodes的比较仅比较该节点中的值，但子树被忽略。你甚至可以像这个一样定义你支票的那部分

(Node a _ _) == (Node d _ _) = a == d

以显示您忽略子树。

也许这是一种理想的行为，但在我看来，更正确的平等检查应该是这样的：

(Node x lx rx) == (Node y ly ry) = x == y && lx == ly && rx == ry

这不仅会检查节点的值，还会递归地检查子树，所以a == b现在会给你False，因为它们确实不同。