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

[David Brown <caml-list@davidb.org>]

On Sat, Aug 09, 2003 at 07:34:35PM -0700, ijtrotts@ucdavis.edu wrote:

> # let filter f a = 
>    let n = ref 0 in 
>    for i = 0 to Array.length a - 1 do if f a.(i) then incr n done;
>    let k = ref 0 in 
>    Array.init !n 
>     (fun i -> while not (f a.(!k)) do incr k done; incr k; a.(!k-1));;

Unfortunately, this calls f twice on each element.  If that solution is
not acceptable, then the results of f a.(i) could be cached in some type
of bit array (perhaps in a string), and then that string iterated again.

This function also poorly if f a.(i) isn't really functional, and
returns different results.  For example:

   List.filter (fun _ -> Random.bool) data

will return roughly half of the items, randomly.  This would cause array
bounds problems about half the time with the above code.

Dave Brown

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