Left-bias and non-structural equality.

[Jean-Philippe Bernardy]

Hi,

On 1/4/06, Adrian Hey <ahey at iee.org> wrote:
> 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:-)

Ok for sets; but biasing is still a sound notion for maps, as we
discussed previously.

> 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?".

Agreed. Still, I have fixed the Current Data.Map and Data.Set so they
match what the documentation says.

> 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.

We can have high-level types/API for maps and sets that rely on a
sound Ord instance and in return guarantees validity of the structure;
and a low level api for AVL trees that allows everything.

Additionally, we should provide "toAVLTree / unsafeFromAVLTree" to
convert between low and high level types. This allows the best of both
worlds; safety by default, and high-performance/flexibility if the
user wishes.

Cheers,
JP.