English version
Accueil     À propos     Téléchargement     Ressources     Contactez-nous    

Ce site est rarement mis à jour. Pour les informations les plus récentes, rendez-vous sur le nouveau site OCaml à l'adresse ocaml.org.

Browse thread
How to do this properly with OCaml?
[ Home ] [ Index: by date | by threads ]
[ Search: ]

[ Message by date: previous | next ] [ Message in thread: previous | next ] [ Thread: previous | next ]
Date: 2005-07-23 (19:50)
From: Stephane Glondu <Stephane.Glondu@c...>
Subject: Re: [Caml-list] How to do this properly with OCaml?
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.


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