Lazy implementation of the sieve of Eratosthenes

lazy-sieve.clj

(defn vector-comparator [a b]
  "Orders vectors by the first element which differs"
  (loop [v1 a v2 b]
    (let [comparison (compare (first v1) (first v2))]
      (cond (and (empty? v1) (empty? v2)) 0
            (empty? v1) -1
            (empty? v2) 1
            (not= 0 comparison) comparison
            :else (recur (rest v1) (rest v2))))))

(defn replace-sorted-set [orig-set replacement-map]
  "Replaces items in a given set according to the replacement map by using conj and disj
   instead of 'replace' so that sort order is maintained"
  (loop [result-set orig-set my-keys (keys replacement-map)]
    (if (empty? my-keys) result-set
        (recur (conj (disj result-set (first my-keys)) (get replacement-map (first my-keys)))
               (rest my-keys)))))

(defn lazy-sieve
  "Returns a lazy sequence of primes using the sieve of Eratosthenes."
  ; Rather than precomputing the "crossed-out" multiples of each new
  ; prime found up to a predetermined upper limit, we simply carry forward
  ; a priority queue of the next crossed-out composites to ignore and the prime
  ; from which each is generated. The composites are incremented as the candidate
  ; number passes them.
  ([] 
    (cons 2 (lazy-sieve 3 (sorted-set-by vector-comparator [4 2]))))
  ([candidate composites] ; sorted set of [next-composite prime]
    (let [next-composite (ffirst composites)
          stale-composites (fn [n coll] (take-while #(<= (first %) n) coll))
          ; Takes a vector of [composite prime] and increments the composite by prime
          gen-update (fn [v] (hash-map v (vector (reduce + v) (second v))))
          ; Takes the current composite and our set of known composites and returns a
          ; map of current composites to their updated value
          replacement-map (fn [n coll] 
                            (reduce merge (map gen-update (stale-composites n coll))))
          ; n is a composite, so increment our collection of known composites past it
          inc-composites (fn [n coll] 
                           (replace-sorted-set coll (replacement-map n coll)))]
      (if (< candidate next-composite)
        (lazy-seq
          (cons candidate (lazy-sieve (inc candidate) (conj composites [(+ candidate candidate) candidate]))))
        (lazy-sieve (inc candidate) (inc-composites candidate composites))))))