Re: Left-bias and non-structural equality.

On Wednesday 04 Jan 2006 3:36 pm, Jean-Philippe Bernardy wrote:

On 1/4/06, Adrian Hey 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