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 RAA22464 for caml-redistribution; Tue, 23 Feb 1999 17:59:14 +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 RAA07520 for ; Tue, 23 Feb 1999 17:49:50 +0100 (MET) Received: from tequila.cs.yale.edu (TEQUILA.CS.YALE.EDU [128.36.229.152]) by nez-perce.inria.fr (8.8.7/8.8.7) with ESMTP id RAA14522 for ; Tue, 23 Feb 1999 17:49:48 +0100 (MET) Received: from tequila.cs.yale.edu (localhost [127.0.0.1]) by tequila.cs.yale.edu (8.8.7/8.8.7) with SMTP id LAA05586 for ; Tue, 23 Feb 1999 11:49:39 -0500 To: caml-list@inria.fr Sender: weis From: Stefan Monnier Newsgroups: lists.caml Subject: Re: polymorphically comparable Maps? References: <14033.38333.652607.941379@heplix4.ikp.physik.tu-darmstadt.de> Date: 23 Feb 1999 11:49:33 -0500 Message-ID: <5lww199iaq.fsf@tequila.cs.yale.edu> X-Newsreader: Gnus v5.5/Emacs 20.3 Path: tequila.cs.yale.edu NNTP-Posting-Host: tequila.cs.yale.edu X-Trace: 23 Feb 1999 11:49:33 -0500, tequila.cs.yale.edu >>>>> "Thorsten" == Thorsten Ohl writes: > library) with the property that identical maps will have an identical > representation? Sorted association lists work, but have linear access > and insertion. Is there something logarithmical (even with an OCaml > implementation)? 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. Of course, equality comparison (although simple thanks to the identical representation) will still be linear, so it doesn't buy you much since equality comparisons of non-balanced binary trees (or pretty much any map of ordered types) can also be done fairly simply in linear time. So why exactly do you want that representation to be `identical' ? Stefan