Version française
Home     About     Download     Resources     Contact us    

This site is updated infrequently. For up-to-date information, please visit the new OCaml website at

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: David Brown <caml-list@d...>
Subject: Re: [Caml-list] Array.filter (was Multi-keyed lookup table?)
On Sat, Aug 09, 2003 at 07:34:35PM -0700, 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 Archives:
Bug reports: FAQ:
Beginner's list: