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
Request for weak functional map ...
[ Home ] [ Index: by date | by threads ]
[ Search: ]

[ Message by date: previous | next ] [ Message in thread: previous | next ] [ Thread: previous | next ]
Date: 2005-12-02 (21:11)
From: Christophe Raffalli <christophe.raffalli@u...>
Subject: Request for weak functional map ...


It is a the second time I am in need for this ... Let me explain.

I wish a data structure similar to the Map provided by standard library
(logarithmic insertion and deletion) ... but with a "weak key" behavior:

This means that when the key is no more accessible by the GC, all the
bindings of this key are erased in all maps by the next GC.

Typicaly, key will be records with a unique ID used for the comparison
... So when the key is no more accessible, you are sure the bindings to
this key are useless.

I think it is not trivial to implement this in the GC, but if you can
have a removal in balanced tree that does no allocation (reusing the
existing cell), then the sweep/copy phase of the GC could do the removal.

BTW: I think this is impossible to implement using the Weak module ...
but I am not so sure. (it may be possible to implement if you do not
have the logarithmic requirement in complexity, but all insertiosn will
copy a weak array and a standard array ... this is not reasonable).

BTW2: there is also a solution with a weak array/hashtbl of all maps
using a given key stored in the key record itself (you could point to
the nodes of the balanced tree using the key, and wait the next
insertion to rebalance the tree when deleting the key) ... then a
finaliser could do the removal job ... But this does not look nice,
because the data type for the key is not "free" anymore, and it also
looks quite bad for the complexity.

Are they other people that think this is a usefull feature to add to the
language ?

Is their functional languages that can do this ?