Rein funktionales Äquivalent von weakhashmap?

Question

Schwache Hashtabellen wie Java's weak hash map verwenden schwache Verweise, um die Sammlung nicht erreichbarer Schlüssel vom Garbage Collector zu verfolgen und Bindungen mit diesem Schlüssel aus der Sammlung zu entfernen. Schwache Hashtabellen werden normalerweise verwendet, um Umleitungen von einem Scheitelpunkt oder einer Kante in einem Diagramm zu einem anderen zu implementieren, da sie es dem Speicherbereiniger ermöglichen, nicht erreichbare Teile des Graphen zu sammeln.

Gibt es ein rein funktionales Äquivalent dieser Datenstruktur? Wenn nicht, wie könnte man erschaffen werden?

Dies scheint eine interessante Herausforderung. Die interne Implementierung kann nicht rein sein, da sie die Datenstruktur sammeln (dh mutieren) muss, um unerreichbare Teile zu entfernen, aber ich glaube, dass sie eine reine Schnittstelle für den Benutzer darstellen könnte, der die Unreinheiten nie beobachten könnte, weil sie nur Teile der Daten betreffen Struktur, die der Benutzer definitionsgemäß nicht mehr erreichen kann.

Answer 1

Rein funktionale Datenstrukturen können sich aus der Benutzerperspektive nicht ändern. Also, wenn ich einen Schlüssel von einer Hash-Karte bekomme, warte, und dann den gleichen Schlüssel wieder, muss ich den gleichen Wert bekommen. Ich kann Schlüssel festhalten, damit sie nicht verschwinden können.

Der einzige Weg, es könnte funktionieren, wenn die API mir die nächste Generation gibt und die Werte nicht gesammelt werden, bis alle Verweise auf die früheren Versionen des Containers freigegeben sind. Von den Benutzern der Datenstruktur wird erwartet, dass sie regelmäßig nach neuen Generationen fragen, um schwach gehaltene Werte freizugeben.

EDIT (basierend auf Kommentar): Ich habe das Verhalten verstehen Sie wollen, aber Sie können diesen Test mit einer Karte nicht passieren, die Objekte freigibt:

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 

ich vorschlage, dass dieser Test

passieren konnte

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"]); 

Answer 2

Das ist ein interessantes Konzept. Eine Hauptkomplikation bei einer "rein funktionalen" Einstellung wäre, dass die Objektidentität normalerweise nicht in einem "rein funktionalen" Sinn wahrnehmbar ist. Wenn ich beispielsweise ein Objekt kopiere oder ein neues identisches Objekt erstelle, wird in Java erwartet, dass der Klon nicht das Original ist. Aber in einer funktionalen Umgebung wird erwartet, dass die neue semantisch identisch mit der alten ist, obwohl der Garbage Collector sie anders behandelt.

Also, wenn wir zulassen, dass Objektidentität ein Teil der Semantik ist, wäre es Ton, sonst wahrscheinlich nicht. In letzterem Fall, selbst wenn ein Hack gefunden werden könnte (ich dachte an einen, der unten beschrieben wird), wird es wahrscheinlich sein, dass die Sprachimplementierung Sie überall hin bekämpfen wird, weil er alle möglichen Dinge tun wird, um diese Tatsache auszunutzen Diese Objektidentität soll nicht beobachtbar sein.

Ein 'Hack', der mir in den Sinn kam, wäre die Verwendung von Unique-by-Construction-Werten als Schlüssel, so dass die Wertgleichheit größtenteils mit der Referenzgleichheit übereinstimmt. Zum Beispiel habe ich eine Bibliothek, die ich persönlich mit der folgenden in ihrer Schnittstelle in Haskell verwenden:

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

Eine Hash-Karte wie Sie beschreiben, würde wahrscheinlich meist Arbeit mit diesen als Schlüssel, aber auch hier kann ich von einem denken So könnte es brechen: Angenommen, ein Benutzer speichert einen Schlüssel in einem strikten Feld einer Datenstruktur, wobei die Optimierung der "Unbox-Strict-Fields" -Funktion des Compilers aktiviert ist. Wenn "Uniq" nur ein Wrapper vom Typ newtyp zu einer Maschinen-Ganzzahl ist, ist möglicherweise kein Objekt mehr vorhanden, auf das der GC zeigen und sagen kann "das ist der Schlüssel". Wenn der Benutzer seinen Schlüssel auspackt und ihn dann auspackt, kann die Karte dies bereits vergessen haben.(Edit: Dieses spezielle Beispiel kann offensichtlich umgangen werden; machen Uniqs Implementierung zu etwas, das so nicht entkoppelt werden kann; der Punkt ist nur, dass es schwierig ist, gerade weil der Compiler versucht, in vielerlei Hinsicht hilfreich zu sein erwarten)

TL; DR: Ich würde nicht sagen, dass es nicht getan werden kann, aber ich vermute, dass "Optimierungen" in vielen Fällen entweder brechen oder durch eine schwache Hash-Map-Implementierung gebrochen werden, sofern Objekt-Identität gegeben ist erstklassiger beobachtbarer Status