Efficiente coda in Haskell

Question

Come posso implementare in modo efficiente una struttura di dati dell'elenco in cui posso avere 2 viste alla testa e alla fine dell'elenco, che puntano sempre a una coda di una lista senza chiamate costose da invertire. cioè:

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

finale dovrebbe essere in grado di farlo senza invocare 'inverso', ma semplicemente guardando la lista data dal punto di vista della lista sia in senso inverso automaticamente. Lo stesso dovrebbe valere se creo nuovi elenchi dalle concatenazioni per iniziare.

Answer 1

Si può sempre usare appena Data.Sequence.

Un'implementazione ben nota di una coda puramente funzionale consiste nell'utilizzare due elenchi. Uno per l'accodamento e l'altro per la rimozione. Enqueue sarebbe semplicemente contro con l'elenco di accodamento. Dequeue prende la testa dell'elenco di dequeue. Quando l'elenco di dequotazione è vuoto, riempirlo invertendo la lista di accodamento. Vedi Chris Okasaki's Purely Functional Datastructures.

Anche se questa implementazione utilizza reverse, il costo di ammortamento di questo è insignificante in modo asintotico. Funziona in modo che per ogni acconto, si incorre in un debito di tempo di Θ (1) per la ricarica della lista di dequeue. Il tempo atteso di una coda di attesa è quindi il doppio di un accodamento. Questo è un fattore costante, quindi il costo di entrambe le operazioni è Θ (1).

Answer 2

Non sono realmente un utente Haskell, ma ho trovato a blog post che dichiara di descrivere una coda Haskell che può essere utilizzata in tempo costante ammortizzato. Si basa su un progetto dell'ottima struttura dati puramente funzionale di Chris Okasaki.

Answer 3

Is Data.Dequeue Cosa stai cercando?

(Non deve reverse ma è possibile aggiungerlo abbastanza facilmente e inviare una patch per l'autore.)