Hi,
On 1/4/06, 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:-)
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.