Left-bias and non-structural equality.

[Adrian Hey]

On Wednesday 04 Jan 2006 3:36 pm, Jean-Philippe Bernardy wrote:
> On 1/4/06, Adrian Hey <ahey at iee.org> wrote:
> > 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.

Well I wouldn't use the term biasing at all for association
values in Maps. The choice is clearly semantically significant and
I guess both options should provided by the new Map API.

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

Yes, though I wonder how many people actually rely on this being correct?
Not many I suspect, since the implementations themselves were incorrect
in several cases :-)

I still think specifying this at all was a mistake and we should
deprecate all these functions. Unfortunately they use a lot of good
names, so maybe the entire API should be deprecated and put in
separate module (Data.OldSet or something).

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

Yes, in the short term where we're only providing one polymorphic
Set type. But I think the longer term goal is to provide some
kind of type constructor class that allowed multiple possible
implementations of polymorphic sets (and multiple specialised
monomorphic implementations too). So we shouldn't assume the
underlying data structure is always going to be AVL trees.

Regards
--
Adrian Hey