set union-operation in Prolog : Erklärung

union([H|T],[],[H|T]).     
union([],[H|T],[H|T]).    
union([H|T], SET2, RESULT) :- member(H,SET2), union(T,SET2,RESULT).    
union([H|T], SET2, [H|RESULT]) :- not(member(H,SET2)), union(T,SET2,RESULT).

Ich bin in der Lage zu verstehen, dass es ist das Durchlaufen der ersten Liste und das hinzufügen auf der Grundlage, ob das element ist ein Mitglied der 2. Liste steht oder nicht. Ich habe die Logik. Aber der workflow ist geheimnisvoll für mich, wo es fügt die Elemente der "zweiten Liste" zu dem Ergebnis, sobald die erste Liste ist erschöpft.

Könnte bitte jemand ein einfaches Beispiel, wie union([1,2], [2,3], Result), und erklären Sie den workflow.

danke für das edit.. das machte es viel mehr klar..

InformationsquelleAutor Firefox | 2012-10-16

prolog

7

Werde ich davon ausgehen, dass Sie anrufen union/3 mit dem ersten und zweiten Argumente instanziiert. Das Dritte argument kann entweder nicht instanziierten nach dem Aufruf und wird vereinigt bei Rückkehr mit der Vereinigung der beiden Listen, oder ob Sie bereits instantiiert, es kann verwendet werden, um zu überprüfen, ob es stimmt mit dem (bestellten) union der beiden ersten Listen.

Die erste Klausel besagt, dass, wenn das zweite argument die leere Liste und die erste Liste hat mindestens ein element, dann die union ist gerade diese erste Liste.
Ebenso die zweite Klausel besagt, dass, wenn das erste argument die leere Liste und in der zweiten Liste hat mindestens ein element, dann die union ist gerade diese zweite Liste.

Die Dritte Klausel eine Rekursion über die erste Liste und prüft die zweite Liste, um zu sehen, ob das Element schon da ist. In diesem Fall ist es nur ruft sich selbst mit dem Schwanz von der ersten Liste.

Vierten Klausel tests der Kopf der ersten Liste, um zu überprüfen, dass es nicht enthalten ist in der zweiten Liste und ruft rekursiv mit dem Schwanz (genau wie die Dritte Klausel). Jedoch nach der Rückkehr von der Rekursion es fügt das Element an den Kopf der Dritten Liste, so addieren sich die posten für die union.

Beachten Sie, dass in Ihrer Implementierung, die Vereinigung von zwei leeren Sätzen wird immer scheitern. Sie können dieses Problem beheben, durch das modifizieren der ersten oder zweiten Klausel zu ermöglichen, wird eine leere Liste, oder fügen Sie eine weitere Klausel für diesen Fall. E. g.
```
union([],[],[]).
```
Nun wollen wir sehen, was passiert, wenn wir rufen union([1,2],[2,3], Result):

Den ersten beiden Klauseln nicht entsprechen, da keiner von Ihnen die leere Liste.

Wir treten in die Dritte Klausel und überprüfen, um zu sehen, dass element 1 ist nicht Mitglied der zweiten Liste, so versagt es.

Versuchen wir nun die vierte Klausel an und testen das element 1, die ich nicht in der zweiten Liste, also nennen wir union([2], [2,3], Result) ist, markieren wir diese Ausführung zeigen (*1).

Wieder die beiden ersten Klauseln nicht entsprechen, so treten wir in die Dritte Klausel. Hier testen wir, dass in der Tat element 2 enthalten ist, in die zweite Liste, also nennen wir union([], [2,3], Result) ist, markieren wir diese Ausführung zeigen (*2)

Nun die erste Klausel fehl, da das erste argument die leere Liste.
Wir treten nun in die zweite Klausel verbindendes drittes argument mit der zweiten Liste ([2,3]).

An dieser Stelle kehren wir zu (*2), wo nun instanziiert mit [2,3]. Diese Klauseln zu Ende, so dass wir gebunden, das Dritte argument mit [1,2,3], und kehren wir zu (*1).

Sind wir jetzt bei (*1), wo Ergebnis und somit das Dritte argument instanziiert mit [1,2,3].

Dies gibt uns die erste Folge [1,2,3].

Jedoch eine Wahl Punkt war übrig, wenn wir succedded in (*2), so dass, wenn wir bitten Prolog die Suche nach einer anderen Antwort, es hat immer noch versuchen, die vierte Ziffer der union([2],[2,3], Ergebnis).

So tragen wir die vierte Klausel, um zu testen, ob 2 nicht Mitglied der [2,3], die fehl, so ist der Prolog wird uns sagen, dass es keine anderen Antworten.

... Lese gerade 'einmal' war es genug.. Sie sind sicherlich ein großer Lehrer. Vielen Dank 🙂

InformationsquelleAutor gusbro
1

Sind Sie nicht Inspektion SET2, also vorausgesetzt, es gibt keine Duplikate in der es, dann die Basis-Rekursion kann sein, das einzelne Prädikat
```
union([], U, U).
```
@gusbro bereits erklärt, dass, wenn H gehört nicht zu SET2 es sich in (lokalen) vor Ergebnis nach der rekursive Aufruf erfolgreich war.

Die Erklärung sollte klar Ihre Zweifel, aber bitte beachten Sie, dass not/1 im wesentlichen wiederholen Sie den gleichen test bereits durchgeführt, die in der vorherigen (erfolglosen) anrufen. Dann eine bessere code kann
```
union([H|T], SET2, RESULT) :-
   member(H,SET2), !, % note the commit
   union(T,SET2,RESULT).    
union([H|T], SET2, [H|RESULT]) :- 
   % useless now 
   % not(member(H,SET2)),
   union(T,SET2,RESULT).
```
Dies ist äquivalent zum code, vorausgesetzt member/2 side effects free (und es ist).

not/1 implementiert werden kann, mit !/0.

danke für die Antwort.. ich glaube, ich verstehe den trick-Sie waren darauf hin.. es war hilfreich, hat mir geholfen, zu verstehen, die use case '!'.. Jedoch, mit der check (zumindest auskommentiert) verbessert die Lesbarkeit..

InformationsquelleAutor CapelliC
1

In meine Antwort Antwort auf eine Frage im Zusammenhang mit "Schnittmenge und Vereinigung von 2 Listen" ich Stelle eine logisch Reine Umsetzung von intersection und union.

Im Gegensatz zu den anderen Antworten zu deiner Frage die pure Variante ist monoton und bleibt somit logisch klingen, wenn verwendet mit nicht-Boden-Bedingungen.

InformationsquelleAutor repeat

Schreibe einen Kommentar

Du musst angemeldet sein, um einen Kommentar abzugeben.