Coda immutabile in Clojure

Question

Qual è il modo migliore per ottenere un tipo di dati di coda immutabile semplice ed efficiente in Clojure?

Ha solo bisogno di due operazioni, accodare e deselezionare con la solita semantica.

Ho considerato liste e vettori ovviamente, ma capisco che hanno prestazioni relativamente scarse (cioè O (n) o peggio) per le modifiche alla fine e all'inizio rispettivamente - quindi non sono l'ideale per le code!

Idealmente mi piacerebbe una struttura adeguata di dati persistente con O (log n) sia per accodamento e le operazioni dequeue.

Answer 1

Problema risolto: soluzione per gli altri che potrebbero trovare utile.

ho scoperto che Clojure ha la classe clojure.lang.PersistentQueue che fa ciò che è necessario.

È possibile creare un'istanza in questo modo:

(def x (atom clojure.lang.PersistentQueue/EMPTY)) 

Per quanto posso vedere, è attualmente necessario utilizzare il Java interoperabilità per creare l'istanza, ma come Michal utilmente sottolineato è possibile utilizzare peek, pop e conj successivamente.

Answer 2

Io uso la seguente funzione queue per creare un PersistentQueue. Opzionalmente, potresti voler avere un metodo di stampa e un lettore di dati se stai per stampare e leggere le code.

Le solite funzioni Clojure sono già implementate per PersistentQueue.

• peek - ottenere la testa
• pop - restituisce un nuovo PersistentQueue senza la testa
• conj - aggiungere elemento alla coda
• vuoto? - vero se vuote
• ss - contenuti come una sequenza (lista)

    (defn queue 
     ([] clojure.lang.PersistentQueue/EMPTY) 
     ([coll] (reduce conj clojure.lang.PersistentQueue/EMPTY coll))) 

    (defmethod print-method clojure.lang.PersistentQueue 
     [q ^java.io.Writer w] 
     (.write w "#queue ") 
     (print-method (sequence q) w)) 

    (comment 
     (let [*data-readers* {'queue #'queue}] 
     (read-string (pr-str (queue [1 2 3]))))) 

Answer 3

Clojure potrebbe davvero beneficiare di una coda letterale. Questo sarebbe più pulito (e più portabile) di quello basato sull'interoperabilità di Java.

Tuttavia, non è così difficile da rotolare il proprio coda permanente portatile, usando solo oggetti per la casa comune come liste.

consideri coda come due liste, una fornendo la porzione di testa della coda, e l'altra la coda. enqueue aggiunge al primo elenco, dequeue pop da quest'ultimo. La maggior parte delle funzioni ISeq sono implementate banalmente.

Probabilmente l'unica parte difficile è ciò che accade quando la coda è vuota e si desidera dequeue. In tal caso l'elenco principale è reverse d e diventa la nuova coda e la lista vuota diventa la nuova lista principale. Credo che, anche con l'overhead di reverse, che enqueue e dequeue rimangano O(1), anche se lo k sarà superiore a un vettore di vaniglia, naturalmente.

Happy queue ing!