[trac@galois.com: Re: [GHC] #1218: Add sortNub and sortNubBy to Data.List]

[Neil Mitchell]

Hi

> Does it? I was under the impression that a compiler can never assume
> that any laws hold of any user-defined instances (to do optimisations,
> for instance).

That was my impression.

> > So one could say that we can't really rely on any laws that should go
> > along with type class instances, but that's clearly not right since then
> > we cannot sort!
>
> Libraries can of course depend on various laws (hopefully this
> dependence is explicit in the documentation). I guess you can argue
> whether rewrite rules are part of the compiler or the library. To me a
> rewrite rule is fishy unless the two sides are observationally
> equivalent, though.

Taking an example, if your Ord instance is not transitive then
Data.Map may loop infinitely. Tracking this down was not particularly
fun...

I'd guess that if there is an Ord and an Eq instance, they should be
in agreement, but until the compiler can prove it, I'd be wary of
exploiting it.

Thanks

Neil