haskell - 声明 Eq (Tree a) 的实例，其中如果两棵树具有相同的元素，则它们相等

Question

我正在尝试为 Haskell 中的树数据类型创建 Eq (Tree a) 实例，以便两棵树在具有相同元素时相等。所以我有一种方法可以将我的树变成一个列表(展平)，然后比较排序后的列表。 但是我收到错误，例如当我对列表进行排序时没有 (Ord a) 的实例，或者当我 == 我的两个列表时没有 (Eq a) 的实例。

import Data.List as L    
data Tree a = EmptyTree | Node (Tree a) a (Tree a)

instance Eq (Tree a) where     
 (==) t1 t2 = L.sort(flatten t1) == L.sort(flatten t2)

flatten :: Tree a -> [a]    
flatten EmptyTree = []    
faltten (Node x1 y x2) = [y] ++ (flatten x1) ++ (flatten x2)

我不知道为什么这拒绝编译。我使用了一种方法，可以从列表中创建一棵树，然后压平该树返回原始列表，所以我知道压平工作正常。我假设它提示不知道列表的内容是 Ord 还是 Eq，但我不知道如何解决这个问题。添加

 (Ord a, Eq a) => 

扁平签名没有做到这一点。

Answer 1

问题不在于 flatten:flatten 不需要元素可排序，它只是生成一个元素列表。

问题是您使用 sort :: Ord a => [a] -> [a]在 (==) 的实现中，sort 因此需要列表中的元素属于 Ord 实例的类型> 类型类。

元素的类型也需要是 Eq 类型类的成员，因为您随后可以在列表上调用 (==)。但由于 Ord 隐含 Eq，因此这并不是真正的问题。

因此，我们需要将这些类型约束添加到 instance 声明中:

instance <b>Ord a =></b> Eq (Tree a) where     
 (==) t1 t2 = L.sort(flatten t1) == L.sort(flatten t2)

因此，这里我们只能检查两棵树是否相等，前提是两棵树包含 Ord 类型类实例的类型的元素。