Haskell：标准库假定Eq和Ord是兼容的吗？ [英] Haskell: do standard libraries assume Eq and Ord are compatible?

问题描述

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

这个问题实质上是：当声明 Eq 和 Ord 必须确保比较xy 返回 EQ 当且仅当 x == y 返回 True ？创建破坏这个假设的实例是危险的吗？这似乎是一个人们可以假设的自然法则，但似乎并没有在前奏中明确说明，基本的回答是：这样做有点危险，因为图书馆可能会认为这个定律是成立的。

$ b

$ b

现在我的问题是：执行任何标准库（特别是 Set 或 Map ）做出这个假设？使用不兼容的类型 Eq 和 Ord 是危险的，只要我只依赖标准库是否提供GHC？（如果大问题仍然可以接受，我会问：哪些常用图书馆采用此法律？）

编辑。我的用例与原始问题类似。我有一个使用 Eq 的自定义实例的类型，我使用了很多。我想要 Ord 的唯一原因是我可以将它用作 Map 的域;我不关心具体的顺序，也不会在代码中明确地使用它。因此，如果我可以使用 Ord 的派生实例，那么我的生活会更容易，我的代码更清晰。

解决方案

在 Ord 本身.html> standard prelude 要求已经存在 Eq 实例：

  class（Eq a）=> Ord a其中
 ... 
  

所以违反 p>

  x == y =比较xy == EQ 
x / = y =比较xy / = EQ 
  

因为它会违反Ord中这些运算符的默认定义。

  x <= y =比较xy / = GT 
x< y =比较x y == LT 
 x> = y =比较x y / = LT 
 x> y =比较xy == GT 
  

编辑：在库中使用

如果标准库没有使用 Ord 的 = = 和 / = 运算符。特定目的操作符（ == ， / = ， <= ，< ，> = ，> ）通常比 compare 更方便，所以我期望看到它们在代码中用于 map s或过滤器 s。

您可以将< == 用于<来自fromAscListWithKey的code> Data.Map 。这个特定的函数只会调用 Eq 类，但是如果这个键也是一个 Ord 实例，那么 Ord 的 compare 将用于结果 Map的其他函数 ，这是假定 Eq 的 == 与 Ord code>的比较并测试 EQ 。





作为一个库程序员，如果任何特殊用途运算符为特定目的胜过 compare ，我不会感到惊讶。毕竟，这就是为什么它们是 Eq 和 Ord 类的一部分，而不是被定义为所有<$的多态c $ c> Eq 或 Ord 实例。即使 compare 比较方便，我也可以使用它们。如果我这样做，我可能会定义类似于：

  compareOp ::（Ord a）=>订购 - >布尔 - > a  - > a  - > Bool 
 compareOp EQ True =（==）
 compareOp EQ False =（/ =）
 compareOp LT True =（<）
 compareOp LT False =（> =） 
 compareOp GT True =（>）
 compareOp GT False =（<=）
  

This is a followup question to Inconsistent Eq and Ord instances?.

The question there is essentially: when declaring Eq and Ord instances for a type, must one ensure that compare x y returns EQ if and only if x == y returns True? Is it dangerous to create instances that break this assumption? It seems like a natural law one might assume, but it doesn’t appear to be explicitly stated in the Prelude, unlike e.g. the monad or functor laws.

The basic response was: it is a bit dangerous to do this, since libraries may assume that this law holds.

My question, now, is: do any of the standard libraries (in particular, Set or Map) make this assumption? Is it dangerous to have a type with incompatible Eq and Ord, so long as I am only relying on the standard libraries supplied with GHC? (If big-list questions were still acceptable, I would be asking: which commonly used libraries assume this law?)

Edit. My use-case is similar to that of the original question. I have a type with a custom instance of Eq, that I use quite a bit. The only reason I want Ord is so that I can use it as the domain of a Map; I don’t care about the specific order, and will never use it explicitly in code. So if I can use the derived instance of Ord, then my life will be easier and my code clearer.

解决方案

The definition of Ord itself in the standard prelude requires there already be an Eq instance:

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

So it would be just as wrong to violate

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

As it would be to violate (from the default definitions for these operators in 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

Edit: Use in libraries

I would be quite surprised if standard libraries didn't make use of Ord's == and /= operators. The specific purpose operators (==, /=, <=, <, >=, >) are frequently more convenient than compare, so I'd expect to see them used in code for maps or filters.

You can see == being used in guards on keys in Data.Map in fromAscListWithKey. This specific function only calls out for the Eq class, but if the key is also an Ord instance, Ord's compare will be used for other functions of the resulting Map, which is an assumption that Eq's == is the same as Ord's compare and testing for EQ.

As a library programmer, I wouldn't be surprised if any of the special purpose operators outperformed compare for the specific purpose. After all, that's why they are part of the Eq and Ord classes instead of being defined as polymorphic for all Eq or Ord instances. I might make a point of using them even when compare is more convenient. If I did, I'd probably define something like:

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 = (<=)

这篇关于Haskell：标准库假定Eq和Ord是兼容的吗？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！