[Haskell-cafe] Breaking change to Eq accepted by Core Libraries Committee

[Olaf Klinke]

On Sun, 2021-11-14 at 20:24 +0100, Sven Panne wrote:
> Am So., 14. Nov. 2021 um 20:05 Uhr schrieb Olaf Klinke <
> olf at aatal-apotheke.de>:
> 
> > That module defines two intervals to be equal if their bounds are
> > equal, but to be unequal only if they are disjoint.
> 
> Well, this is simply a broken implementation. Quick question: Is the Ord
> instance lawful or not? Hard to tell... (at least without pencil & paper)
> 

No, it's not. All four relations (>), (>=), (<), (<=) are transitive,
but (>=) and (<=) should be reflexive, which they aren't: 
let i = I 0 1 :: Interval Int in i <= i
= 1 <= 0 
= False
Comparability fails as well, which is why the author did not implement
`compare`: 
j = I 0 2 :: Interval Int
k = I 1 3 :: Interval Int
  (j <= k) || (k <= j)
= (2 <= 1) || (3 <= 0)
= False || False
= False

Antisymmetry is particularly interesting: It holds, but only for
singleton intervals. 

> 
> > In my eyes this speaks for the proposal, because the library author would
> > have been
> > unable to write the broken instance. [...]
> > 
> 
> But this is an extremely weak argument for the proposal: One can easily
> write broken instances even with a single (==) method, e.g. violating
> symmetry etc.  As another example: Given some e.g. Monad instance, can one
> quickly see if it is lawful? I very much doubt so, unless one tries to
> prove it. Laws of type classes are very much "outside of the Haskell
> language", anyway, so I see nothing special for Eq.

Indeed in general one can't tell whether a monad instance is lawful
(Rice's theorem applies), but a least the class methods aren't
trivially redundant. That removes one possible source of non-lawful-
ness. 

Olaf