From mboxrd@z Thu Jan 1 00:00:00 1970 Received: (from majordomo@localhost) by pauillac.inria.fr (8.7.6/8.7.3) id SAA18979; Mon, 6 Oct 2003 18:56:08 +0200 (MET DST) X-Authentication-Warning: pauillac.inria.fr: majordomo set sender to owner-caml-list@pauillac.inria.fr using -f 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 SAA26615 for ; Mon, 6 Oct 2003 18:56:06 +0200 (MET DST) Received: from fichte.ai.univie.ac.at (fichte.ai.univie.ac.at [131.130.174.156]) by nez-perce.inria.fr (8.11.1/8.11.1) with ESMTP id h96Gu3101265 for ; Mon, 6 Oct 2003 18:56:05 +0200 (MET DST) Received: from fichte.ai.univie.ac.at (markus@localhost [127.0.0.1]) by fichte.ai.univie.ac.at (8.12.3/8.12.3/Debian-6.4) with ESMTP id h96Gu1qF012224; Mon, 6 Oct 2003 18:56:01 +0200 Received: (from markus@localhost) by fichte.ai.univie.ac.at (8.12.3/8.12.3/Debian-6.4) id h96Gu00o012223; Mon, 6 Oct 2003 18:56:00 +0200 Date: Mon, 6 Oct 2003 18:56:00 +0200 From: Markus Mottl To: Michal Moskal , Richard Jones , Claudio Sacerdoti Coen Cc: ocaml-lib-devel@lists.sourceforge.net, caml-list@inria.fr Subject: [Caml-list] Re: [Ocaml-lib-devel] pMap.ml Message-ID: <20031006165600.GB2594@fichte.ai.univie.ac.at> Mail-Followup-To: Michal Moskal , Richard Jones , Claudio Sacerdoti Coen , ocaml-lib-devel@lists.sourceforge.net, caml-list@inria.fr References: <20031005154938.GB31811@fichte.ai.univie.ac.at> <20031006083236.GA8512@redhat.com> <20031006090209.GA2594@fichte.ai.univie.ac.at> <008901c38bfd$aa08b530$6f01a8c0@PWARP> <20031006115403.GA13493@redhat.com> <20031005154938.GB31811@fichte.ai.univie.ac.at> <20031006083236.GA8512@redhat.com> <20031006090209.GA2594@fichte.ai.univie.ac.at> <008901c38bfd$aa08b530$6f01a8c0@PWARP> <20031006114114.GA12034@roke.freak> Mime-Version: 1.0 Content-Type: multipart/mixed; boundary="/9DWx/yDrRhgMJTb" Content-Disposition: inline In-Reply-To: <20031006125246.GA25703@cs.unibo.it> <20031006115403.GA13493@redhat.com> <20031006114114.GA12034@roke.freak> User-Agent: Mutt/1.4.1i X-Loop: caml-list@inria.fr X-Spam: no; 0.00; michal:01 moskal:01 cannasse:01 extlib:01 hashtable:01 hashtable:01 fwiw:01 non-mutable:01 michal:01 monads:01 annotations:01 tightly:01 incompatible:01 sacerdoti:01 coen:01 X-Attachments: name="pMap.ml" name="hashtbl.ml" Sender: owner-caml-list@pauillac.inria.fr Precedence: bulk --/9DWx/yDrRhgMJTb Content-Type: text/plain; charset=us-ascii Content-Disposition: inline On Mon, 06 Oct 2003, Michal Moskal wrote: > On Mon, Oct 06, 2003 at 01:33:18PM +0200, Nicolas Cannasse wrote: > > Manipulating references is most of the time quite a pain, and make the code > > quite ugly. > > I understand in some cases the need of pure functional data structure (Coq > > code proof) but in the "average user" cases that target ExtLib, having a > > mutable structure is surely better. For example I often use an Hashtable > > where a Map would be better for theses two reasons : > > - no need to define a module type (this is corrected by this polymorphic > > version) > > - the hashtable is mutable ! means, easy to use. > > FWIW implementing mutable map on top of non-mutable one is easier and > more efficient then vice versa. Just need to use ref. Otherwise you need > to do some copy() tricks. I completely agree with Michal here: it's essentially impossible to get rid of the imperativeness of a datastructure unless you use some tricks like monads that hide the state. Probably not what the "average user" wants to work with :-) On Mon, 06 Oct 2003, Richard Jones wrote: > Hashtbls are much easier to use than Maps precisely for the reasons he > has outlined. They'd be even better if the language offered syntactic > support for them (but this just reflects my Perl background), eg: Note that you can always easily implement the functionality of Hashtbls using (purely functional) Maps and references - but not easily the other way round! See attachment for an implementation. I haven't tested the Hashtbl-code, but have used type annotations to have the code verified a bit more tightly. Furthermore, I have updated pMap.ml, because, as I have found out, its functional interface was incompatible with the on in Map and also lacked functions. On Mon, 06 Oct 2003, Claudio Sacerdoti Coen wrote: > Most of the time, mutable means non-reentrant. > This point should never be forgot when considering pros and cons > of an implementation. Expecially when dealing with proposed > "standard" libraries for a multi-threaded programming language. Which is another very good argument against impure structures that don't benefit from impurity in terms of efficiency... Regards, Markus -- Markus Mottl http://www.oefai.at/~markus markus@oefai.at --/9DWx/yDrRhgMJTb Content-Type: text/plain; charset=us-ascii Content-Disposition: attachment; filename="pMap.ml" (* * pMap - Polymorphic maps * Copyright (C) 2003 Markus Mottl * * This library is free software; you can redistribute it and/or * modify it under the terms of the GNU Lesser General Public * License as published by the Free Software Foundation; either * version 2.1 of the License, or (at your option) any later version. * * This library is distributed in the hope that it will be useful, * but WITHOUT ANY WARRANTY; without even the implied warranty of * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU * Lesser General Public License for more details. * * You should have received a copy of the GNU Lesser General Public * License along with this library; if not, write to the Free Software * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA *) type ('k, 'v) map = | Empty | Node of ('k, 'v) map * 'k * 'v * ('k, 'v) map * int type ('k, 'v) t = { cmp : 'k -> 'k -> int; map : ('k, 'v) map; } let height = function | Node (_, _, _, _, h) -> h | Empty -> 0 let make l k v r = Node (l, k, v, r, max (height l) (height r) + 1) let bal l k v r = let hl = height l in let hr = height r in if hl > hr + 2 then match l with | Node (ll, lk, lv, lr, _) -> if height ll >= height lr then make ll lk lv (make lr k v r) else (match lr with | Node (lrl, lrk, lrv, lrr, _) -> make (make ll lk lv lrl) lrk lrv (make lrr k v r) | Empty -> assert false) | Empty -> assert false else if hr > hl + 2 then match r with | Node (rl, rk, rv, rr, _) -> if height rr >= height rl then make (make l k v rl) rk rv rr else (match rl with | Node (rll, rlk, rlv, rlr, _) -> make (make l k v rll) rlk rlv (make rlr rk rv rr) | Empty -> assert false) | Empty -> assert false else Node (l, k, v, r, max hl hr + 1) let rec merge t1 t2 = match t1, t2 with | Node (l1, k1, v1, r1, _), Node (l2, k2, v2, r2, _) -> bal l1 k1 v1 (bal (merge r1 l2) k2 v2 r2) | Empty, t -> t | t, Empty -> t let create cmp = { cmp = cmp; map = Empty } let empty = { cmp = compare; map = Empty } let add x d { cmp = cmp; map = map } = let rec loop = function | Node (l, k, v, r, h) -> let c = cmp x k in if c = 0 then Node (l, x, d, r, h) else if c < 0 then let nl = loop l in bal nl k v r else let nr = loop r in bal l k v nr | Empty -> Node (Empty, x, d, Empty, 1) in { cmp = cmp; map = loop map } let find x { cmp = cmp; map = map } = let rec loop = function | Node (l, k, v, r, _) -> let c = cmp x k in if c < 0 then loop l else if c > 0 then loop r else v | Empty -> raise Not_found in loop map let remove x { cmp = cmp; map = map } = let rec loop = function | Node (l, k, v, r, _) -> let c = cmp x k in if c = 0 then merge l r else if c < 0 then bal (loop l) k v r else bal l k v (loop r) | Empty -> Empty in { cmp = cmp; map = loop map } let mem x { cmp = cmp; map = map } = let rec loop = function | Node (l, k, v, r, _) -> let c = cmp x k in c = 0 || loop (if c < 0 then l else r) | Empty -> false in loop map let iter f { map = map } = let rec loop = function | Empty -> () | Node (l, k, v, r, _) -> loop l; f k v; loop r in loop map let map f { cmp = cmp; map = map } = let rec loop = function | Empty -> Empty | Node (l, k, v, r, h) -> Node (loop l, k, f v, loop r, h) in { cmp = cmp; map = loop map } let mapi f { cmp = cmp; map = map } = let rec loop = function | Empty -> Empty | Node (l, k, v, r, h) -> Node (loop l, k, f k v, loop r, h) in { cmp = cmp; map = loop map } let fold f { cmp = cmp; map = map } acc = let rec loop acc = function | Empty -> acc | Node (l, k, v, r, _) -> loop l (f k v (loop r acc)) in loop acc map let enum m = let rec to_list acc = function | Empty -> acc | Node (l, k, v, r, _) -> to_list ((k, v) :: to_list acc r) l in ExtList.List.enum (to_list [] m.map) let uncurry_add (k, v) m = add k v m let of_enum ?(cmp = compare) e = Enum.fold uncurry_add (create cmp) e --/9DWx/yDrRhgMJTb Content-Type: text/plain; charset=us-ascii Content-Disposition: attachment; filename="hashtbl.ml" type ('k, 'v) t = ('k, 'v list ref) PMap.t ref let create () : ('k, 'v) t = ref PMap.empty let clear (m_ref : ('k, 'v) t) : unit = m_ref := PMap.empty let add (m_ref : ('k, 'v) t) (x : 'k) (d : 'v) : unit = try let vlst_ref = PMap.find x !m_ref in vlst_ref := d :: !vlst_ref with Not_found -> m_ref := PMap.add x (ref [d]) !m_ref let copy_ref r = ref !r let copy (m_ref : ('k, 'v) t) : ('k, 'v) t = ref (PMap.map copy_ref !m_ref) let find (m_ref : ('k, 'v) t) (x : 'k) : 'v = List.hd !(PMap.find x !m_ref) let find_all m_ref x : 'v list = !(PMap.find x !m_ref) let mem (m_ref : ('k, 'v) t) (x : 'k) : bool = PMap.mem x !m_ref let remove (m_ref : ('k, 'v) t) (x : 'k) : unit = try let vlst_ref = PMap.find x !m_ref in match !vlst_ref with | [_] -> m_ref := PMap.remove x !m_ref | _ :: rest -> vlst_ref := rest | [] -> assert false with Not_found -> () let replace (m_ref : ('a, 'b) t) x d = try let vlst_ref = PMap.find x !m_ref in vlst_ref := d :: List.tl !vlst_ref with Not_found -> m_ref := PMap.add x (ref [d]) !m_ref let iter (f : 'k -> 'v -> unit) (m_ref : ('k, 'v) t) : unit = let f' k vlst_ref = List.iter (f k) !vlst_ref in PMap.iter f' !m_ref let fold (f : 'k -> 'v -> 'a -> 'a) (m_ref : ('k, 'v) t) (acc : 'a) : 'a = let f' k vlst_ref acc = List.fold_left (fun acc v -> f k v acc) acc !vlst_ref in PMap.fold f' !m_ref acc --/9DWx/yDrRhgMJTb-- ------------------- To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/ Beginner's list: http://groups.yahoo.com/group/ocaml_beginners