Comparación de implementaciones de cola de prioridad en Haskell

Question

Parece haber varias implementaciones de cola de prioridad disponibles para Haskell. Por ejemplo, hay:

• Data.PriorityQueue.FingerTree (en fingertree-0.0.1.0 en hackage)
• Data.PurePriorityQueue (en pure-priority-queue-0.14 en hackage)

ambos de los cuales parece ser pura cola de prioridad de los datos estructuras. El primero se basa en árboles de dedo, una estructura de datos con la que no estoy familiarizado; el último es un contenedor alrededor de Data.Map. También hay

• Data.Heap (de heap-1.0.0 en hackage)

que define estructuras datos montón puramente funcional de la que uno trivialmente puede hacer colas de prioridad. . También hay

• Data.Heap (en heaps-0.2 en hackage)
• Data.MeldableHeap (en meldable-heap-2.0.3 en hackage)

la que tanto implementar montones meldable puramente funcionales utilizando los datos Brodal/Okasaki estructura, que creo que es análoga a la estructura de datos de montón binomial en tierra funcional no pura.

(Ah, y también hay

• Data.PriorityQueue (en prioridad-cola-0.2.2 en hackage)

cuya función es claro para mí, pero que parece estar relacionado crear colas de prioridad adjuntas a una mónada, y que parece construirse encima de Data.Map de todos modos. En esta pregunta, me preocupan las colas de prioridad puramente funcionales, así que creo que el paquete priority-queue-0.2.2 es irrelevante . ¡Pero corríjame si estoy equivocado!)

Necesito una estructura de datos de cola de prioridad pura y funcional para un proyecto que estoy construyendo. Me preguntaba si alguien podría dar algunas palabras de sabiduría cuando decida entre el embarrassment of riches proporcionado por hackage. Específicamente:

1. Supongamos que quiero hacer funciones aparte de las operaciones tradicionales de inserción de cola y extracción-mínimo, en una presentación puramente funcional/inmutable. ¿Cuáles son los pros y los contras de los paquetes mencionados anteriormente? ¿Alguien tiene experiencia en usar cualquiera de ellos 'enojado'? ¿Cuáles son las compensaciones en el rendimiento? ¿Confiabilidad? ¿Cuáles son usados ​​más ampliamente por otros? (Usar esos puede hacer que mi código sea más fácil de leer para otros, ya que es más probable que estén familiarizados con la biblioteca). ¿Hay alguna otra cosa que deba saber antes de tomar una decisión entre ellos?
2. Si también quiero una fusión eficiente de las colas de prioridad, ¿entonces qué? (No lo hago para este proyecto, pero pensé en agregar esto pero haría que la pregunta SO sea más útil para futuros lectores.)
3. ¿Hay algún otro paquete de cola de prioridad por ahí que me haya perdido?

Answer 1

Hay una gran cantidad de implementaciones de cola de prioridad que debe conocer en hackage, sólo para completar su lista:

• http://hackage.haskell.org/package/PSQueue
• http://hackage.haskell.org/package/pqueue
• http://hackage.haskell.org/package/queuelike
• http://hackage.haskell.org/package/priority-queue
• http://hackage.haskell.org/package/pure-priority-queue
• http://hackage.haskell.org/package/fingertree-psqueue

De aquellos que encontré, PSQueue tiene una interfaz especialmente agradable. Supongo que fue una de las primeras implementaciones y está muy bien cubierto en this paper por Ralf Hinze. Puede que no sea la implementación más eficiente y completa, pero hasta ahora ha cumplido todas mis necesidades.

Hay un artículo muy bueno en el MonadReader (issue 16) de Louis Wassermann (que también escribió el paquete pqueue). En su artículo, Louis ofrece una variedad de implementaciones de colas de prioridad diferentes y también incluye complejidades algorítmicas para cada una.
Como un ejemplo sorprendente de la simplicidad de algunas colas de prioridad interna, incluye algunas pequeñas implementaciones geniales. Mi favorito (tomado de su artículo):

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

(+++) :: Ord a => SkewHeap a -> SkewHeap a -> SkewHeap a 
heap1@(SkewNode x1 l1 r1) +++ heap2@(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) 

poca implementación fresca ... un breve ejemplo de uso:

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

Algunos referentes de las implementaciones de cola de prioridad se puede encontrar here y de una forma bastante interesante thread en haskell.org here.