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 EAA11368; Mon, 11 Aug 2003 04:39:41 +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 EAA23602 for ; Mon, 11 Aug 2003 04:39:40 +0200 (MET DST) Received: from manzanita (63-217-154-71.greystoneapts.com [63.217.154.71]) by nez-perce.inria.fr (8.11.1/8.11.1) with ESMTP id h7B2ddT20125 for ; Mon, 11 Aug 2003 04:39:39 +0200 (MET DST) Received: from ijtrotts by manzanita with local (Exim 3.36 #1 (Debian)) id 19lg5O-0000nn-00 for ; Sat, 09 Aug 2003 19:37:34 -0700 Date: Sat, 9 Aug 2003 19:37:34 -0700 From: ijtrotts@ucdavis.edu To: caml-list@inria.fr Subject: Re: [Caml-list] Array.filter (was Multi-keyed lookup table?) Message-ID: <20030810023734.GB3019@localhost> References: <005d01c35e51$7c927200$6628f9c1@zofo> <20030809184851.GA946@localhost> <20030810195307.GA19113@roke.freak> <200308102223.05184.qrczak@knm.org.pl> Mime-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Disposition: inline In-Reply-To: <200308102223.05184.qrczak@knm.org.pl> User-Agent: Mutt/1.5.4i X-Loop: caml-list@inria.fr X-Spam: no; 0.00; ijtrotts:01 caml-list:01 marcin:01 'qrczak':01 kowalczyk:01 nie:99 michal:01 moskal:01 shorter:01 issac:01 trotts:01 davis:99 center:98 rec:01 0200,:01 Sender: owner-caml-list@pauillac.inria.fr Precedence: bulk On Sun, Aug 10, 2003 at 10:23:05PM +0200, Marcin 'Qrczak' Kowalczyk wrote: > Dnia nie 10. sierpnia 2003 21:53, Michal Moskal napisa?: > > > 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. Mine is tested (on a small example), is shorter, and takes O(1) stack :o). Issac -- Issac Trotts Programmer Center for Neuroscience University of California, Davis ------------------- 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