Сравнение реализаций очереди приоритетов в Haskell
Похоже, что для Haskell есть несколько готовых реализаций очереди с приоритетом. Например, там:
- Data.PriorityQueue.FingerTree (в fingertree-0.0.1.0 при взломе)
- Data.PurePriorityQueue (в pure-priority-queue-0.14 on hackage)
, оба из которых выглядят как структуры данных очереди с чистым приоритетом. Первый основан на деревьях пальцев, структуре данных, с которой я не знаком; последний - оболочка вокруг Data.Map. Также существует
- Data.Heap (в heap-1.0.0 при взломе)
, который определяет чисто функциональные структуры данных кучи, из которых можно тривиально создавать очереди приоритетов. . Также есть
- Data.Heap (в heaps-0.2 при взломе)
- Data.MeldableHeap (в meldable-heap-2.0.3 при взломе)
, которые реализуют чисто функциональные объединяемые кучи с использованием структуры данных Бродала / Окасаки, которая, как я полагаю, аналогична биномиальной структуре данных кучи в нечистом функциональном мире.
(О, и есть также
- Data.PriorityQueue (в priority-queue-0.2.2 при взломе)
, функция которого мне непонятна, но который, похоже, связан с построением очередей приоритетов, прикрепленных к монаде , и который, похоже, так или иначе построен поверх Data.Map. В этом вопросе меня интересуют чисто функциональные очереди приоритетов, поэтому я считаю, что пакет priority-queue-0.2.2 не имеет значения. Но поправьте меня, если я ' m неверно!)
Мне нужна чисто функциональная структура данных очереди приоритетов для проекта, который я создаю. Мне было интересно, может ли кто-нибудь дать какие-то мудрые слова, когда я выбираю между позором богатства , полученным путем взлома. В частности:
- Предположим, мне нужны функции, отличные от традиционных операций вставки и извлечения очереди в приоритетную очередь, в чисто функциональном / неизменяемом представлении. Каковы плюсы и минусы упомянутых выше пакетов? Есть ли у кого-нибудь опыт использования любого из них «в гневе»? Каковы компромиссы в производительности? Надежность? Какие из них более широко используются другими? (Их использование может облегчить чтение моего кода другим людям, поскольку они с большей вероятностью будут знакомы с библиотекой.) Есть ли еще какие-то вещи, которые я должен знать, прежде чем принимать решение между ними?
- Если я также хочу эффективного слияния приоритетных очередей, что тогда? (Я не участвую в этом проекте, но я подумал, что добавлю это, но это сделает вопрос SO более полезным для будущих читателей.)
- Есть ли какие-нибудь другие пакеты очереди с приоритетом, которые я пропустил?