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 WAA28351; Sun, 10 Aug 2003 22:46:31 +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 WAA16534 for ; Sun, 10 Aug 2003 22:46:30 +0200 (MET DST) Received: from ep09.kernel.pl (ep09.kernel.pl [212.87.11.162]) by concorde.inria.fr (8.11.1/8.11.1) with ESMTP id h7AKkOf26932 for ; Sun, 10 Aug 2003 22:46:24 +0200 (MET DST) Received: (qmail 8603 invoked by uid 566); 10 Aug 2003 20:45:30 -0000 Date: Sun, 10 Aug 2003 22:43:19 +0200 From: Michal Moskal To: caml-list@inria.fr Subject: Re: [Caml-list] Array.filter (was Multi-keyed lookup table?) Message-ID: <20030810204319.GA24968@roke.freak> Mail-Followup-To: caml-list@inria.fr References: <005d01c35e51$7c927200$6628f9c1@zofo> <20030809184851.GA946@localhost> <20030810195307.GA19113@roke.freak> <200308102222.16369.qrczak@knm.org.pl> Mime-Version: 1.0 Content-Type: text/plain; charset=iso-8859-2 Content-Disposition: inline Content-Transfer-Encoding: 8bit In-Reply-To: <200308102222.16369.qrczak@knm.org.pl> User-Agent: Mutt/1.4.1i X-PGP-Fingerprint: CF89 1B14 11BE 1CC9 2CA3 7497 5E32 69B4 BC71 B4C2 X-AntiVirus: scanned for viruses by AMaViS 0.2.1 (http://amavis.org/) X-Loop: caml-list@inria.fr X-Spam: no; 0.00; michal:01 moskal:01 malekith:01 pld-linux:01 caml-list:01 marcin:01 'qrczak':01 kowalczyk:01 nie:99 predicate:01 arrays:01 bool:01 kernel:01 int:01 rec:01 Sender: owner-caml-list@pauillac.inria.fr Precedence: bulk On Sun, Aug 10, 2003 at 10:22:16PM +0200, Marcin 'Qrczak' Kowalczyk wrote: > Dnia nie 10. sierpnia 2003 21:53, Michal Moskal napisał: > > > > # Array.filter (fun x -> x * x) [| 1;2;3 |];; > > > - : int array = [|1; 4; 9|] > > > > This is map, not filter. Writing filter is more difficult, since you > > need to first make list of results and then put them into array (or use > > Obj.magic tricks). > > let filter pred arr = > let sz = Array.length arr in > if sz == 0 then arr else > let rec loop i j = > if i >= sz then Array.make j arr.(0) else > let x = arr.(i) in > if pred x then begin > let result = loop (i + 1) (j + 1) in > result.(j) <- x; > result > end else loop (i + 1) j in > loop 0 0 > > Untested. Doesn't make a list on heap but uses O(result_length) stack. It will bomb for large arrays. List.filter will not (BTW I don't understand why List.filter uses List.rev to be tail recursive and List.map does not). Another thought would be to create bool array for predicate results, fill it, counting how much space do you need, and then create result array. There is also third way, to run predicate twice, but it is not guaranteed safe in presence of side effects. -- : Michal Moskal :: http://www.kernel.pl/~malekith : GCS {C,UL}++++$ a? !tv : When in doubt, use brute force. -- Ken Thompson : {E-,w}-- {b++,e}>+++ h ------------------- 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