Haskell:标准库假设Eq和Ord是兼容的吗



这是不一致的Eq和Ord实例的后续问题?。

问题本质上是:当为类型声明EqOrd实例时,是否必须确保compare x y返回EQ当且仅当x == y返回True?创建打破这种假设的实例是否危险?这似乎是一个人们可能会假设的自然定律,但它似乎没有在前奏曲中明确说明,不像例如monad或函子定律。

基本的反应是:这样做有点危险,因为图书馆可能会认为这项法律成立。

现在,我的问题是:是否有任何标准库(特别是SetMap)做出了这种假设?只要我只依赖GHC提供的标准库,那么使用EqOrd不兼容的类型是否危险(如果大列表问题仍然可以接受,我会问:哪些常用的库假设了这一定律?)

编辑我的用例与原始问题的用例相似。我有一个带有Eq自定义实例的类型,我经常使用它。我想要Ord的唯一原因是,我可以将其用作Map的域;我不在乎具体的顺序,也永远不会在代码中明确使用它。因此,如果我可以使用Ord的派生实例,那么我的生活会更轻松,代码也会更清晰。

标准前奏中Ord本身的定义要求已经有一个Eq实例:

class  (Eq a) => Ord a  where
    ...

因此,违反同样是错误的

    x == y           =  compare x y == EQ
    x /= y           =  compare x y /= EQ

因为这将违反(根据Ord中这些运算符的默认定义)。

    x <= y           =  compare x y /= GT
    x <  y           =  compare x y == LT
    x >= y           =  compare x y /= LT
    x >  y           =  compare x y == GT

编辑:在库中使用

如果标准库没有使用Ord==/=运算符,我会非常惊讶。专用运算符(==/=<=<>=>)通常比compare更方便,所以我希望在map s或filter s的代码中使用它们。

您可以在AscListWithKey中的Data.Map中看到==用于密钥保护。这个特定函数只调用Eq类,但如果键也是Ord实例,则Ordcompare将用于生成的Map的其他函数,这是假设Eq==Ordcompare相同,并测试EQ

作为一名库程序员,如果任何一个特殊目的操作符在特定目的上优于compare,我不会感到惊讶。毕竟,这就是为什么它们是EqOrd类的一部分,而不是被定义为所有EqOrd实例的多态性。即使compare更方便,我也可能会特意使用它们。如果我这样做了,我可能会定义一些类似的东西:

compareOp :: (Ord a) => Ordering -> Bool -> a -> a -> Bool
compareOp EQ True  = (==)
compareOp EQ False = (/=)
compareOp LT True  = (<)
compareOp LT False = (>=)
compareOp GT True  = (>)
compareOp GT False = (<=)

要扩展Circec的答案,只有当定义的操作是规范的时,才应该创建typeclass实例。如果有一个合理的Eq没有扩展到合理的Ord,那么最好选择另一个Eq,或者不定义Ord。为"其他"等式创建一个非多态函数是很容易的。

这种张力的一个很好的例子是潜在的Monoid实例

instance Monoid Int where
  mzero = 0
  mappend = (+)

与其他"明显"的Monoid实例竞争

instance Monoid Int where
  mzero = 1
  mappend = (*)

在这种情况下,所选择的路径既不实例化,因为不清楚其中一个是否是"规范的"路径。这通常最符合用户的期望,并且可以防止错误。

我已经通读了这个和你最初的问题,所以我将解决你的一般问题。。。。

你想要这个-

Map BigThing OtherType

这个-

(==)::BigThing->BigThing->Bool

其中一种情况必须准确,另一种情况出于性能原因应该忽略它的一些数据。(在第一个问题中需要准确,但在这个问题中,看起来你可能在回答相反的问题。。。。答案相同)。

例如,您希望地图只存储基于某些标签的结果,如

`name::BigThing->String`

但是(==)应该做一个深入的比较。这样做的一种方法是定义不兼容的compare(==)函数。然而

在这种情况下,这是不必要的。为什么不直接使用地图

Map String OtherThing

并做这样的查找-

lookup (name obj) theMap

直接对非常大的文档数据进行索引是非常罕见的。。。。

最新更新