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

[Stephane Glondu <Stephane.Glondu@crans.org>]

On Saturday 23 July 2005 12:35, Thomas Fischbacher wrote:
> This seems to be equivalent to the idea of using an array option, which
> I mentioned earlier.

Indeed.

> Problems:
>
> What if I have operations that add and remove elements on the heap in
> random order (so that the heap sometimes has to shrink), and I want
> (1) that every element which was removed from the heap and is otherwise
> inaccessible can be reclaimed by GC,

When you want to "remove" an element, you can put another (random) value 
from the same array at its place so that it can be garbage collected. If 
the remaining heap is empty (i.e. there is no other value to pick), you 
replace the Fill a with Empty n.

> and (2) that removing a single  
> element from the heap does not require copying the underlying Array?

This is a matter of algorithmics, isn't it?


Stephane Glondu.