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

[Michal Moskal <malekith@pld-linux.org>]

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