On Friday 30 Dec 2005 10:33 am, Christian Maeder wrote:
I would not impose an implicit requirement for strong structural equality/order on the keys. But it would suffice to document which of two "equal" keys is dropped or kept. Maybe it is even possible to keep "Set a" somehow in sync with "Map a ()" or an identity "Map a a". (And "Set (MapEntryPair a b)" to "Map a b")
On the other hand, if we would forget about biasing also for sets than insertion could be optimized to do nothing with sets that contain already the element. (Maybe that should even be changed so in Data.Set for efficiency reasons. An extra function might do the job of actually replacing an equal element.)
I think it's going to be very difficult to properly address all these issues without creating a huge API with many different flavours of essentially the same functions. I agonised over considerations like this for Data.Tree.AVL. Eventually decided it was a hopeless task and deleted all abstracted Map/Set related functions and instead concentrated on providing just a raw API for AVL trees (only) that gave users the freedom to make their own decisions about this kind of thing (primarily by requiring them to supply the appropriate "combining comparison" as an argument). Even so, the AVL API so still somewhat big for a single data structure library (but I don't think there's much redundancy there). Whilst this made life somewhat simpler for me, it still leaves the question of what an API that is simple, abstracted and time/space efficient should look like. Perhaps these are contradictory goals and it's just not possible to produce such thing. We'll have to see what Jean-Philippe and anybody else who wants to contribute come up with. So best of luck :-) As for the structural equality issue, I have always assumed that if (==) returned True or `compare` returned EQ this implied structural equality. But I'm not sure that's documented anywhere, and as it happens it's not true for the Eq and Ord instances defined AVL trees. This is something that had been worrying me (maybe I should remove these instances). Regards -- Adrian Hey