Существует ли где-то библиотека хранения memoization на основе объектов, основанная на объектах?

Я знаю, что memoization, кажется, является постоянной проблемой здесь, в теге haskell при переполнении стека, но я думаю, что этот вопрос не задавался раньше.

Я знаю несколько разных библиотек memoization для "Hackell":

Компоненты memo-combinators и memotrie, которые используют красивый трюк с ленивыми бесконечными структурами данных для достижения memoization чисто функциональным способом. (Как я понимаю, первый немного более гибкий, в то время как последний проще использовать в простых случаях: см. этот SO ответ для обсуждения.)
Пакет uglymemo, который использует небезопасныйPerformIO внутри, но все же представляет собой ссылочно прозрачный интерфейс. Использование unsafePerformIO внутренне приводит к лучшей производительности, чем предыдущие два пакета. (Вне полки его реализация использует структуры данных поиска на основе сравнения, а не, возможно, несколько более эффективные хэш-функции, но я думаю, что если вы найдете и замените Cmp для Hashable и Data.Map для Data.HashMap и добавьте Appropraite import s, вы получите версию на основе хэша.)

Однако я не знаю ни одной библиотеки, которая будет отвечать на запросы, основанные на идентификаторе объекта, а не на значении объекта. Это может быть важно, потому что иногда типы объектов, которые используются в качестве ключей к вашей таблице заметок (то есть, как ввод функции, которая сохраняется в память), могут быть большими - настолько большими, чтобы полностью изучить объект, чтобы определить, "Я видел это раньше, это сама медленная операция. Медленный, а также ненужный, если вы снова и снова будете применять memoized функцию к объекту, который хранится в данном" месте в памяти "1. (Это может произойти, например, если мы memoizing функцию, которая называется рекурсивно над некоторой большой структурой данных с большим количеством структурного обмена.) Если мы уже вычислили нашу memoized функцию на этом конкретном объекте раньше, мы можем уже знаю ответ, даже не глядя на сам объект!

Реализация такой библиотеки memoization включает в себя несколько тонких проблем, и для правильного выполнения этого требуется несколько специальных частей поддержки от языка. К счастью, GHC предоставляет все специальные функции, которые нам нужны, и есть бумага от Пейтона-Джонса, Марлоу и Эллиота, которые в основном беспокоят большинство этих вопросов для вас, объясняя, как построить прочную реализацию. Они не предоставляют всех подробностей, но они приближаются.

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

Мой вопрос: кто-нибудь знает о упакованной библиотеке, которая делает вид memoization, обсуждаемый в бумаге Peyton-Jones, Marlow и Elliott, заполняя все детали (и предпочтительно заполняя надлежащую безопасность потоков)?

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

UPDATE

Следующее предложение @luqui ниже, здесь немного больше данных о конкретной проблеме, с которой я сталкиваюсь. Предположим, что существует тип:

data Node = Node [Node] [Annotation]

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

У меня есть функция

myTransform : Node -> Node

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

recursiveTransform : Node -> Node

результат которого выглядит так же, как структура данных, как вы бы это сделали:

recursiveTransform Node originalChildren annotations = 
   myTransform Node recursivelyTransformedChildren annotations
   where
     recursivelyTransformedChildren = map recursiveTransform originalChildren

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

Я понимаю, что все это было бы проще, если бы сказали, что Nodes были пронумерованы до того, как я их получил, иначе я мог бы изменить определение Node. Я не могу (легко) сделать любую из этих вещей.

Меня также интересует общий вопрос о существовании библиотеки, реализующей функциональность, о которой я упоминаю, совершенно независимо от конкретной конкретной проблемы, с которой я сталкиваюсь прямо сейчас: я чувствую, что мне пришлось работать над такой проблемой на несколько раз, и было бы неплохо убить дракона раз и навсегда. Тот факт, что SPJ и соавт. Считали, что для GHC нельзя добавить ни одну, ни три функции для поддержки существования библиотек этой формы, предполагает, что эта функция действительно полезна и не может быть использована во всех случаях. (НО мне все равно очень хотелось бы услышать об обходных решениях, которые помогут в этом конкретном случае: долгосрочная проблема не такая срочная, как проблема, с которой я сталкиваюсь прямо сейчас:-))

1 Технически я не совсем понимаю местоположение в памяти, поскольку сборщик мусора иногда перемещает объекты вокруг бит --- что я действительно имею в виду "идентичность объекта". Но мы можем думать об этом как о том же, что и наше интуитивное представление о местоположении в памяти.

Ответ 1

Если вы хотите только memoize на основе идентификации объекта, а не равенства, вы можете просто использовать существующие механизмы лени, встроенные в язык.

Например, если у вас есть структура данных, подобная этой

data Foo = Foo { ... }
expensive :: Foo -> Bar

то вы можете просто добавить значение, которое будет запомнено как дополнительное поле, и пусть лень позаботится о вас для остальных.

data Foo = Foo { ..., memo :: Bar }

Чтобы упростить использование, добавьте интеллектуальный конструктор, чтобы связать узел.

makeFoo ... = let foo = Foo { ..., memo = expensive foo } in foo

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

Ответ 2

Кажется, что stable-memo будет именно тем, что вам нужно (хотя я не уверен, что он может обрабатывать несколько потоков):

В то время как большинство памятных комбинаторов memoize на основе равенства, stable-memo делает это на основе того, был ли тот же самый аргумент передан функции раньше (то есть, тот же аргумент в памяти).

stable-memo оценивает только ключи WHNF.

Это может быть более подходящим для рекурсивных функций над графами с циклами.

stable-memo не сохраняет ключи, которые он видел до сих пор, что позволяет им собирать мусор, если они больше не будут использоваться. Финализаторы устанавливаются на место, чтобы удалить соответствующие записи из таблицы заметок, если это произойдет.

Data.StableMemo.Weak предоставляет альтернативный набор комбинаторов, который также позволяет не сохранять результаты функции, а только повторно использовать результаты, если они еще не были собраны мусором.

В аргументе функции нет ограничения типа класса.
stable-memo не будет работать для аргументов, которые имеют одинаковое значение, но не являются одним и тем же объектом кучи. Это исключает многих кандидатов для memoization, таких как наиболее распространенный пример, наивная реализация Фибоначчи, чей домен является машинным Ints; его все же можно заставить работать для некоторых областей, например, таких как ленивые натуры.

Ответ 3

Ekmett только что загрузил библиотеку, которая обрабатывает это и многое другое (производится в HacPhi): http://hackage.haskell.org/package/intern. Он уверяет меня, что это безопасный поток.

Изменить: На самом деле, строго говоря, я понимаю, что это делает что-то совсем другое. Но я думаю, вы можете использовать его для своих целей. Это больше похоже на библиотеку интернинга типа stringtable-atom, которая работает над произвольными структурами данных (включая рекурсивные). Он использует WeakPtrs внутри, чтобы поддерживать таблицу. Тем не менее, он использует Int для индексации значений, чтобы избежать проверок структурных равенств, что означает их упаковку в тип данных, когда то, что вы хотите, по-видимому, фактически StableName s. Поэтому я понимаю, что это отвечает на связанный с этим вопрос, но требует изменения вашего типа данных, которого вы хотите избежать...