[Haskell-cafe] Any precedent or plan for guaranteed-safe Eq and Ord instances?

[Tom Ellis]

On Wed, Oct 02, 2013 at 11:24:39AM +0200, Heinrich Apfelmus wrote:
> I'm not sure whether the  Eq  instance you mention is actually
> incorrect. I had always understood that  Eq  denotes an equivalence
> relation, not necessarily equality on the constructor level.

There's a difference between implementors being able to distingush equals,
and application programmers.  Internal implementations are allowed to break
all sorts of invariants, but, by definition, APIs shouldn't.

Are there examples where application programmers would like there so be some
f, a and b such that a == b but f a /= f b (efficiency concerns aside)?  I
can't think of any obvious ones.

> One prominent example would be equality of Data.Map itself: two maps
> are "equal" if they contain the same key-value pairs,
> 
>     map1 == map2  <=>  toAscList map1 == toAscList map2
> 
> but that doesn't mean that their internal representation -- the
> balanced tree -- is the same. Virtually all exported operations in
> Data.Map preserve this equivalence, but the library is, in
> principle, still able to distinguish "equal" maps.

I had a quick skim of 

    http://www.haskell.org/ghc/docs/latest/html/libraries/containers/Data-Map-Lazy.html

to find such examples, and the only one that jumped out was "showTree".  Are
there others?

Still, although the library is, in principle, able to distinguish "equal"
maps, isn't this just a leaking implementation detail?  Is it somehow of
benefit to API users?

Tom