[Haskell] Data.Map and Data.Set
maeder at tzi.de
Thu Oct 20 09:16:34 EDT 2005
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
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.)
More information about the Libraries