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 UAA08814; Fri, 30 Apr 2004 20:51:32 +0200 (MET DST) X-Authentication-Warning: pauillac.inria.fr: majordomo set sender to owner-caml-list@pauillac.inria.fr using -f Received: from concorde.inria.fr (concorde.inria.fr [192.93.2.39]) by pauillac.inria.fr (8.7.6/8.7.3) with ESMTP id UAA08787 for ; Fri, 30 Apr 2004 20:51:31 +0200 (MET DST) Received: from out2.smtp.messagingengine.com (out2.smtp.messagingengine.com [66.111.4.26]) by concorde.inria.fr (8.12.10/8.12.10) with ESMTP id i3UIpTSH004029 for ; Fri, 30 Apr 2004 20:51:30 +0200 X-Sasl-enc: VWH8R0mMbHBNhQw1e2XtZA 1083351087 Received: from [192.168.1.100] (unknown [218.81.128.244]) by mail.messagingengine.com (Postfix) with ESMTP id 64D17AD1F01; Fri, 30 Apr 2004 14:51:25 -0400 (EDT) Date: Sat, 1 May 2004 02:51:17 +0800 (HKT) From: Martin Jambon X-X-Sender: martin@localhost To: Rahul Siddharthan Cc: caml-list@inria.fr Subject: Re: [Caml-list] "List.index" or "List.unique" functions? In-Reply-To: <20040430175429.GB11118@online.fr> Message-ID: MIME-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII X-Miltered: at concorde with ID 4092A032.000 by Joe's j-chkmail (http://j-chkmail.ensmp.fr)! X-Loop: caml-list@inria.fr X-Spam: no; 0.00; caml-list:01 grail:01 python:01 hash:01 hashtbl:01 hashtbl:01 accu:01 accu:01 ocaml:01 rec:01 rec:01 concise:01 match:02 match:02 jambon:02 Sender: owner-caml-list@pauillac.inria.fr Precedence: bulk On Fri, 30 Apr 2004, Rahul Siddharthan wrote: > I just discovered OCaml a week or so ago, and it really seems to be > the "holy grail" -- more concise and elegant that python, almost as > fast as C. I wish I'd known of it a year ago. Now I just need to get > used to the functional way of thinking... > > I have a question: suppose I have a list l1, and I want to create a new > list l2 with only one copy of any repeated members of the first list > (eg, l1=[1;2;3;4;3;4;5;6;5] -> l2=[1;2;3;4;5;6]) 1) Naive O(n^2) solution: let rec unique = function [] -> [] | hd :: tl -> if List.mem hd tl then unique tl else hd :: unique tl The result is not sorted. 2) With a hash table you can get something quite efficient (O(n)) and not too difficult to write: let unique l = let tbl = Hashtbl.create 10 in List.iter (fun i -> Hashtbl.replace tbl i ()) l; Hashtbl.fold (fun key data accu -> key :: accu) tbl [] The result is not sorted. You can replace "10" with "List.length l" if really you don't have any idea of the initial size of the table and want to avoid multiple resizings of the table. "fold" functions (List.fold_left, List.fold_right, Hashtbl.fold, Array.fold_left...) are very useful, and are most of the time more appropriate than imperative loops ("for" and "while"). 3) With sort/simplify (O(n log n)) (I expect it to be much less efficient than 2)): let unique l = let rec simplify last l = match l with [] -> [last] | hd :: tl -> if hd = last then simplify last tl else last :: simplify hd tl in match List.sort compare l with [] -> [] | hd :: tl -> simplify hd tl Martin ------------------- 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