Skip to content

Instantly share code, notes, and snippets.

@viebel
Forked from cemerick/sets.clj
Last active October 27, 2016 06:49
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save viebel/9416c96b4caf11c58b0c186a67b552d9 to your computer and use it in GitHub Desktop.
Save viebel/9416c96b4caf11c58b0c186a67b552d9 to your computer and use it in GitHub Desktop.
Name that set operation!
; 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))))
(join #{#{:a :b} #{:a :c}
#{:d :e} #{:d :f}})
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment