CODEWITHSUNDEEP
algorithmdata-structuresclojurequeueimmutability
mikera
mikera

Reputation: 106371

Immutable queue in Clojure

What is the best way to obtain a simple, efficient immutable queue data type in Clojure?

It only needs two operations, enqueue and dequeue with the usual semantics.

I considered lists and vectors of course, but I understand that they have comparatively poor performance (i.e. O(n) or worse) for modifications at the end and beginning respectively - so not ideal for queues!

Ideally I'd like a proper persistent data structure with O(log n) for both enqueue and dequeue operations.

Upvotes: 36

Views: 7303

Answers (3)

CurtainDog
CurtainDog

Reputation: 3205

Clojure could really benefit from a queue literal. This would be cleaner (and more portable) than relying on Java interop.

However, it's not that hard to roll your own portable persistent queue, just using ordinary household items like lists.

Consider the queue as two lists, one providing the head portion of the queue, and the other the tail. enqueue adds to the first list, dequeue pops from the latter. Most ISeq functions are trivially implemented.

Probably the only tricky part is what happens when the tail is empty and you want to dequeue. In that case the head list is reversed and becomes the new tail, and the empty list becomes the new head list. I believe, even with the overhead of the reverse, that enqueue and dequeue remain O(1), though the k is going to be higher than a vanilla vector of course.

Happy queueing!

Upvotes: 1

miner49r
miner49r

Reputation: 1107

I use the following function queue to create a PersistentQueue. Optionally, you might want to have a print-method and a data-reader if you're going to be printing and reading the queues.

The usual Clojure functions are already implemented for PersistentQueue.

  • peek -- get the head
  • pop -- returns a new PersistentQueue without the head
  • conj -- add item to the tail
  • empty? -- true if empty
  • seq -- contents as a sequence (list)

    (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])))))

Upvotes: 9

mikera
mikera

Reputation: 106371

Problem solved - solution for others who may find it helpful.

I've found that Clojure has the clojure.lang.PersistentQueue class that does what is needed.

You can create an instance like this:

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

As far as I can see, you currently need to use the Java interop to create the instance but as Michal helpfully pointed out you can use peek, pop and conj subsequently.

Upvotes: 36

Related Questions