Left-bias and non-structural equality.

[Adrian Hey]

Hello,

On Monday 02 Jan 2006 11:43 pm, Adrian Hey wrote:
> Anyway, the problem is we have one hole and two "equal" things, only
> one of which can fit in the hole. Is there any reason why we can't
> simply adopt the position that which one is chosen is unspecified and
> the choice is entirely at the implementors discretion?

Well we've had 24 hours of silence on this issue, so I assume this
indicates that there is no reason we can't adopt the above position :-)
So I vote we drop the left/right biasing distinction. This way lies
madness (as they say:-)

Instead we demand that instances of Eq and Ord are semantically
sane, as should be stated in the Haskell language definition,
(but isn't AFAIK for some reason).

So for all instances of Ord, the semantics regarding which of two (or
more) "equal" values is used should always be "Who knows? Who cares?".

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

But as others have pointed out, this is probably the wrong thing
to do as Sets should provide some kind of semantic guarantees
(not sure what :-) which may be broken if we allow arbitrary
"combining comparisons" to be used.

I think the right thing to do is to expose a non-overloaded API
for the underlying data structure implementation, but don't
call it a "Set" or "Map" or whatever. Call it exactly what it
is "AVL tree" or "Adams tree" or "trie" (or whatever).

If we don't expose this API, this leaves users no alternative but
to define *broken* instances of Ord (and maybe Eq too) if they
want to make use of the data structure, and then leaves them
scrutinising source code trying to figure out if biasing
is the way they need it (and if not, what the heck they can
do about it?). This is Bad Thing I think.

Regards
--
Adrian Hey