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 SAA27379 for caml-red; Wed, 8 Nov 2000 18:29:43 +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 UAA06254 for ; Tue, 7 Nov 2000 20:49:22 +0100 (MET) Received: from mail.mimuw.edu.pl (pn252.warszawa.cvx.ppp.tpnet.pl [213.76.109.252]) by nez-perce.inria.fr (8.11.1/8.10.0) with ESMTP id eA7Jn2v22934 for ; Tue, 7 Nov 2000 20:49:03 +0100 (MET) Received: (from news@localhost) by mail.mimuw.edu.pl (PLD/8.9.3) id UAA16904 for caml-list@inria.fr; Tue, 7 Nov 2000 20:19:45 +0100 X-Authentication-Warning: qrnik.knm.org.pl: news set sender to qrczak@knm.org.pl (Marcin 'Qrczak' Kowalczyk) using -f From: qrczak@knm.org.pl (Marcin 'Qrczak' Kowalczyk) Subject: Re: practical functional programming Date: 7 Nov 2000 19:19:40 GMT Organization: Klub Nieszkodliwych =?iso-8859-2?Q?Manjak=F3w?= Message-ID: References: <4.3.2.7.2.20001103055229.00ab6880@shell16.ba.best.com> <4.3.2.7.2.20001103055229.00ab6880@shell16.ba.best.com> <4.3.2.7.2.20001106100700.00c447b0@shell16.ba.best.com> Mime-Version: 1.0 Content-Type: text/plain; charset=iso-8859-2 Content-Transfer-Encoding: 8bit X-Trace: qrnik.knm.org.pl 973624780 16792 127.0.0.1 (7 Nov 2000 19:19:40 GMT) X-Complaints-To: news@qrnik.knm.org.pl NNTP-Posting-Date: 7 Nov 2000 19:19:40 GMT User-Agent: slrn/0.9.6.3 (Linux) To: caml-list@inria.fr Sender: weis@pauillac.inria.fr Mon, 06 Nov 2000 10:15:30 -0800, Chris Hecker pisze: > I guess my next question then would be related to efficiency: > isn't there a lot of copying going on if you've got to make a new > instance of your symbol table just to add an element? How does > this work out in practice? It depends on how the symbol table is implemented. With balanced binary trees element search costs log(N) and obtaining an updated mapping costs log(N). Updating must copy the path from the root to the place where the change is being made. With hash tables search costs a constant time but obtaining an updated mapping costs N. There is a tricky idea providing fast arrays with a functional interface. A mutable array is kept under a mutable reference. Obtaining an updated array does the update in place and then replaces the contents of the old reference by a data structure which refers to the new copy and tells which element to replace by which old value. So values from which other versions were derived behave as before, even though their representation changes. Accessing older versions becomes slower and slower as more updates are being made. There is a complex imperative implementation here, especially as we must deal with cases when the updated version is no longer used and there is a chain of updates starting from an older copy. When versions diverge too much, probably it's time to make separate copies. I'm not sure how all details should be done. But once it is done, usage of these arrays is completely functional. > Is there some sort of reference counted sharing going on, or are > there actually two copies of the data in memory if you wrote your > example in caml? Everything not explicitly copied is shared, but OCaml's implementation of the garbage collector does not use reference counting. -- __("< Marcin Kowalczyk * qrczak@knm.org.pl http://qrczak.ids.net.pl/ \__/ ^^ SYGNATURA ZASTĘPCZA QRCZAK