Чисто функциональный эквивалент weakhashmap?

Question

Слабые хеш-таблицы, такие как Java's weak hash map, используют слабые ссылки для отслеживания коллекции недоступных ключей сборщиком мусора и удаления привязок с этим ключом из коллекции. Слабые хеш-таблицы обычно используются для реализации маршрутов с одной вершины или края в графике на другой, поскольку они позволяют сборщику мусора собирать недостижимые части графика.

Существует ли чисто функциональный эквивалент этой структуры данных? Если нет, как можно создать?

Это похоже на интересную задачу. Внутренняя реализация не может быть чистой, поскольку она должна собирать (т. Е. Мутировать) структуру данных, чтобы удалить недостижимые части, но я считаю, что она может представлять чистый интерфейс для пользователя, который никогда не мог наблюдать за примесями, поскольку они влияют только на части данных структура, которую пользователь, по определению, больше не достигает.

Answer 1

Совершенно функциональные структуры данных не могут меняться с точки зрения пользователя. Итак, если я получу ключ из хэш-карты, подождите, а затем снова получите тот же ключ, мне нужно получить то же значение. Я могу держать ключи, поэтому они не могут исчезнуть.

Единственный способ, которым это могло бы работать, - это, если API дает мне следующее поколение, и значения не собираются до тех пор, пока не будут выпущены все ссылки на прошлые версии контейнера. Ожидается, что пользователи структуры данных будут периодически просить новые поколения выпускать слабо удерживаемые значения.

EDIT (на основе комментариев): Я понимаю поведение, которое вы хотите, но вы не можете пройти этот тест с картой, которая высвобождает объекты:

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 

Я предполагаю, что этот тест может пройти

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

Это интересная концепция. Одним из основных осложнений в «чисто функциональной» настройке было бы то, что идентичность объекта обычно не наблюдается в «чисто функциональном» смысле. I.Е., если я копирую объект или создаю новый идентичный, в Java ожидается, что клон не является оригиналом. Но в функциональной настройке ожидается, что новый будет семантически идентичным старому, хотя сборщик мусора будет рассматривать его по-разному.

Итак, если мы разрешаем идентификацию объекта быть частью семантики, это будет звук, иначе, вероятно, нет. В последнем случае, даже если взломать можно было бы найти (я подумал об одном, описанном ниже), у вас, вероятно, будет реализация языка, сражающаяся с вами повсюду, потому что она собирается делать всевозможные вещи, чтобы использовать этот факт что идентификация объекта не должна быть наблюдаемой.

Один из «взломов», который появился в моем сознании, заключался бы в использовании значений уникальной конструкции как ключей, так что в большинстве случаев значение равенства будет совпадать с эталонным равенством. Например, у меня есть библиотека, я использую лично в Haskell со следующим в интерфейсе:

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

Хэш карту, как вы описали бы, вероятно, в основном, работа с ними, как ключ, но даже здесь я могу думать о это может сломаться: предположим, что пользователь хранит ключ в строгом поле некоторой структуры данных, при этом оптимизация оптимизатора «unbox-strict-fields» компилятора. Если «Uniq» - это просто оболочка newtype для целочисленного числа машин, больше не может быть объекта, к которому GC может указать и сказать «это ключ»; поэтому, когда пользователь идет и распаковывает свой ключ, чтобы использовать его, карта, возможно, уже забыла об этом.(Edit: этот конкретный пример, очевидно, можно обойти, сделать реализацию Uniq тем, что не может быть unboxed как это, дело в том, что это сложно, потому что компилятор пытается быть полезным во многих отношениях, мы могли бы не ожидайте)

TL; Я бы не сказал, что это невозможно сделать, но я подозреваю, что во многих случаях «оптимизация» либо сломается, либо будет нарушена слабой реализацией карты хэша, если не указывается идентификатор объекта первоклассный наблюдаемый статус.