CODEWITHSUNDEEP
haskelltypeclass
PLL
PLL

Reputation: 1631

Haskell: do standard libraries assume Eq and Ord are compatible?

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.

Upvotes: 7

Views: 1658

Answers (3)

jamshidh
jamshidh

Reputation: 12070

I've read through this and your original question, so I will address your general problem....

You want this-

Map BigThing OtherType

and this-

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

One of these cases has to be exact, the other case should ignore some of its data, for performance reasons. (it was (==) that needed to be exact in the first question, but it looks like you might be addressing the reverse in this question.... Same answer either way).

For instance, you want the map to only store the result based on some label, like a 

`name::BigThing->String`

but (==) should do a deep compare. One way to do this would be to define incompatible compare and (==) functions. However....

in this case, this is unnecessary. Why not just instead use the map

Map String OtherThing

and do a lookup like this-

lookup (name obj) theMap

It is pretty rare to index directly on very large document data....

Upvotes: 1

Cirdec
Cirdec

Reputation: 24166

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

Upvotes: 7

J. Abrahamson
J. Abrahamson

Reputation: 74364

To extend Cirdec's answer, typeclass instances should only be made if the operation being defined is somehow canonical. If there is a reasonable Eq which doesn't extend to a reasonable Ord, then it's best practice to pick either the other Eq or to not define an Ord. It's easy enough to create a non-polymorphic function for the "other" equality.

A great example of this tension is the potential Monoid instance

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

which contests with the other "obvious" Monoid instance

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

In this case the chosen path was to instantiate neither because it's not clear that one is "canonical" over the other. This typically conforms best to a user's expectation and which prevent bugs.

Upvotes: 4

Related Questions