world tutorial simbolos online hello descargar constructora company haskell

tutorial - Comparación de implementaciones de cola de prioridad en Haskell



haskell simbolos (1)

Parece que hay varias implementaciones de cola de prioridad disponibles en el mercado para Haskell. Por ejemplo, hay:

ambos parecen ser estructuras de datos de cola de prioridad pura. 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

que define estructuras de datos de montón puramente funcionales a partir de las cuales se pueden hacer colas de prioridad trivialmente. . También hay

que implementan montones combinables puramente funcionales utilizando la estructura de datos de Brodal / Okasaki, que creo que es análoga a la estructura de datos de montón binomial en terrenos funcionales no puros.

(Ah, y también hay

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

cuya función no está clara para mí, pero que parece estar relacionada con la creación de colas de prioridad adjuntas a una mónada, y que parece estar construida sobre 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ígeme 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 darme algunas palabras de sabiduría cuando decida entre la vergüenza de la riqueza proporcionada por hackage. Específicamente:

  1. Supongamos que quiero hacer funciones, aparte de las operaciones tradicionales de insertar cola y extraer-min, 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 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 los lectores futuros).
  3. ¿Hay algún otro paquete de cola de prioridad por ahí que me perdí?

Hay una gran cantidad de implementaciones de cola de prioridad que se encuentran en hackage, solo para completar su lista:

De esos, descubrí que PSQueue tiene una interfaz especialmente agradable. Supongo que fue una de las primeras implementaciones y está muy bien cubierto en este artículo 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 MonadReader ( número 16 ) de Louis Wassermann (quien también escribió el paquete http://hackage.haskell.org/package/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 algunos elementos internos de la cola de prioridad, 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 )

Genial implementación ... 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 puntos de referencia de implementaciones de cola de prioridad se pueden encontrar here y en un thread bastante interesante en haskell.org here .