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 TAA06713 for caml-redistribution@pauillac.inria.fr; Tue, 11 Apr 2000 19:53:06 +0200 (MET DST) Resent-Message-Id: <200004111753.TAA06713@pauillac.inria.fr> 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 CAA08710 for ; Tue, 11 Apr 2000 02:24:01 +0200 (MET DST) Received: from motgate2.mot.com (motgate2.mot.com [136.182.1.10]) by nez-perce.inria.fr (8.8.7/8.8.7) with ESMTP id CAA01947 for ; Tue, 11 Apr 2000 02:24:00 +0200 (MET DST) Received: [from pobox2.mot.com (pobox2.mot.com [136.182.15.8]) by motgate2.mot.com (motgate2 2.1) with ESMTP id RAA22837; Mon, 10 Apr 2000 17:23:56 -0700 (MST)] Received: [from fraser.asc.corp.mot.com (fraser.asc.corp.mot.com [217.1.104.8]) by pobox2.mot.com (MOT-pobox2 2.0) with ESMTP id RAA12242; Mon, 10 Apr 2000 17:23:53 -0700 (MST)] Received: from motorola.com (jaguar [217.1.104.76]) by fraser.asc.corp.mot.com (8.8.7/8.8.7) with ESMTP id JAA21682; Tue, 11 Apr 2000 09:53:49 +0930 (CST) Sender: dchen@asc.corp.mot.com Message-ID: <38F270CF.221F5BD0@motorola.com> Date: Tue, 11 Apr 2000 09:54:47 +0930 From: "Dennis (Gang) Chen" Organization: Motorola Australia Software Centre X-Mailer: Mozilla 4.5 [en] (X11; I; SunOS 5.5.1 sun4u) X-Accept-Language: en MIME-Version: 1.0 To: Jean-Christophe Filliatre CC: "caml-list@inria.fr" Subject: Re: When functional languages can be accepted by industry? References: <38E7F364.5D24BB7C@motorola.com> <14572.49274.910966.673172@cylinder.csl.sri.com> <38ED71B6.30118608@motorola.com> <14574.1721.508470.790475@cylinder.csl.sri.com> Content-Type: text/plain; charset=us-ascii Content-Transfer-Encoding: 7bit Resent-From: weis@pauillac.inria.fr Resent-Date: Tue, 11 Apr 2000 19:53:06 +0200 Resent-To: caml-redistribution@pauillac.inria.fr Jean-Christophe Filliatre wrote: > > I have not found a method to implement a set with an efficient > > element removal operation. To my knowledge, the implementation of > > set based on balanced tree is efficient for union, difference etc, > > but does not seem to be reasonably efficient for deleting an > > element. Besides, the tree-based implementation of set requires that > > the elements have an ordered type, it is not clear to me how to > > extend these techniques to build a set of unordered elements, say, > > set of sets. > > Ocaml sets come with a comparison function, so that you can build sets > of sets. See http://caml.inria.fr/ocaml/htmlman/manual053.html. > > If you can manage with sets of integers, you could consider Patricia > trees instead of balanced trees, as suggested in that article > http://www.cs.columbia.edu/~cdo/papers.html#ml98maps > > As I already wrote, Okasaki's book is marvelous, and gives many > different implementations of efficient datastructures, together with > tools to analyze theire complexity. Thanks for the suggestion, it sounds to be interesting to consider the ocaml comparison function on sets to build sets of sets. For the deletion operation, I've contacted Okasaki, who has also proposed balanced tree and Patricia tree, as well as the above paper and the following one: http://www-swiss.ai.mit.edu/~adams/BB/index.html The deletion operation described in these papers will rebuild a tree. Therefore, it does not seem to be comparably efficient with those implementations in imperative languages. Best regards. Gang Chen