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