[Haskell-cafe] strange stack overflow with Data.Map

[Adrian Hey]

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