Hello All, Folks, could you please check this out and comment on the proposed class API(s), in particular if there's anything that's really bugged you about Data.Map/Set etc now is your chance to get a (hopefully) decent performing lib with your personal wishlist items included. Jamie, I'm sure it would help a lot if you could produce (and update if necessary) documented API proposal using Haddock. The email is rather difficult to follow IMHO (at least with my email client)
Guarantees about ordering will probably vary between maps.
I take it you mean different concrete implementations. For classes I think it's important to be clear exactly what is being promised wrt ordering, and that promise must be kept by *all* instances. A "class law" that applies to some instances and not others is no use at all really (we'll end up with kind of mess and confusion we seem to have for the Ord/Eq classes at present :-) As having an explicit Ord constraint is objectionable to some folk and there might indeed be efficient implementations that don't offer any ordering guarantees, it may be good to break that API into an unordered Map class and have a separate subclass for methods that are supposed to deliver on ordering promises. Regarding ordering promises, what do folk think they should be? I think ideally we would want the same Ordering as the corresponding Ord instance (if it exists), but this is hard to guarantee as typically we won't have any control over the Ord instance definition (and won't be using the compare method). Would it be OK to simply to promise that the Ordering is the same as that that would be wholly derived? In which case we wouldn't want the Ord constraint, but we probably would want our own private compare method (which generally won't agree with Ords compare). If we want ordering that's guaranteed to be consistent with Ord (and have a meaningful Ord constraint), I can think of two ways to do this: 1- Have users write the matching instance by hand (a huge amount of work if we're talking about a generalised trie). 2- Fall back on balanced tree implementation and actually use Ords compare method (slow). Regards -- Adrian Hey