Сравнение реализаций очереди приоритетов в Haskell

Кажется, что существует несколько версий очередей приоритетов, доступных для Haskell. Например, есть:

Data.PriorityQueue.FingerTree(в fingertree-0.0.1.0 в хакете)
Data.PurePriorityQueue(в pure-priority-queue-0.14 в хакете)

оба из них представляют собой структуры данных с чистой приоритетной очередью. Первый основан на пальцах, структуре данных, с которыми я незнакома; последний является оберткой вокруг Data.Map. Там также

Data.Heap(в heap-1.0.0 для взлома)

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

Data.Heap(в heaps-0.2 для взлома)
Data.MeldableHeap(в meldable-heap-2.0.3 о взломе)

которые оба реализуют чисто функциональные смежные кучи, используя структуру данных Бродала/Окасаки, которая, как я полагаю, аналогична структуре данных биномиальной кучи на нечистых функциональных землях.

(Oh, и там также

Data.PriorityQueue(в очереди с приоритетом-0.2.2 на хаке)

чья функция для меня непонятна, но которая, по-видимому, связана с приоритетными очередями построения, прикрепленными к монаде, и которая, похоже, построена поверх Data.Map так или иначе. В этом вопросе я занимаюсь чисто функциональными очередями приоритетов, поэтому я считаю, что пакет priority-queue-0.2.2 не имеет значения. Но исправьте меня, если я ошибаюсь!)

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

Предположим, что я хочу использовать функции, отличные от традиционных вложений очереди приоритетов и операций извлечения-мин, в чисто функциональном/неизменяемом представлении. Каковы преимущества и недостатки упомянутых выше пакетов? Кто-нибудь имеет опыт использования любого из них "в гневе"? Каковы компромиссы в производительности? Надежность? Которые более широко используются другими? (Использование этих функций может облегчить чтение кода другим пользователям, поскольку они будут более знакомы с библиотекой.) Есть ли какие-либо другие вещи, которые я должен знать, прежде чем принимать решение между ними?
Если я также хочу эффективно слить очереди приоритетов, что тогда? (Я не для этого проекта, но я думал добавить это, но сделает вопрос SO более полезным для будущих читателей.)
Существуют ли какие-либо другие пакеты очереди приоритетов, которые я пропустил?

Ответ 1

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

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

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

data SkewHeap a = Empty | SkewNode a (SkewHeap a) (SkewHeap a) deriving (Show)

(+++) :: Ord a => SkewHeap a -> SkewHeap a -> SkewHeap a
[email protected](SkewNode x1 l1 r1) +++ [email protected](SkewNode x2 l2 r2) 
  | x1 <= x2    = SkewNode x1 (heap2 +++ r1) l1 
  | otherwise = SkewNode x2 (heap1 +++ r2) l2
Empty +++ heap = heap
heap +++ Empty = heap

extractMin Empty = Nothing
extractMin (SkewNode x l r ) = Just (x , l +++ r )

Прохладная небольшая реализация... пример короткого использования:

test = foldl (\acc x->acc +++ x) Empty nodes
  where nodes = map (\x-> SkewNode x Empty Empty) [3,5,1,9,7,2]

Некоторые этапы реализации приоритетных очередей можно найти здесь и в довольно интересном thread на haskell.org здесь.