Sets

Alles aus Teil 2 gilt weiter, mit "Element" statt "Key":

• Offene Sets sind bekannte Elemente plus ein unbekannter Rest, (lset #{1 2} | _0). Der Rest ist so eingeschränkt, dass ihm die bekannten Elemente fehlen. Wie die Keys einer offenen Map sind die Elemente eines offenen Sets immer bekannt. Diese Einschränkung hält offene Sets billig: Sie verzweigen nie.
• Set-Literale dürfen unbekannte Elemente enthalten, und die bleiben paarweise verschieden. #{x y} ist ein Set aus zwei Elementen und scheitert, sobald x und y gleich werden, auch wenn das lange nach dem Bau des Sets passiert. Die Prüfung läuft auf dem Occurs Check mit, genau wie bei Map-Keys.
• Die Unifikation von Sets mit unbekannten Elementen verzweigt darüber, welche Elemente einander zugeordnet werden. Sie legt sich fest, wenn nur eine Zuordnung übrig ist, und wartet sonst.

(run* [s] (containso s 1) (containso s 2))
;;=> ((lset #{1 2} | _0))

(run* [x y] (== #{x y} #{1 2}))
;;=> ([1 2] [2 1])

(run* [x y] (== #{x y} #{1}))
;;=> ()

containso, lackso, conjo, disjo und lseto sind die Set-Versionen von geto, lacks-keyo, assoco, dissoco und lmapo (lseto ist die Grundform der Sets: conj von Elementen, die noch nicht drin waren), und jede läuft in jede Richtung:

(run* [s] (disjo s 1 #{2}))
;;=> (#{1 2} #{2})                ;; s had 1, or it didn't

(run* [x r] (lseto #{1 2 3} #{x} r))
;;=> ([1 #{3 2}] [3 #{1 2}] [2 #{1 3}])

Eine Frage nach Mitgliedschaft in einem offenen Set bekommt jede ehrliche Antwort, auch "irgendein Element des Rests, das ich noch nicht kenne":

(run* [x] (fresh [s] (lseto s #{1 2} (lvar)) (containso s x)))
;;=> (1 2 (_0 :- (clojure.core.logic/containso (lset #{1 2} | _1) _0) (!= (_0 1)) (!= (_0 2))))

uniono, intersectiono, differenceo, subseto und disjointo handeln, sobald eine Seite geschlossen ist, und warten sonst, wie mergeo. Rückwärts zählen sie genau die Möglichkeiten auf:

(run* [a b] (uniono a b #{1 2}))
;;=> 9 answers: each element in a, in b, or in both

(run* [a] (differenceo a #{2 3} #{1}))
;;=> (#{1 3 2} #{1 2} #{1 3} #{1})

(run* [a] (subseto a #{1 2}))
;;=> (#{1 2} #{2} #{1} #{})

Auf Sets aus einfachen Werten sind sie ein einziger clojure.set-Aufruf: Vereinigung und Schnitt zweier Sets mit je 500 Elementen dauern unter einer Millisekunde.

Set-Unifikation ist NP-vollständig (Kapur und Narendran, 1986), also lässt sich das Verzweigen über unbekannte Elemente im Allgemeinen nicht vermeiden; Teil 5 hat die Details. {log} (Dovier, Omodeo, Pontelli, Rossi) erlaubt unbekannte Elemente auch in offenen Sets und zahlt dafür mit vierfacher Verzweigung bei jeder Unifikation offener Sets und mit redundanten Antworten. Dieser Fork geht denselben Tausch ein wie bei Maps: Offene Sets haben bekannte Elemente, und die schweren Fälle bleiben auf geschlossene Literale beschränkt. Dort ist die Verzweigung eine Bijektion und liefert jede Antwort genau einmal.

(get #{1} 1) ist in Clojure 1, aber geto funktioniert nicht auf Sets. Ließe man es zu, müsste jedes geto auf einer Collection unbekannter Art auch "ein Set, das den Key enthält, mit dem Wert gleich dem Key" in Betracht ziehen. Das würde Antworten auf Maps ändern, die mit Sets nichts zu tun haben. Für Sets gibt es containso.

Generiert von Claude im Auftrag von Benjamin Schwerdtner.