Re: [Caml-list] Array.filter (was Multi-keyed lookup table?)

["Marcin 'Qrczak' Kowalczyk" <qrczak@knm.org.pl>]

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