Re: [Caml-list] Re: Wanted - General Purpose "Glue Logic" Data-Structures

[Jean-Christophe Filliatre <Jean-Christophe.Filliatre@lri.fr>]

Yaron M. Minsky writes:
 > Resizeable arrays seem like a
 > pretty essential data structure, and the fact that you can't implement
 > them nicely without breaking the standard compiler abstractions (due to
 > the dummy value issue) argues in favor of including it in the
 > distribution, I would think.

There is an easy trick for this dummy value issue.

What you want is an interface looking like:

======================================================================
type 'a t                    (* resizeable vectors *)
val create : int -> 'a t     (* only initial capacity is given *)
val add : 'a t -> 'a -> unit 
...
======================================================================

The idea is  to initially store the capacity as  a negative size, thus
remembering that the data array still needs initialization:

======================================================================
type 'a t = { mutable size : int; mutable data : 'a array }

let create n = 
  if n <= 0 then invalid_arg "create";
  { size = -n; data = [||] }
======================================================================

Note that being empty is having a size less or equal than zero:

======================================================================
let is_empty v = v.size <= 0
======================================================================

Then the first time an addition is performed, you allocate the array:

======================================================================
let add v x =
  if v.size < 0 then begin  (* first addition: we allocate the array *)
    v.data <- Array.create (- v.size) x; v.size <- 0
  end;
  (* code to insert x, resizing data if needed *)
  ...
======================================================================

Hope this helps,
-- 
Jean-Christophe Filliâtre (http://www.lri.fr/~filliatr)

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