On Tue, 20 Mar 2007, Duncan Coutts
Actually it's fine. The library report states that:
When the "By" function replaces an Eq context by a binary predicate, the predicate is assumed to define an equivalence; when the "By" function replaces an Ord context by a binary predicate, the predicate is assumed to define a total ordering.
So we can assume they're ok for the specification of those List module functions but as you say, beyond that we can't make any hard assumptions.
Well, the report says (about the Prelude, but I think the same applies to the libraries): "It constitutes a specification for the Prelude. Many of the definitions are written with clarity rather than efficiency in mind, and it is not required that the specification be implemented as shown here." I interpret this as "you can change (optimise) the definitions, but the user shouldn't be able to observe the difference (except by measuring resource usage)". What else could "specification" mean?
In other words we can assume Ord is a total order (for non-_|_ values) for the purposes of defining sort [...]
I'd say you still need to define a function observationally equivalent to the one given in the report. -- /NAD