Left-bias and non-structural equality.

[Christian Maeder]

Adrian Hey wrote:
> So I vote we drop the left/right biasing distinction. This way lies
> madness (as they say:-)

I would not like to drop biasing distinction, as I don't think this 
costs too much. With biasing, maps could be implemented via "biased 
sets" (Set (MapEntry a b)):

data MapEntry a b = a := b

instance Eq/Ord a => Eq/Ord (MapEntry a b) where
     compare (a1 := _) (a2 := _) = compare a1 a2

> If there's some good reason why we should care then the corresponding
> type should not be an instance of Ord. So what should be done in cases
> like this? It's tempting to think we should add HOF versions like
> this..
> 
> insertUsing :: (a -> a -> COrdering a) -> a -> Set a -> Set a

It may also be possible to pass an order to "empty" and use it further 
on. The major problem is if varying orders are used ie. for "union".

By good, bad or earlier design Data.Set/Map relies on Ord instances and 
I'm quite content with it.

Cheers Christian