声明Eq(树a)的实例,如果它们具有相同的元素,则两个树相等

Question

我正在尝试在Haskell中为我的树数据类型创建一个Eq(树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)

我不知道为什么拒绝编译.我使用了一种方法,从列表中生成一个树并展平该树返回原始列表,所以我知道flatten工作正常.我假设它抱怨不知道列表的内容是Ord还是Eq,但我不知道如何解决这个问题.添加

 (Ord a, Eq a) => 

扁平的签名没有做到.

Answer 1

这个问题是不是有flatten:flatten不需要元素可订购,它只是生产要素的列表.

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

元素的类型也需要是Eq类型类的成员,因为您随后调用(==)列表.但是,自从Ord暗示Eq,这不是一个真正的问题.

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

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

所以在这里我们只能检查两棵树是否相等,因为树包含类型为元Ord类的实例的元素.