Какой самый идиоматический подход к коллекциям с несколькими индексами в Haskell?

В С++ и других языках библиотеки дополнений реализуют контейнер с несколькими индексами, например. Boost.Multiindex. То есть коллекция, которая хранит один тип значения, но поддерживает несколько разных индексов над этими значениями. Эти индексы обеспечивают различные способы доступа и способы сортировки, например. map, multimap, set, multiset, array и т.д. Сложность выполнения многоиндексного контейнера обычно представляет собой сумму сложностей отдельных индексов.

Есть ли эквивалент для Haskell или люди создают свои собственные? В частности, каков наиболее идиоматический способ реализации коллекции типа T с индексом заданного типа (T - это экземпляр Ord), а также индекс типа карты (предположим, что ключевое значение типа K может быть предоставлено для каждого T либо явно, либо через функцию T -> K)?

Ответ 1

В тривиальном случае, когда каждый элемент имеет уникальный ключ, который всегда доступен, вы можете просто использовать Map и извлечь ключ для поиска элемента. В несколько менее тривиальном случае, когда каждое значение имеет только ключ, простым решением было бы что-то вроде Map K (Set T). При поиске элемента непосредственно следует сначала извлечь ключ, индексируя Map, чтобы найти набор элементов, которые разделяют этот ключ, затем просматривая тот, который вы хотите.

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

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

Интуитивно, это похоже на проблему, которая может работать лучше не как одна реализация, а скорее набор примитивов, которые могут быть составлены более гибко, чем Data.Map позволяет создавать специальные специализированные структуры. Но это не очень полезно для краткосрочных потребностей.

Ответ 2

Я только что загрузил IxSet для взлома сегодня утром,

http://hackage.haskell.org/package/ixset

ixset предоставляет множества, которые имеют несколько индексов.

ixset уже давно существует как happstack-ixset. Эта версия удаляет зависимости от чего-либо конкретного случая, и является новой официальной версией IxSet.

Другим вариантом будет kdtree:

darcs get http://darcs.monoid.at/kdtree

kdtree стремится улучшить IxSet, предлагая большую безопасность типов и лучшее время и пространство. Текущая версия, похоже, преуспевает во всех трех аспектах - но она еще не готова к прайм-тайм. Дополнительные участники будут очень приветствоваться.

Ответ 3

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

Ответ 4

Я считаю, что самый простой способ сделать это - просто с Data.Map. Хотя он предназначен для использования отдельных индексов, когда вы вставляете один и тот же элемент несколько раз, большинство компиляторов (разумеется, GHC) заставят значения размещаться на одном месте. Отдельная реализация мультимапа не будет такой эффективной, поскольку вы хотите найти элементы на основе их индекса, поэтому вы не можете наивно связать каждый элемент с несколькими индексами - скажем [([key], value)] - поскольку это было бы очень неэффективно.

Однако я не рассматривал реализации Boost Multimaps, чтобы увидеть, окончательно, если есть оптимизированный способ сделать это.

Ответ 5

У меня проблема? И T, и K имеют порядок. Существует функциональный ключ:: T → K, но он не сохраняет порядок. Желательно управлять набором Ts, индексированным (для быстрого доступа) как по порядку T, так и по порядку K. В более общем плане, может потребоваться коллекция элементов T, проиндексированных кучей заказов key1:: T → K1,.. keyn:: T → Kn, и так получилось, что здесь key1 = id. Это фотография?

Я думаю, что согласен с предложением gereeter о том, что основой для решения является просто синхронизация связки (Map K1 T,.. Map Kn T). Вставка пары ключ-значение в карте не дублирует ни ключ, ни значение, выделяя только дополнительную кучу, необходимую для создания новой записи в нужном месте в индексе. Вставка одного и того же значения, с соответствующим ключом, в несколько индексов не должна нарушать общий доступ (даже если одним из ключей является значение). Стоит обернуть структуру в API, который гарантирует, что любые последующие изменения значения вычисляются один раз и разделяются, а не пересчитываются для каждой записи в индексе.

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