Re: [Ocaml-lib-devel] ExtArray?

[Brian H. <bh...@sp...>]

On Thu, 24 Nov 2005, Richard W. M. Jones wrote:

> On Thu, Nov 24, 2005 at 03:56:20PM +0000, Amit Dubey wrote:
>>> Array.filter
>>>> Array.find_all
>>>> Array.partition
>>>>
>>>> Would these return lists or arrays?
>>>
>>> I think it's better to return arrays, but what do people think about
>>> that?
>>
>> Actually, I agree it makes complete sense for partition.  As I think about
>> it, I think filter and find_all should be different.  find_all should return
>> a list, and filter should return an array.  And possibly, filter should be
>> defined in terms of find_all.
>
> Perhaps you can share your thinking on this :-)
>
> I think the principle of least surprise is going to be that
> Array.filter should return an array - this is surely what users would
> expect.  The problem will be in the implementation which may require
> two passes -- it could be solved better if there was a truncation
> primitive for arrays.

I wonder if something like this (coding into email- ymmv) might work:

let filter f arr =
     let len = Array.length arr in
     if len == 0 then
         [| |]
     else
     let bits = String.make ((len + 7)/8) '\000' in
     let rec loop i c =
         if (i >= len) then
             c
         else
             if f arr.(i) then
                 begin
                     bits.[i/8] <- char_of_int (
                         (int_of_char bits.[i/8]) lor (1 lsl (i mod 8))
                     );
                     loop (i+1) (c+1)
                 end
             else
                 loop (i+1) c
     in
     let rlen = loop 0 0 in
     if rlen == 0 then
         [| |]
     else
     let rarr = Array.make rlen arr.(0) in
     let rec loop2 i j =
         if j >= rlen then
             rarr
         else if (((int_of_char bits.[i/8]) lsr (i mod 8)) land 1) == 1
         then
 	            begin
                 rarr.(j) <- arr.(i);
                 loop2 (i+1) (j+1)
             end
         else
             loop2 (i+1) j
     in
     loop2 0 0
;;

OK, that's a little more complicated than I originally envisioned.  But 
the idea is to use a bit field (in this case a string) to hold the 
"results" of the filter function- 0 for not copying the element over and 1 
for copying the element over.  So we do two passes, but the filter 
function is only called for one- on the second pass, we just use the saved 
results.

Brian