类型树应为类型类Eq的实例

Question

我具有以下数据结构，并希望它成为typeclass 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必须是作为Eqtypeclass 实例的类型。

因此，您可以使用以下方法实现此目的：

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

请注意，现在它将编译，但是仍然存在问题：如果您检查a Node … … …是否等于a 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 … … …，从它们包装相同的值开始，您将在这里将它们视为两个。因此，您不必关注子树。为了解决此问题，您需要执行递归。我将其保留为练习。