Purely functional equivalent of weakhashmap?

Weak hash tables like Java's weak hash map use weak references to track the collection of unreachable keys by the garbage collector and remove bindings with that key from the collection. Weak hash tables are typically used to implement indirections from one vertex or edge in a graph to another because they allow the garbage collector to collect unreachable portions of the graph.

Is there a purely functional equivalent of this data structure? If not, how might one be created?

This seems like an interesting challenge. The internal implementation cannot be pure because it must collect (i.e. mutate) the data structure in order to remove unreachable parts but I believe it could present a pure interface to the user, who could never observe the impurities because they only affect portions of t开发者_开发问答he data structure that the user can, by definition, no longer reach.

---

That's an interesting concept. One major complication in a "purely functional" setting would be that object identity is not normally observable in a "purely functional" sense. I.E., if I copy an object or create a new identical one, in Java it's expected that the clone is not the original. But in a functional setting, it is expected that the new one be semantically identical to the old one, even though the garbage collector will treat it differently.

So, if we allow object identity to be a part of the semantics, it would be sound, otherwise probably not. In the latter case, even if a hack could be found (I thought of one, described below), you're likely to have the language implementation fighting you all over the place because it's going to do all sorts of things to exploit the fact that object identity is not supposed to be observable.

One 'hack' that popped into my mind would be to use unique-by-construction values as keys, so that for the most part value equality will coincide with reference equality. For example, I have a library I use personally in Haskell with the following in its interface:

data Uniq s
getUniq :: IO (Uniq RealWorld)
instance Eq (Uniq s)
instance Ord (Uniq s)

A hash map like you describe would probably mostly-work with these as key, but even here I can think of a way it might break: Suppose a user stores a key in a strict field of some data structure, with the compiler's "unbox-strict-fields" optimization enabled. If 'Uniq' is just a newtype wrapper to a machine integer, there may no longer be any object to which the GC can point and say "that's the key"; so when the user goes and unpacks his key to use it, the map may have forgotten about it already. (Edit: This particular example can obviously be worked around; make Uniq's implementation be something that can't be unboxed like that; the point is just that it's tricky precisely because the compiler is trying to be helpful in a lot of ways we might not expect)

TL;DR: I wouldn't say it can't be done, but I suspect that in many cases "optimizations" will either break or be broken by a weak hash map implementation, unless object identity is given first-class observable status.

---

Purely functional data-structures can't change from the user perspective. So, if I get a key from a hash-map, wait, and then get the same key again, I have to get the same value. I can hold onto keys, so they can't disappear.

The only way it could work is if the API gives me the next generation and the values aren't collected until all references to the past versions of the container are released. Users of the data-structure are expected to periodically ask for new generations to release weakly held values.

EDIT (based on comment): I understand the behavior you want, but you can't pass this test with a map that releases objects:

FunctionalWeakHashMap map = new FunctionalWeakHashMap();

{ // make scope to make o have no references
   Object o = new SomeObject();
   map["key"] = o;
}  // at this point I lose all references to o, and the reference is weak

// wait as much time as you think it takes for that weak reference to collect, 
// force it, etc

Assert.isNotNull(map["key"]); // this must be true or map is not persistent

I am suggesting that this test could pass

FunctionalWeakHashMap map = new FunctionalWeakHashMap();

{ // make scope to make o have no references
   Object o = new SomeObject();
   map["key"] = o;
}  // at this point I lose all references to o, and the reference is weak in the map

// wait as much time as you think it takes for that weak reference to collect, 
// force it, etc

map = map.nextGen();

Assert.isNull(map["key"]);