Name that set operation!

sets.clj

; I'm hoping to find a common name for a particular operation over sets that I've
; been thinking of as a "join" of sorts.
; 
; It's _not_ a relational join -- the values involved aren't relations (for me
; at the moment, they're actually graphs essentially representing
; disjoint recursive sets, but I think that's probably irrelevant
; detail) -- but it feels like it's in the spirit of a full outer join
;
;     Given N sets, recursively produce all unions of those sets that are disjoint.
;
; Does this operation have a name?

(defn- all-pairs [xs]
  (when-let [next (next xs)]
    (concat
     (map list (repeat (first xs)) next)
     (all-pairs next))))

(defn disjoint? [s1 s2]
  (empty? (clojure.set/intersection s1 s2)))

(defn join [sets]
  (let [new (->> (all-pairs sets)
                 (filter (partial apply disjoint?))
                 (map (partial apply clojure.set/union))
                 set)]
    (clojure.set/union
     sets
     (if (seq new)
       (join new)
       new))))

user> (join #{#{:a :b} #{:a :c}
              #{:d :e} #{:d :f}})
#{#{:c :d :f :a} #{:b :a} #{:c :a} #{:d :f} #{:e :d} #{:b :d :f :a} #{:e :c :d :a} #{:e :b :d :a}}
; just for readability's sake
user> (doseq [x (map (partial apply sorted-set) *1)]
        (println x))
#{:a :c :d :f}
#{:a :b}
#{:a :c}
#{:d :f}
#{:d :e}
#{:a :b :d :f}
#{:a :c :d :e}
#{:a :b :d :e}

If it's a product (like outer join) then join : {X} -> X, but that's not really what we're seeing since it's more like join : X -> X. I agree with @crisptrutski that it's more of a closure-like operator. But that isn't quite the right idea either since we expect closure to be idempotent, join . join = join, but that's not true

user=> (join #{#{1 2} #{3 4} #{5 6}})
#{#{4 3} #{4 6 3 5} #{1 4 3 2} #{6 5} #{1 6 2 5} #{1 2}}
user=> (join (join #{#{1 2} #{3 4} #{5 6}}))
#{#{4 3} #{4 6 3 5} #{1 4 3 2} #{1 4 6 3 2 5} #{6 5} #{1 6 2 5} #{1 2}}

But this might just be a bug in join? Do you actually mean it to be

(defn join1 [sets]
  (->> (all-pairs sets)
       (filter (partial apply disjoint?))
       (map (partial apply clojure.set/union))
       set
       (clojure.set/union sets))

iterated until stable? That's clearly a closure operation if it ever stabilizes. Does it necessarily stabilize? Yes, since it clearly adds no more elements than (->> sets all-pairs (map #(apply union %)) set (union sets)) which just "completes the union/contains lattice" and it's easy to prove termination.

So if my fix is right then you could say it's the closure under "non-touching unions".