coll-util.clj

(defn lazy-combine-sorted [xs ys]
  "lazily combines xs and ys and returns their union (assumes xs ys sorted)"
  (lazy-seq
   (if-let [[x & xs*] xs]
     (if-let [[y & ys*] ys]
       (cond (= x y) (cons x (lazy-combine-sorted xs* ys*))
             (< x y) (cons x (lazy-combine-sorted xs* ys))
             (> x y) (cons y (lazy-combine-sorted xs ys*)))
       xs) ; no more ys
     ys))) ; no more xs

(defn combine-lazy [xs ys]
  "combines xs and ys and returns their union"
  (lazy-combine-sorted (sort xs) (sort ys)))

(defn combine-sorted [xs ys]
  "combines xs and ys and returns their union (assumes xs ys sorted)"
  (loop [x+ xs y+ ys acc []]
    (let [[x & x*] x+  ;; x head, x* tail of x+
          [y & y*] y+] ;; y head, y* tail of y+
      (if (nil? x) ;; no more x? return acc + y+
        (concat acc y+) 
        (if (nil? y) ;; no more y? return acc + x+
          (concat acc x+)
          (cond (= x y) (recur x* y* (conj acc x))
                (< x y) (recur x* y+ (conj acc x))
                (> x y) (recur x+ y* (conj acc y))))))))

(defn combine [A B]
  (combine-sorted (sort A) (sort B)))