**Next message:**Xavier Leroy: "Re: bug in floating point implementation ?"**Previous message:**Shyjan Mahamud: "bug in floating point implementation ?"**Messages sorted by:**[ date ] [ thread ] [ subject ] [ author ]

From: Thorsten Ohl <ohl@hep.tu-darmstadt.de>

Date: Tue, 23 Feb 1999 19:10:03 +0100 (CET)

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

Subject: Re: polymorphically comparable Maps?

In-Reply-To: <5lww199iaq.fsf@tequila.cs.yale.edu>

<5lww199iaq.fsf@tequila.cs.yale.edu>

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]

**Next message:**Xavier Leroy: "Re: bug in floating point implementation ?"**Previous message:**Shyjan Mahamud: "bug in floating point implementation ?"**Messages sorted by:**[ date ] [ thread ] [ subject ] [ author ]

*
This archive was generated by hypermail 2b29
: Sun Jan 02 2000 - 11:58:20 MET
*