Version française
Home     About     Download     Resources     Contact us    
Browse thread
[Caml-list] Multi-keyed lookup table?
[ Home ] [ Index: by date | by threads ]
[ Search: ]

[ Message by date: previous | next ] [ Message in thread: previous | next ] [ Thread: previous | next ]
Date: -- (:)
From: Marcin 'Qrczak' Kowalczyk <qrczak@k...>
Subject: Re: [Caml-list] Array.filter (was Multi-keyed lookup table?)
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