Data.Set和自定义Ord实例的结果不一致

Question

这是我的数据结构

data Ex =
  P String
  | (:?) Ex

它有财产p == ??p.我的自定义Eq和Ord实例尝试定义相同的内容.但是,我看到test3(由[p,←←p,←p]创建的集合)和test4(从[p,←p,←←p]创建的集合)的结果不一致.结果如下图所示:

*Test> test3
fromList [?q,??q]
*Test> test4
fromList [q,?q,??q]

请注意,test3和test4仅在创建集合的元素的顺序上有所不同.然而,结果不同.

我认为使用Data.Set.fromList创建集合的顺序并不重要.有人可以帮我找到我的Eq或Ord实例的错误吗？下面的完整代码,使用GHC 8.4.3编译.

module Test where    
import Data.Set as S


data Ex =
  P String
  | (:?) Ex

instance Show Ex where
  show (P s) = s
  show ((:?) e) = "?" ++ (show e)

instance Eq Ex where
  (P s1) == (P s2) = s1 == s2
  (:?) e1 == (:?) e2
    | e1 == e2 = True
    | otherwise = False
  e1 == (:?) e2
    | e1 == e2 = False
    | (:?) e1 == e2 = True
    | otherwise = False
  (:?) e1 == e2
    | e1 == e2 = False
    | e1 == (:?) e2 = True
    | otherwise = False

elength :: Ex   -> Int
elength (P s) = length s
elength ((:?) e) = elength e + 1

instance Ord Ex where
  compare e1 e2
    | e1 == e2 = EQ
    | otherwise = if (elength e1) <= (elength e2) then LT
      else GT

-- Check that ?q == ??q                                                                                               
test2 = S.fromList [(:?) ((:?) (P "q")), P "q"]
-- output should be : {??q, ?q}                                                                                       
test3 = S.fromList [P "q",  (:?) ((:?) (P "q")), (:?) (P "q")]  
-- output should be same as that of test3 : {??q, ?q}                                                                 
test4 = S.fromList [P "q", (:?) (P "q"), (:?) ((:?) (P "q"))]

编辑:

1. 请注意,如果我修改elength定义来处理大小写,则不一致性就会消失.

   elength ((:?) ((:?) e)) = elength e

2. 也许我的elength指标和==定义在q和的情况下是不一致的??q.我仍然想知道他们到底出了什么问题

Answer 1

你的Eq实例对我来说当然很奇怪.我会一次解开两个被取消的配对,而不是零敲碎打:

instance Eq Ex where
  (P s1) == (P s2)     = s1 == s2
  ((:?) e1) == (:?) e2 = e1 == e2
  e1 == (:?) ((:?) e2) = e1 == e2
  (:?) ((:?) e1) == e2 = e1 == e2
  _ == _ = False

也许这相当于你所写的; 这很难分辨,因为你的模式匹配与你的目标不一致.

您的Ord实例也是一个问题,因为您没有定义一致的排序.对于任何一组项目x y z,x < y && y < z应该是这样的情况x < z.但是,根据您的规则,有简单的反例:

x = P "a"
y = (P "b" :?)
z = ((P "a" :?) :?)

在这里x == z,尽管y他们之间为In.

要解决这两个问题的一种方法是写一个simplify函数,删除所有对抵偿构造函数,并使用在这两个Eq和Ord实例.简化每个参数,以便您知道每个参数都有0或1个否定级别.从那里开始,Eq很容易,在你定义之前你需要做的Ord就是确定否定值是否应该小于或大于非否定值.你不能选择它们是平等的,因为这再次打破了传递性.

如果你写了simplify,那么每次触摸其中一个对象时调用简化会浪费大量的工作,因为你立即抛弃了简化.我选择不导出此类型的构造函数,而是提供一个在返回值之前简化的智能构造函数.然后消费者会知道一切都被否定了或根本没有.