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

[ijtrotts@ucdavis.edu]

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