On Fri, 3 Sep 2010 12:02:22 +1000, Ivan Lazar Miljenovic
What precisely do you mean by natural ordering?
An ordering that has relevant meaning for the information represented by the datatype. Ideally, it should also be alone in being the order anyone would expect this datatype to have (because instances are global). (If there is not a single most obvious ordering, then don't define an instance for Ord – chances are someone will use it with the wrong expectations. We may use newtypes instead.)
A separate type class for types which can be ordered in some (possibly arbitrary) way, for use in Data.Map, would remedy this.
Sure... except that the way Data.Map and Data.Set are implemented is by a binary tree, and you typically want some kind of ordering for those.
Yes, so you would use the (possibly arbitrary) ordering provided by the new class.
How is a type class that represents arbitrary ordering any different from what we already have?
The important thing is that there are *two* classes: one for "natural", semantic orderings, and one for arbitrary orderings. Henning's example of the Gaussian integers is excellent. We would be able to have Sets of gaussians, and still catch mistaken uses of '<' on them. There is a further advantage to this separation. Some types may have a "natural", obvious ordering that is hard to compute, while their representation also allows a fast comparison, that has nothing to do with the semantics of the type (is "arbitrary"). Further, if you change the representation, you can also change to a new arbitrary ordering, which is more efficient in this new situation, without ever touching the semantic ordering, so users of the type need not know.
The notation might not be the best if you consider the ordering to be arbitrary, but what else would you use? "isArbitrarilyBefore :: (ArbitraryOrdering a) => a -> a -> Bool" ?
Yes, something like that. If you use it a lot, say in the implementation of Data.Set, you can make a nice local operator alias (say, ≼ or ⊑). Regards, Arie