ocaml-lib-devel

[Ocaml-lib-devel] Proposed addition to DynArray

[William D. N. <wne...@cs...>]

I currently need some of the DynArrays that I'm working with to have the
ability to expand to a given size without adding a series of elements
onto the end of the array (I have a situation  where I need to expand the
size of the array to fit the data I will be adding, but I might be adding
the elements out of order, so I can't just call DynArray.add).

Now, I can easily do this externally with a call to make and then blit
(or append if the DynArray is a non-mutable record field or class
member), or I could add it to my local copy of the DynArray module itself
via something like:

let expand darr new_length =
  if new_length > darr.length then
    changelength darr (new_length - darr.length)

and adding the appropriate blurb to the interface.

I'm just wondering if anyone else thinks this would be useful enough to
add to the DynArray module proper... Discuss.

William D. Neumann

---

"Well I could be a genius, if I just put my mind to it.
And I...I could do anything, if only I could get 'round to it.
Oh we were brought up on the space-race, now they expect you to clean toilets.
When you've seen how big the world is, how can you make do with this?
If you want me, I'll be sleeping in - sleeping in throughout these glory days."

	-- Jarvis Cocker

Re: [Ocaml-lib-devel] Proposed addition to DynArray

[Brian H. <bri...@ql...>]

On Thu, 29 May 2003, William D. Neumann wrote:

> I have a situation  where I need to expand the
> size of the array to fit the data I will be adding, but I might be adding
> the elements out of order, so I can't just call DynArray.add

I don't have a problem with a pre-expand, but adding elements out of order 
doesn't work (at least the way I think they work).  If the dynarray has n 
elements, the elements are numbers 0..n-1 inclusive.

The solution is to use a 'a option Dynarray.t.  You're null element then
becomes None.  I dislike exposing the null elements as "valid entries"- to
my mind, they're just filler.  This is especially important if you
consider an int Dynarray.t - is that 0 a real, important 0, or a null
element?  So I would would fake up a enum that returns n Nones and append
it to the dynarray to increase the size.  Dynarray.set can then change the
Nones to Some x.

We might want to consider adding a function in Enum to create an enum that 
returns so many of a given value, to make this easier.

Brian

Re: [Ocaml-lib-devel] Proposed addition to DynArray

[William D. N. <wne...@cs...>]

On Thu, 29 May 2003, Brian Hurt wrote:

> I don't have a problem with a pre-expand, but adding elements out of order
> doesn't work (at least the way I think they work).  If the dynarray has n
> elements, the elements are numbers 0..n-1 inclusive.
>
> The solution is to use a 'a option Dynarray.t.  You're null element then
> becomes None.  I dislike exposing the null elements as "valid entries"- to
> my mind, they're just filler.  This is especially important if you
> consider an int Dynarray.t - is that 0 a real, important 0, or a null
> element?  So I would would fake up a enum that returns n Nones and append
> it to the dynarray to increase the size.  Dynarray.set can then change the
> Nones to Some x.

Yeah, exposing phony nulls was one of the philisophical issues I was
wrestling with as I added my expansion hack.  At the time I decided that
the ability to do this outweighed the potential to do something silly (and
I promised myself to always look out for null values (the null I'm using
in this case would never be a valid value, so I can ignore them when I run
across them).

And you're right, expanding the array the way I described it won't work
like I wanted, you have to do something along the lines of:

let null = "";;
let j = DynArray.make 2 null;;
DynArray.add j "blah";;
DynArray.add j "flah";;

(* Now I want to add something to slot 9 *)

ignore (Dynarray.append j (DynArray.init 8 8 null (fun x -> null)));;
DynArray.set j 9 "flee";;

Where the length field is artificially pushed out to the end of the array,
so stuff can be added out of order.  But this does expose all those
not-really-null nulls in spots 2 - 8.  Now that I think about it this
might be best left out.  However, if it is added, it should be called
unsafe_expand or something similar so people realize that they're
willfully doing something "incorrect".

Sigh...why does doing things the right way always interfere with doing
what I think I want...

William D. Neumann

---

"Well I could be a genius, if I just put my mind to it.
And I...I could do anything, if only I could get 'round to it.
Oh we were brought up on the space-race, now they expect you to clean toilets.
When you've seen how big the world is, how can you make do with this?
If you want me, I'll be sleeping in - sleeping in throughout these glory days."

	-- Jarvis Cocker

Re: [Ocaml-lib-devel] Proposed addition to DynArray

[Brian H. <bri...@ql...>]

On Thu, 29 May 2003, William D. Neumann wrote:

> On Thu, 29 May 2003, Brian Hurt wrote:
> 
> Yeah, exposing phony nulls was one of the philisophical issues I was
> wrestling with as I added my expansion hack.  At the time I decided that
> the ability to do this outweighed the potential to do something silly (and
> I promised myself to always look out for null values (the null I'm using
> in this case would never be a valid value, so I can ignore them when I run
> across them).

One of the reasons I didn't want to use options as the array elements- for 
the cases where they weren't needed, and there really was a safe null.

> 
> And you're right, expanding the array the way I described it won't work
> like I wanted, you have to do something along the lines of:
> 
> let null = "";;
> let j = DynArray.make 2 null;;
> DynArray.add j "blah";;
> DynArray.add j "flah";;
> 
> (* Now I want to add something to slot 9 *)
> 
> ignore (Dynarray.append j (DynArray.init 8 8 null (fun x -> null)));;
> DynArray.set j 9 "flee";;

Given:

let enum_dup c val =
    (* returns an enumeration which is just val repeated c times *)
    let cref = ref c in
    let next () = if (!cref) > 0 then decr cref; val 
                  else raise No_more_elements
    and count () = !cref
    in
    Enum.make ~next:next ~count:count

You don't actually need to create the intermediate array.  You can just 
do:

DynArray.set_enum j (DynArray.length j) (enum_dup 8 "");
DynArray.set j 9 "flee";;

Mental note to self: need to add DynArray.append_enum.

> Sigh...why does doing things the right way always interfere with doing
> what I think I want...

Because what you think you wanted to do is not what you really wanted to 
do.  Perhaps instead of a Dynamic Array, you wanted a hash table mapping 
int->'a?

Brian

Re: [Ocaml-lib-devel] Proposed addition to DynArray

[Nicolas C. <war...@fr...>]

> let enum_dup c val =
>     (* returns an enumeration which is just val repeated c times *)
>     let cref = ref c in
>     let next () = if (!cref) > 0 then decr cref; val 
>                   else raise No_more_elements
>     and count () = !cref
>     in
>     Enum.make ~next:next ~count:count

Added to the CVS :

Enum.init :  int -> (int -> 'a) -> 'a t

Similar to List.init and Array.init

Nicolas Cannasse