sorted-intersection-with, O(n+m)

gistfile1.clj

(defn sorted-intersection-with [f m1 m2]
  (assert (= (.comparator m1) (.comparator m2)))
  (let [cmpr (.comparator m1)]
    (loop [m1 (seq m1), m2 (seq m2), ret (transient {})]
      (if-not (and m1 m2)
        (persistent! ret)
        (let [[[k1 v1]] m1
              [[k2 v2]] m2
              c (.compare cmpr k1 k2)]
          (cond
            (zero? c) (recur (next m1) (next m2) (assoc! ret k1 (f v1 v2)))
            (neg? c)  (recur (next m1) m2 ret)
            :else     (recur m1 (next m2) ret)))))))

(let [a (sorted-map :a 1 :c 3 :e 5)
      b (sorted-map :a 1 :b 2 :d 4 :e 5)]
  (sorted-intersection-with + a b))