Cola eficiente en Haskell

Question

¿Cómo puedo implementar de manera eficiente una estructura de datos de listas donde puedo tener 2 vistas al principio y al final de la lista, que siempre apuntan a la cola una cola de una lista sin costosas llamadas a la inversa. es decir:

start x = [] 
end x = reverse start -- [] 
start1 = [1,2,3] ++ start 
end start1 -- [3,2,1] 

final debe ser capaz de hacer esto sin invocar 'inversa', sino simplemente mirar la lista dada desde la perspectiva de la lista de ser a la inversa automáticamente. Lo mismo debería ocurrir si creo nuevas listas de concatenaciones para comenzar.

Answer 1

siempre se puede simplemente usar Data.Sequence.

Una implementación bien conocida de una cola puramente funcional es usar dos listas. Uno para enqueue y otro para dequeue. Enqueue simplemente contraería la lista en cola. Dequeue toma el encabezado de la lista de dequeue. Cuando la lista de dequeue está vacía, vuelva a llenarla invirtiendo la lista en cola. Ver Purely Functional Datastructures. de Chris Okasaki

Aunque esta implementación usa reverse, el costo de tiempo amortizado de esto es insignificante asintóticamente. Funciona de modo que para cada enqueue, incurre en una deuda de tiempo de Θ (1) para la recarga de la lista de dequeue. El tiempo esperado de un dequeue es, por lo tanto, el doble que el de una secuencia. Este es un factor constante, por lo que el costo de ambas operaciones es Θ (1).

Answer 2

No soy realmente un usuario de Haskell, pero encontré a blog post que dice describir una cola Haskell que puede operarse en tiempo constante amortizado. Se basa en un diseño de las excelentes estructuras de datos puramente funcionales de Chris Okasaki.

Answer 3

¿Es Data.Dequeue lo que está buscando?

(No tiene reverse pero puede agregar muy fácilmente y enviar un parche para el autor.)