Building a lazy, impure id generator

Question

I'd like to know how to create an infinite, impure sequence of unique values in Clojure.

(def generator ...) ; def, not defn
(take 4 generator) ; => (1 2 3 4)
(take 4 generator) ; => (5 6 7 8). note the generator's impurity.

I think that such a design could be more convenient than e.g. wrapping a single integer value into a reference type and increment it from its consumers, as:

• The proposed approach reduces the implementation details to a single point of change: the generator. Otherwise all the consumers would have to care about both the reference type (atom), and the concrete function that provides the next value (inc)
• Sequences can take advantage many clojure.core functions. 'Manually' building a list of ids out of an atom would be a bit bulky: (take 4 (repeatedly #(swap! _ inc)))

I couldn't come up with a working implementation. Is it possible at all?

Answer 1

You can wrap a lazy sequence around an impure class (like a java.util.concurrent.atomic.AtomicLong) to create an id sequence:

(def id-counter (java.util.concurrent.atomic.AtomicLong.))

(defn id-gen []
  (cons
   (.getAndIncrement id-counter)
   (lazy-seq
     (id-gen))))

This works, but only if you don't save the head of the sequence. If you create a var that captures the head:

(def id-seq (id-gen))

Then call it repeatedly, it will return ids from the beginning of the sequence, because you've held onto the head of the sequence:

(take 3 id-seq)
;; => (0 1 2)
(take 3 id-seq)
;; => (0 1 2)
(take 3 id-seq)
;; => (0 1 2)

If you re-create the sequence though, you'll get fresh values because of the impurity:

(take 3 (id-gen))
;; (3 4 5)
(take 3 (id-gen))
;; (6 7 8)
(take 3 (id-gen))
;; (9 10 11)

I only recommend doing the following for educational purposes (not production code), but you can create your own instance of ISeq which implements the impurity more directly:

(def custom-seq
     (reify clojure.lang.ISeq
            (first [this] (.getAndIncrement id-counter))
            (next  [this] (.getAndIncrement id-counter))
            (cons  [this thing]
                   (cons thing this))
            (more [this] (cons
                          (.getAndIncrement id-counter)
                          this))
            (count [this] (throw (RuntimeException. "count: not supported")))
            (empty [this] (throw (RuntimeException. "empty: not supported")))
            (equiv [this obj] (throw (RuntimeException. "equiv: not supported")))
            (seq   [this] this)))

(take 3 custom-seq)
;; (12 13 14)
(take 3 custom-seq)
;; (15 16 17)

Answer 2

I had a fun time discovering something during answering your question. The first thing that occured to me was that perhaps, for whatever ultimate goal you need these IDs for, the gensym function might be helpful.

Then, I thought "well hey, that seems to increment some impure counter to generate new IDs" and "well hey, what's in the source code for that?" Which led me to this:

(. clojure.lang.RT (nextID))

Which seems to do what you need. Cool! If you want to use it the way you suggest, then I would probably make it a function:

(defn generate-id []
  (. clojure.lang.RT (nextID)))

Then you can do:

user> (repeatedly 5 generate-id)
=> (372 373 374 375 376)

I haven't yet tested whether this will produce always unique values "globally"--I'm not sure about terminology, but I'm talking about when you might be using this generate-id function from within different threads, but want to still be sure that it's producing unique values.

Answer 3

this is another solution, maybe:

user=> (defn positive-numbers
          ([] (positive-numbers 1))
          ([n] (cons n (lazy-seq (positive-numbers (inc n))))))
#'user/positive-numbers
user=> (take 4 (positive-numbers))
(1 2 3 4)
user=> (take 4 (positive-numbers 5))
(5 6 7 8)