[Haskell-cafe] Unnecessarily strict implementations

[Arie Peterson]

On Fri, 3 Sep 2010 12:02:22 +1000, Ivan Lazar Miljenovic
<ivan.miljenovic at gmail.com> wrote:
> 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