Earlier quoted context omitted.
cljs.user=> (source clojure.set/union) (defn union "Return a set that is the union of the input sets" ([] #{}) ([s1] s1) ([s1 s2] (if ( (source clojure.set/intersection) (defn intersection "Return a set that is the intersection of the input sets" ([s1] s1) ([s1 s2] (if (
I don't feel that I know any more now than I did before you posted this "reply". The third branch ([s1 s2]) adds the elements of the smaller collection one by one onto the larger collection. Conceptually, it does this by constructing a new copy of the result for every addition, since conj is not destructive. It is buggy and will return a result of whatever type the larger collection is, with data being duplicated if…
That's not how persistent data structures work
http://hypirion.com/musings/understanding-persistent-vector-...
> why does efficient set union of two collections require one of the two collections to support fast membership tests
I haven't thought much about this but it seems intuitively true to me. You want to take the smaller set, and add each item to the larger set if it doesn't already exist. That last part is why you need a fast membership test.
If you're still unconvinced, try loading up two similarly structured database tables with a million rows and get the union of them (with and without indices). The indexed one will be orders of magnitude quicker.