Generic tries (long)

Adrian Hey ahey at
Tue Jun 17 04:35:10 EDT 2008

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).

Adrian Hey

More information about the Libraries mailing list