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

[Adrian Hey]

Luke Palmer wrote:
> It could be.  I actually don't know what Haskell specifies here.  If a
> type has an Eq instance and x == y, must x and y be observationally
> equivalent?

I would say yes, without exception, at least as far as the public
(exported) interface is concerned.

>  Or is it reasonable to allow some wiggle room?

Well for abstract data types observational equivalence doesn't
necessarily imply structural identity. An obvious example is the AVL
tree lib, where trees with different shapes (and hence different
heights possibly) are treated as being equal if they contain the same
elements in the same order. But the solution here is not to export
functions that can discriminate between "equal" trees (such as height).

>  I'd say
> (==) definitely has to be an equivalence relation, but beyond that,
> it's open to the implementor, since if an algorithm only depends on
> (Eq a), it can't tell the difference between observational equality
> and any other equivalence relation.

I'm not sure what you're saying. Consider the max method, the Ord
class definition doesn't specify which of two "equal" values should be
returned. So, it must be generally assumed that it doesn't matter.

You could treat the default method implementation as the specification,
but the problem with this is as general rule that it still leaves us no
specification for methods with no defaults.

> There is nonetheless a need to handle duplicates gracefully, that is
> keeping a count won't cut it, because of sortBy.

For the overloaded sort, I would say keep a count of duplicates is
a perfectly reasonable and correct solution (and more space efficient
too).  For sortBy things need specifying more precisely as it can accept
any old function which happens to have the right type.

Regards
--
Adrian Hey