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 WAA13421; Sun, 10 Aug 2003 22:23:12 +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 WAA14430 for <caml-list@pauillac.inria.fr>; Sun, 10 Aug 2003 22:23:11 +0200 (MET DST)
Received: from qrnik.knm.org.pl (paf87.warszawa.sdi.tpnet.pl [217.96.225.87])
	by nez-perce.inria.fr (8.11.1/8.11.1) with ESMTP id h7AKN8T12294
	for <caml-list@inria.fr>; Sun, 10 Aug 2003 22:23:11 +0200 (MET DST)
Received: from localhost ([127.0.0.1] ident=qrczak)
	by qrnik.knm.org.pl with esmtp (Exim 3.36 #1)
	id 19lwiX-0004NH-00
	for caml-list@inria.fr; Sun, 10 Aug 2003 22:23:05 +0200
From: "Marcin 'Qrczak' Kowalczyk" <qrczak@knm.org.pl>
To: caml-list@inria.fr
Subject: Re: [Caml-list] Array.filter (was Multi-keyed lookup table?)
Date: Sun, 10 Aug 2003 22:23:05 +0200
User-Agent: KMail/1.5.1
References: <005d01c35e51$7c927200$6628f9c1@zofo> <20030809184851.GA946@localhost> <20030810195307.GA19113@roke.freak>
In-Reply-To: <20030810195307.GA19113@roke.freak>
MIME-Version: 1.0
Content-Type: text/plain;
  charset="iso-8859-2"
Content-Transfer-Encoding: 8bit
Content-Disposition: inline
Message-Id: <200308102223.05184.qrczak@knm.org.pl>
X-Loop: caml-list@inria.fr
X-Spam: no; 0.00; marcin:01 'qrczak':01 kowalczyk:01 qrczak:01 caml-list:01 nie:99 michal:01 moskal:01 rec:01 knm:01 stack:02 heap:03 obj:03 let:04 array:04 
Sender: owner-caml-list@pauillac.inria.fr
Precedence: bulk

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.

-- 
   __("<         Marcin Kowalczyk
   \__/       qrczak@knm.org.pl
    ^^     http://qrnik.knm.org.pl/~qrczak/

-------------------
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