anders/2 - existiert eine reine, bestimmte Definition?

Question

different(Xs, Ys) :- 
    member(X, Xs), 
    non_member(X, Ys). 
different(Xs, Ys) :- 
    member(Y, Ys), 
    non_member(Y, Xs). 

Während diese Definition member/2 und non_member/2 ist fast perfekt aus einer deklarativen Sicht verwendet wird, erzeugt es redundante Lösungen für bestimmte Abfragen und Blätter, die alle um Wahl Punkte.

Was eine Definition, die (in einer reinen Weise wahrscheinlich if_/3 und (=)/3 verwendet) auf diese verbessert, so dass genau den gleichen Satz von Lösungen von different/2 beschrieben wird, ist aber zumindest für Boden Abfragen bestimmt (also keine nutzlosen nicht verlassen Wahl Punkte offen) und (wenn möglich) jede überflüssige Antwort weglässt?

---

_{Tatsächlich gelingt es different([a|nonlist],[]), different([],[b|nonlist]). Es könnte ebenso scheitern. Eine Lösung, die für beide fehlschlägt, ist in Ordnung (vielleicht sogar feiner).}

Answer 1

Nehmen wir es an die Grenze --- mit Hilfe von list_nonmember_t/3, exists_in_t/3 und or_/2!

some_absent_t(Xs,Ys,Truth) :- 
    exists_in_t(list_nonmember_t(Ys),Xs,Truth). 

different(Xs,Ys) :- 
    or_(some_absent_t(Xs,Ys), 
     some_absent_t(Ys,Xs)). 

Answer 2

Erster Versuch!

Der folgende Code basiert auf den Meta-Prädikaten tfilter/3 und tpartition/4, die monotone if-then-else-Steuer if_/3 konstruieren, das verdinglichte einstellige logische Verknüpfung not_t/3 und der verdinglichten Begriff Gleichheitsprädikat (=)/3:

different([],[_|_]). 
different([X|Xs0],Ys0) :- 
    tpartition(=(X),Ys0,Es,Ys1), 
    if_(Es=[], true, (tfilter(not_t(=(X)),Xs0,Xs1),different(Xs1,Ys1))). 

Beispielabfrage:

?- different([A,B],[X,Y]). 
       A=Y ,   dif(B,Y),  X=Y 
;  A=X   ,  B=X   , dif(X,Y) 
;  A=X   , dif(B,X), dif(B,Y), dif(X,Y) 
;    A=Y ,    B=Y , dif(X,Y) 
;    A=Y , dif(B,X), dif(B,Y), dif(X,Y) 
; dif(A,X), dif(A,Y). 

Lassen Sie uns Determinismus beobachten, wenn sie mit Bodendaten arbeiten:

?- different([5,4],[1,2]). 
true. 

Der obige Ansatz fühlt sich an wie ein Schritt in die richtige Richtung ... Aber, wie es ist, würde ich es nicht perfekt nennen.

Answer 3

Hier ist ein weiterer Versuch! Wir verwenden das monotone if-then-else-Steuerelementkonstrukt if_/3 in Kombination mit dem Prädikat der erstatteten Listenmitgliedschaft und der Indexierung des ersten Arguments, um die Erzeugung nutzloser Auswahlpunkte zu vermeiden.

different(Xs,Ys) :- 
    different_aux(Xs,Ys,Xs,Ys). 

different_aux([],[_|_],Xs0,Ys0) :- 
    different_aux(Ys0,[],Ys0,Xs0).  % swap Xs/Ys pair 
different_aux([X|Xs],Ys,Xs0,Ys0) :- 
    if_(memberd_t(X,Ys0), 
     different_aux(Ys,Xs,Ys0,Xs0), % variant: different_aux(Xs,Ys,Xs0,Ys0) 
     true). 

Zuerst führen wir eine Abfrage, die wir erwarten, zum Scheitern verurteilt:

?- different([1,2,3],[2,3,1]). 
false. 

Die folgenden Abfragen sind ähnlich wie die fehlerhafte Abfrage oben angegeben; jeder hat einen einzigen „anders“ Artikel x an verschiedenen Indizes in der ersten [1,2,3] oder der zweiten Liste platziert [2,3,1]:

 
?- different([4,2,3],[2,3,1]), different([1,2,3],[4,3,1]), 
    different([1,4,3],[2,3,1]), different([1,2,3],[2,4,1]), 
    different([1,2,4],[2,3,1]), different([1,2,3],[2,3,4]). 
true.         % all subgoals succeed deterministically 

OK! Lassen Sie uns einen anderen laufen (ganz allgemein) Abfrage, die ich in meinem verwendet previous answer:

?- different([A,B],[X,Y]). 
     A=X ,    B=X , dif(Y,X) 
;  A=X ,   dif(B,X), dif(Y,B) 
;    A=Y , dif(B,X), dif(Y,X) 
; dif(A,X), dif(A,Y). 

Compact! Eine große Verbesserung gegenüber dem, was ich präsentierte earlier!

Answer 4

Zurück zu den Wurzeln! Diese Variante ist sehr nahe zu dem Code von der OP in der Frage gegeben.

Die folgenden Angaben basieren auf if_/3 und memberd_t/3.

different(Xs,Ys) :- 
    if_(some_absent_t(Xs,Ys), 
     true, 
     some_absent_t(Ys,Xs,true)). 

some_absent_t([] ,_ ,false). 
some_absent_t([X|Xs],Ys,Truth) :- 
    if_(memberd_t(X,Ys), some_absent_t(Xs,Ys,Truth), Truth=true). 

Hier ist eine Boden-Abfrage:

 
?- different([4,2,3],[2,3,1]), different([1,2,3],[4,3,1]), 
    different([1,4,3],[2,3,1]), different([1,2,3],[2,4,1]), 
    different([1,2,4],[2,3,1]), different([1,2,3],[2,3,4]). 
true.         % all subgoals succeed deterministically 

Und hier ist die (allgemeinere) Abfrage, die ich in früheren Antworten verwendet:

?- different([A,B],[X,Y]). 
     A=X ,    B=X ,   dif(Y,X) 
;  A=X ,   dif(B,X), dif(B,Y) 
;    A=Y ,    B=Y , dif(Y,X), dif(Y,X) 
;    A=Y , dif(B,X), dif(B,Y), dif(Y,X) 
; dif(A,X), dif(A,Y). 

Answer 5

(Much von @ wiederholen inspiriert last answer, die Namen sind immer noch zu plump)

different(Xs, Ys) :- 
    if_(tnotexists_inlist_t(list_memberd_t(Ys), Xs), 
     true, 
     tnotexists_inlist_t(list_memberd_t(Xs), Ys)). 

tnotexists_inlist_t(_P_2, [], false). 
tnotexists_inlist_t(P_2, [E|Es], T) :- 
    if_(call(P_2, E), 
     tnotexists_inlist_t(P_2, Es, T), 
     T = true). 

Answer 6

Nächster Kandidat für den Code Schönheitswettbewerb! -)

Diese Antwort zeigt eine refaktorierte Variante des Codes, der in a previous answer angezeigt wird. Es verwendet verdinglichten Konjunktion und Disjunktion:

and_(P_1,Q_1) :- 
    and_t(P_1,Q_1,true). 

or_(P_1,Q_1) :- 
    or_t(P_1,Q_1,true). 

and_t(P_1,Q_1,Truth) :- 
    if_(P_1, call(Q_1,Truth), Truth=false). 

or_t(P_1,Q_1,Truth) :- 
    if_(P_1, Truth=true, call(Q_1,Truth)). 

Beachten Sie die zwei Versionen für beide „und“ und „oder“; diejenigen mit dem Suffix _t haben ein zusätzliches Argument für den Wahrheitswert, diejenigen ohne das Suffix nicht und nehmen an, dass Truth=true gelten soll.

Basierend auf and_t/3 und auf verdinglichten Begriff Ungleichheit Prädikat dif/3 definieren wir nonmember_t/3:

nonmember_t(X,Ys,Truth) :- 
    list_nonmember_t(Ys,X,Truth). 

list_nonmember_t([] ,_, true). 
list_nonmember_t([Y|Ys],X,Truth) :- 
    and_t(dif(X,Y), list_nonmember_t(Ys,X), Truth). 

Jetzt wollen wir some_absent_t/3 definieren, different_t/3 und different/2, etwa so:

 
some_absent_t([] ,_ ,false). 
some_absent_t([X|Xs],Ys,Truth) :- 
    or_t(nonmember_t(X,Ys), some_absent_t(Xs,Ys), Truth). 

different_t(Xs,Ys,Truth) :- 
    or_t(some_absent_t(Xs,Ys), 
     some_absent_t(Ys,Xs), 
     Truth). 

different(Xs,Ys) :- 
    different_t(Xs,Ys,true). 

Ist es noch run?

 
?- different([A,B],[X,Y]). 
     A=X ,    B=X ,   dif(Y,X) 
;  A=X ,   dif(B,X), dif(B,Y) 
;    A=Y ,    B=Y , dif(Y,X), dif(Y,X) 
;    A=Y , dif(B,X), dif(B,Y), dif(Y,X) 
; dif(A,X), dif(A,Y).      % same result as before 

?- different([4,2,3],[2,3,1]), different([1,2,3],[4,3,1]), 
    different([1,4,3],[2,3,1]), different([1,2,3],[2,4,1]), 
    different([1,2,4],[2,3,1]), different([1,2,3],[2,3,4]). 
true.         % same result as before 

Sieht in Ordnung!

Alles in allem keine große Verbesserung gegenüber bestehenden Antworten, aber IMO etwas besser lesbaren Code und eine verdinglichte Version von different/2 als zusätzlichen Bonus!

Answer 7

Die folgende fett Bounty (+500) vor nicht allzu langer Zeit angeboten wurde:

^{Eine idiomatische Antwort noch fehlt hier. Zum Beispiel sollte or_t/3 eher (;)/3 sein. Da ist mehr dran.}

Herausforderung angenommen! Diese Antwort ist eine Folge zu this previous answer.

1. Wir verwenden die verdinglichte logische Verknüpfung (;)/3, die wie folgt definiert werden kann:

    
   ';'(P_1,Q_1,T) :- if_(P_1, T=true, call(Q_1,T)). 
   

2. Als nächstes definieren wir die meta-predicatecall_/1. Es ist nützlich mit verdinglichten Prädikaten, die in dieser Antwort verwendet werden. Mit seinem Namen und seiner Semantik folgt call_/1if_/3, and_/2 und or_/2!

    
   call_(P_1) :- call(P_1,true). 
   

3. Mit (;)/3, call_/1 und some_absent_t/3 wir different/2 implementieren:

    
   different(As,Bs) :- call_((some_absent_t(As,Bs) ; some_absent_t(Bs,As))). 
   

Fertig! Das ist es.

---

Lassen Sie uns die Abfragen, die wir in vorherigen Antworten verwendet haben, erneut ausführen!

?- different([5,4],[1,2]). 
true. 

?- different([1,2,3],[2,3,1]). 
false. 

?- different([4,2,3],[2,3,1]), different([1,4,3],[2,3,1]), different([1,2,4],[2,3,1]), 
    different([1,2,3],[4,3,1]), different([1,2,3],[2,4,1]), different([1,2,3],[2,3,4]). 
true. 

Gleiche Abfragen gleiche Antworten ... Sehen in Ordnung mir!

Answer 8

Conerning Lösungen, die if_ verwenden, würde ich einen alternativen Ansatz wäre konstruktive Negation von Anfang an zu verwenden. Constructive negation wurde bereits in den 80er Jahren erforscht, ein Pionier war David Chan, und taucht immer noch von Zeit zu Zeit auf.

Angenommen, wir haben einen Prolog-Interpreter mit einer konstruktiven Negation (~)/2. Diese konstruktive Negation (~)/2 kann verwendet werden, um eine deklarative zu definieren if-then-else wie folgt, diesen Operator (~->)/2 nennen wir:

(A ~-> B; C) :- (A, B); (~A, C). 

Wenn der Prolog-Interpreter (=>)/2 neben konstruktiven Negation Implikation auch eingebettet ist, könnte man alternativ ein definieren deklarative if-then-else wie folgt, lässt diesen Operator rufen (~=>)/2:

(A ~=> B; C) :- (A => B), (~A => C). 

Hinweis der Wechsel von disjunction (;)/2 zur Verbindung (,)/2. Fragen Sie die BDD-Leute (Binary Decision Diagram), warum sie logisch gleichwertig sind. Verfahrensweise gibt es Nuancen, aber durch die Hintertür der eingebetteten Implikation für bestimmte A wird die zweite Wenn-Dann-sonst-Variante auch Nicht-Determiniertheit einführen.

Aber wie gehen wir vor und führen zum Beispiel konstruktive Negation in einem Prolog-Interpreter ein. Ein direkter Weg wäre, die konstruktive Negation an einen Constraint Solver zu delegieren. Wenn der Constraint-Solver Negation verdinglichten hat, kann dies wie folgt geschehen:

~ A :- #\ A. 

Aber es nicht so viele Constraint Solver um, dass eine sinnvolle Verwendung für Beispiele wie member/2 etc erlauben würde .. Da oft bieten sie verdinglicht Negation nur für Bereiche wie endliche ganze Zahlen, Rationale, etc ..Aber für ein Prädikat wie member/2 würden wir eine verklärte Negation für das Herbrand-Universum benötigen.

Beachten Sie auch, dass die üblichen Ansätze für eine konstruktive Negation auch davon ausgehen, dass die gewöhnliche Regelimplikation einen anderen Messwert erhält. Dies bedeutet, dass in der Regel unter konstruktiver Negation, wir die gewöhnliche member/2 Definition holen konnten, und Abfrage-Ergebnisse wie erhalten:

?- ~ member(X, [a,b,c]). 
dif(X, a), 
dif(X, b), 
dif(X, c). 

Aber auch hier die verdinglichte Negation kaum leicht arbeiten mit definierten Prädikaten, so dass die folgende Abfrage wird wahrscheinlich nicht:

?- #\ member(X, [a,b,c]). 
/* typically won't work */ 

wenn die oben als eine der deklarativen gelingt if-then-else wie (~->)/2 oder (~=>)/2 weniger häufige Verwendung haben wird, da gewöhnliche Prädikat Definitionen bereits deklarative Interpretation durch die Prolog-Interpreter liefern. Aber warum ist die konstruktive Negation nicht weit verbreitet? Ein Grund könnte der große Gestaltungsraum eines solchen Prolog-Interpreters sein. Ich habe bemerkt, dass wir die folgenden Möglichkeiten:

Rückwärts Chaining: Wir würden im Grunde die Vanille-Interpreter spucken solve/1 in zwei Prädikate solvep/1 und solven/1. solvep/1 ist verantwortlich für die Lösung positiver Ziele und solven/1 ist verantwortlich für die Lösung negativer Ziele. Wenn wir dies versuchen, werden wir früher oder später sehen, dass wir eine sorgfältigere Behandlung von Quantifizierern benötigen und wahrscheinlich mit einer Quantifizierer-Eliminierungsmethode für die Herbrand-Domäne enden.

Forward Chaining: Wir werden auch bemerken, dass bei der Rückwärtsverkettung Probleme für die Modellierung von Klauseln mit Disjunktion oder existentiellem Quantor im Kopf auftreten werden. Das hat damit zu tun, dass der für Prolog geeignete Sequenzkalkül nur eine Formel auf der rechten Seite hat. Entweder gehen wir auf der rechten Seite zur Multi-Formel und verlieren die Parakonsistenz, oder wir verwenden die Vorwärts-Verkettung.

Magische Sets: Aber Vorwärtsverkettung wird die Lösungsräume unkontrolliert polieren. Wir brauchen also vielleicht eine Kombination aus Vorwärts- und Rückwärtsverkettung. Ich meine damit nicht nur, dass wir in der Lage sein sollten, dynamisch zwischen den beiden während des Lösungsprozesses zu wechseln, aber ich meine, dass wir auch ein Mittel benötigen, Sätze zu generieren, die den Vorwärtsverkettungsprozess steuern.

Weitere Probleme werden auch in dieser Antwort here notiert. Dies bedeutet nicht, dass früher oder später eine Formel gefunden wird, die alle diese Probleme und Lösungspaare zusammenpasst, aber es könnte noch etwas länger dauern.

Bye