Re: polymorphically comparable Maps?

[Thorsten Ohl <ohl@hep.tu-darmstadt.de>]

Stefan Monnier <monnier+lists/caml/news/@tequila.cs.yale.edu> writes:

> I can't think of any obvious good answer, but if you can live with
> explicit `canonicalization' (linear time) steps in order to then get
> logarithmical access and identical representation, then some kind of
> binary tree can do the job.

Insertion is also important.  Before I fell back to sorted lists, I
tried canonicalization at every insertion and it killed performance.

Since I can live with a small probability for failing matches in early
phases (they will only hurt performance, but never correctness), I
might attempt a staged approach with delayed canonicalization.

> So why exactly do you want that representation to be `identical' ?

I represent elements of freely generated abelian groups as maps from
the generators to their multiplicity in the element.  These abelian
groups appear in recursive data structures (e.g. to represent
algebraic expressions).  Therefore the easiest approach uses the
polymorphic comparison function in the maps.

I might eventually replace the polymorphic comparison by specific
comparison functions stored with the maps or in closures, but this
doesn't help me because deciding whether two trees represent the same
map is at least linear (but with a smaller N, there might be some
gain).  Actually, none of the available Bignum packages for O'Caml
supports polymorphic comparison.  Therefore I might have to make that
change soon.

BTW: how many unreleased symbolic math packages have been witten in
O'Caml?  I can't possibly be the first to discover how neatly one can
build rings from groups, algebras from modules, etc. using O'Caml's
module system ...  One of thy creators might explain why my
representation is a dumb idea!

Cheers,
-Thorsten
-- 
Thorsten Ohl, Physics Department, TU Darmstadt -- ohl@hep.tu-darmstadt.de
http://heplix.ikp.physik.tu-darmstadt.de/~ohl/ [<=== PGP public key here]