merge seqs of Comparable objects (possibly removing duplicates)

merge-seqs.clj

(defn merge-seqs
  "Merges sorted seqs of Comparable objects as in merge sort. Uses
  left-to-right precedence order among the input seqs when duplicates
  are present. Uses clojure.core/compare."
  ([xs ys]
     (lazy-seq
      (if (or (empty? xs) (empty? ys))
        (concat xs ys)
        (let [x (first xs)
              y (first ys)]
          (condp == (compare y x)
              0 (cons x (cons y (merge-seqs (rest xs) (rest ys))))
              1 (cons x (merge-seqs (rest xs) ys))
              (cons y (merge-seqs xs        (rest ys))))))))
  ([xs ys & zss]
     (reduce merge-seqs
             (merge-seqs xs ys)
             zss)))

(defn merge-seqs-nub
  "Merges sorted seqs of Comparable objects while removing duplicates
  from the output. Uses clojure.core/compare."
  ([xs ys]
     (lazy-seq
      (if (or (empty? xs) (empty? ys))
        (concat xs ys)
        (let [x (first xs)
              y (first ys)]
          (condp == (compare y x)
              0 (cons x (merge-seqs (rest xs) (rest ys)))
              1 (cons x (merge-seqs (rest xs) ys))
              (cons y (merge-seqs xs        (rest ys))))))))
  ([xs ys & zss]
     (reduce merge-seqs
             (merge-seqs xs ys)
             zss)))

;;; or DRYer

(defn- nub-runs [xs]
  (lazy-seq
   (cond (empty? xs) xs
         (empty? (rest xs)) xs
         (zero? (compare (first xs) (second xs))) (nub-runs (rest xs))
         :else (cons (first xs) (nub-runs (rest xs))))))

(defn merge-seqs-nub [& seqs]
  (nub-runs (apply merge-seqs seqs)))

(comment
  (take 15 (apply merge-seqs-nub (map (fn [n] (iterate #(+ % n) 0)) [3 5 7])))
  ;; => (0 3 5 6 7 9 10 12 14 15 18 20 21 24 25)
)