Re: [Caml-list] How to do this properly with OCaml?

[Berke Durak <obdurak@free.fr>]

On Fri, Jul 22, 2005 at 04:26:55PM +0200, Thomas Fischbacher wrote:
> I repeatedly stumble across problems where I would like to use a 
> programming style which seems quite out of line with how one is supposed 
> to use OCaml (to say it otherwise, it looks outright wrong and 
> horrendously ugly), but which nevertheless might be just appropriate for 
> the situation in question. So, I would like to hear the opinion of the 
> OCaml community about this.
> 
> Imagine constructing a binary heap of tuples. It is somewhat neat to be 
> able to just use an array to store the entries of the heap which is 
> pre-allocated to some fixed size and replaced by a larger array whenever 
> more space is needed. The only thing known about the heap's entries at 
> compile time is that they are bound to be tuples, hence boxed objects,
> but nothing else is known about their size or even type.
> 
> As one does not have a prototype of such a tuple at the time the array is 
> created, it seems to me as if the best thing one could do in OCaml would 
> be:
> 
> (1) Make an array of <tuple> option and initially fill it with None.
> 
> (2) Make an optional array of tuples which is None until the first entry 
> is made.

I feel some psychorigidity here.  Maybe some
3-[2-[4-(6-fluoro-1,2-benzisoxazol-3-yl)-1-piperidinyl]ethyl]-6,7,8,9-
tetrahydro-2-methyl-4H-pyrido[1,2-a]pyrimidin-4-one can help ?  Just
joking.

I'd suggest you provide a "zero" value for whatever type you want
to put in your heap.  That "zero" value should have a small memory
footprint.  This value does not need to be distinct from possible values
for your heap, since the length information is required and sufficient for
knowing which entries of your array are empty.  You could package the whole
stuff into a modules.  Example :

modul type ELEMENTS =
  sig
    type t
    val zero : t
  end

module Heap(E : ELEMENTS) =
  sig
    type t = {
      a : E.t array;
      mutable n : int; (* count *)
    }

    let create () = { a = Array.make 256 E.zero ; n = 0 }

    etc.
  end
-- 
Berke Durak