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

Question

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

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

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

Answer 1

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

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

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

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

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

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

Answer 2

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

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

РЕДАКТИРОВАТЬ (на основе комментариев): я понимаю, какое поведение вы хотите, но вы не можете пройти этот тест скарта, которая выпускает объекты:

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