-
-
Save viebel/9416c96b4caf11c58b0c186a67b552d9 to your computer and use it in GitHub Desktop.
Name that set operation!
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
; 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