Request for weak functional map ...

Request for weak functional map ...

[Christophe Raffalli]

[-- Attachment #1: Type: text/plain, Size: 1600 bytes --]


Hi,

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 ?

Christophe

[-- Attachment #2: OpenPGP digital signature --]
[-- Type: application/pgp-signature, Size: 894 bytes --]

Re: [Caml-list] Request for weak functional map ...

[skaller]

On Fri, 2005-12-02 at 22:11 +0100, Christophe Raffalli wrote:

> Is their functional languages that can do this ?

Yes, Lua can do it. Lua only has ONE data structure,
namely a map. It can be weak on either
the key or the data or both.

-- 
John Skaller <skaller at users dot sf dot net>
Felix, successor to C++: http://felix.sf.net

Re: Request for weak functional map ...

[Stefan Monnier]

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

Of course you can implement it in the GC (although it can be tricky if you
data-structure is complex, as you mention).  But another way to do it is to
use a normal non-weak Map but using weak-references for the keys and then
"every once in a while" scan the map to remove entries whose weak-key has
been collected.

If you implement the Map yourself (rather than using the library version),
you can do the weak-key-sweep as part of the normal tree traversal done
during lookups and insertions.


        Stefan