[Haskell] Data.Map and Data.Set

[Christian Maeder]

Malcolm Wallace wrote:
> I checked in a Read instance for Data.Set a few weeks ago, when I
> needed one.  An addition like this is rather obvious, so I doubt it
> needs any discussion.  For other changes (like Set.intersection),
> some discussion might be desirable, but the best proposal is an
> implemented one, which others can then improve.

A major problem is to keep Set, Map, IntSet and IntMap in sync, 
particularly when the interface will change.

(In the original DData there used to be Bag, IntBag, Seq and Queue 
modules that have been considered less important for inclusion under 
base/Data. The current Data.Queue is not the one from Daan and doesn't 
follow the naming convention of Data.Set and Data.Map)

Before checking in any non-trivial changes the specified properties 
should be checked using quickcheck. Adding Read instances won't violate 
any invariances, but why not also add a property for it?

It would also be great, if we had a performance test-suite to better 
judge what changes to commit. At least Daan Leijen and Jean-Philippe 
Bernardy and probably many others, too, made performance tests (and it 
would be handy, if these could be simply rerun, before and after a change).

My code proposal for Set.intersection can be found in
http://www.haskell.org//pipermail/glasgow-haskell-users/2005-September/009014.html

But I've neither thoroughly tested correctness nor performance nor 
supplied a quickcheck property "left_biased_intersection", I think, this 
is a desirable property (others might even disagree), but personally I 
don't really depend on it and have no time to work much more on it.

I'm also pretty sure that "Set a" won't behave like "Map a ()" or an 
identity map "Map a a", if "Ord a" is not really total (and at least for 
Sets such orders are expected and the effect is partly documented.)

Christian