From mboxrd@z Thu Jan 1 00:00:00 1970 Received: (from weis@localhost) by pauillac.inria.fr (8.7.6/8.7.3) id KAA20851 for caml-redistribution; Thu, 25 Feb 1999 10:10:12 +0100 (MET) Received: from nez-perce.inria.fr (nez-perce.inria.fr [192.93.2.78]) by pauillac.inria.fr (8.7.6/8.7.3) with ESMTP id TAA00432 for ; Tue, 23 Feb 1999 19:10:12 +0100 (MET) Received: from heplix4.ikp.physik.tu-darmstadt.de (heplix4.ikp.physik.tu-darmstadt.de [130.83.24.139]) by nez-perce.inria.fr (8.8.7/8.8.7) with ESMTP id TAA16277 for ; Tue, 23 Feb 1999 19:10:11 +0100 (MET) Received: (from ohl@localhost) by heplix4.ikp.physik.tu-darmstadt.de (8.8.8/8.8.8) id TAA16229; Tue, 23 Feb 1999 19:10:03 +0100 From: Thorsten Ohl Message-ID: <14034.61179.248680.469064@heplix4.ikp.physik.tu-darmstadt.de> Date: Tue, 23 Feb 1999 19:10:03 +0100 (CET) To: Stefan Monnier Cc: caml-list@inria.fr Subject: Re: polymorphically comparable Maps? Newsgroups: lists.caml In-Reply-To: <5lww199iaq.fsf@tequila.cs.yale.edu> References: <14033.38333.652607.941379@heplix4.ikp.physik.tu-darmstadt.de> <5lww199iaq.fsf@tequila.cs.yale.edu> X-Mailer: VM 6.61 under Emacs 19.34.1 Reply-To: ohl@hep.tu-darmstadt.de Sender: weis Stefan Monnier 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]