[Haskell-cafe] Re: (flawed?) benchmark : sort

[Adrian Hey]

Neil Mitchell wrote:
> Hi
> 
>>  We're talking about *semantic correctness*, not efficiency. If you
>>  want to fine tune your code like this you shouldn't be relying
>>  on overloaded general purpose function implementations. E.G. the
>>  COrdering type used by AVL lib is one way to do this. This lets
>>  a combining comparison chose which of two "equal" values is used
>>  (and other things).
> 
> I would have thought:
> 
> sort x == sortBy compare x
> 
> was a reasonable property to have.

Certainly, but this is part of (but not the complete) specification
for sortBy, not sort. But given sane Ord/Eq instances and sortBy
implementation, then this is indeed also one of many possible
correct implementatations of sort.

> But you are proposing that sort
> should make assumptions on the compare function,

Not just sort, but any function with an Ord constraint is entited
to assume sane behavior wrt to compare. Without this the Ord class
just becomes quite useless, other than saving a few keystrokes for
folk who be bothered to pass any old compare function as explicit arg.
Surely type classes are supposed to be more than that?

> which you can't even state in Haskell,

There are plenty of formal statements about things that can't be
written in Haskell. That doesn't mean they aren't true or should not
be respected or relied upon. It just means Haskell is an imperfect
language for expressing such things.

> but sortBy should not.

sortBy should not "assume" anything about the function of type
x -> x -> Ordering. Rather, what sortBy actually does with that
function should be specified.

> I also know of a data type:
> 
> data Set xs = Set [xs]
> 
> where the Set constructor is all nicely hidden. If I define Set "ab"
> to be equal to Set "ba", should the compiler burst into flames?

??

  If we
> _require_ all Eq definitions to follow our very narrowly defined
> notion of equality, then the question comes up why we permit people to
> write Eq at all - why doesn't the compiler just do it for us, if there
> is only one right answer.

You provided one example yourself..

data Foo = Foo Int (Int -> Int)

It's perfectly possible for Foo to be an abstract type exported from
a module that preserves the invariant that the same function is always
associated with a given Int (value).

If this is the case there's no reason why Foo should not be an instance
of Ord or Eq.

If this isn't the case then Foo should certainly not be an instance or 
either class IMO.

If this was intended to be the case but in fact isn't the case, then
that's a bug.

Regards
--
Adrian Hey