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"))]

编辑：

请注意，如果我修改 elength 定义来处理这种情况，那么不一致就会消失。

elength ((:←) ((:←) e)) = elength e
也许我的 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 在他们之间。

解决这两个问题的一种方法是编写一个 simplify 函数，删除所有对消构造函数对，并在 Eq 和 Ord 实例中使用它。简化每个论点，以便您知道它们每个都有 0 或 1 个否定级别。从那里开始，Eq 很容易，在定义 Ord 之前，您需要做的就是决定取反值应该小于还是大于非取反值。您不能选择让它们相等，因为这又会破坏传递性。

如果你写 simplify，每次你接触其中一个对象时调用 simplify 将会浪费很多工作，因为你会立即丢弃简化。我选择不导出此类型的构造函数，而是提供一个在返回值之前进行简化的智能构造函数。然后消费者就会知道一切都被否定一次或根本没有。

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

Inconsistent results for Data.Set and custom Ord instance

haskell

typeclass