Есть ли где-нибудь библиотека мемоизации, основанная на идентификаторах объектов?

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

Я знаю несколько различных готовых библиотек мемоизации для Haskell:

• Мемо-комбинаторы и пакеты памяток, которые используют красивый трюк, включающий ленивые бесконечные структуры данных, для достижения мемоизации чисто функциональным способом. (Насколько я понимаю, первое немного более гибкое, а второе проще в использовании в простых случаях: см. этот ТАК ответ для обсуждения.)
• Пакет uglymemo, который внутренне использует unsafePerformIO, но по-прежнему предоставляет ссылочно прозрачный интерфейс. Внутреннее использование unsafePerformIO приводит к более высокой производительности, чем в двух предыдущих пакетах. (В готовом виде его реализация использует структуры данных поиска на основе сравнения, а не, возможно, несколько более эффективные хэш-функции; но я думаю, что если вы найдете и замените Cmp на Hashable и Data.Map на Data.HashMap и добавите подходящие imports, вы получить версию на основе хэша.)

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

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

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

Мой вопрос: знает ли кто-нибудь о пакетной библиотеке, которая выполняет запоминания, описанные в статье Пейтон-Джонса, Марлоу и Эллиотта, заполняя все детали (и желательно также заполняя надлежащую безопасность потоков)?

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

ОБНОВЛЕНИЕ

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

data Node = Node [Node] [Annotation]

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

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

myTransform : Node -> Node

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

recursiveTransform : Node -> Node

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

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

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

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

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