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 _______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
