Die Umkehrung einer Liste in Prolog

Ich habe fertig, eine Hausaufgabe für meine Programmierung Klasse. Ich sollte erstellen Sie ein Prolog-Programm, das kehrt eine Liste. Ich bin jedoch Probleme zu verstehen, warum genau es funktioniert.

%1. reverse a list
%[a,b,c]->[c,b,a]

%reverse(list, rev_List).
reverse([],[]).  %reverse of empty is empty - base case
reverse([H|T], RevList):-
    reverse(T, RevT), conc(RevT, [H], RevList).  %concatenation

Was genau ist RevT in diesem Fall? Ich weiß es darstellen soll, das Gegenteil von T oder den rest der gegebenen Liste, aber ich weiß nicht, wie es könnte jeder beliebige Wert, da ich noch nicht zugewiesen, es nichts. Sie tut nur dem gleichen Zweck dienen wie RevList aber für jeden rekursiven Aufruf?

Auch, warum ich [H] statt nur H in meinem conc () - Funktion aufrufen? Nicht H beziehen sich auf den Kopf der Liste (ex: [H])? Oder ist es einfach beziehen sich auf das Element am Kopf der Liste (nur H)?

Hilfe bitte deaktivieren Sie dieses, für mich. Ich habe Schwierigkeiten zu verstehen, die Logik hinter dieser Art der Programmierung.

hilfreiche links: learnprolognow.org/... und csupomona.edu/~jrfisher/www/prolog_tutorial/2_7.html
Ich begann auch die Umsetzung meiner eigenen Rückseite/2 mit dem Prolog 🙂

InformationsquelleAutor Jared | 2013-10-19

16

Ihre Lösung erklärt:
Wenn wir Umgekehrt die leere Liste, erhalten wir die leere Liste.
Bei Umkehrung die Liste [H|T] , den wir am Ende mit der Liste gewonnen durch Umkehrung T und die Verkettung mit [H] .
Zu sehen, dass die recursive-Klausel korrekt ist, sollten Sie die Liste [a,b,c,d] . Wenn wir rückwärts den Schwanz der Liste, die wir erhalten, [d,c,b] . Verketten dieses mit [a] ergibt sich [d,c,b,a] , die ist die umkehrfunktion von [a,b,c,d]

Anderen reverse Lösung:
```
 reverse([],Z,Z).

 reverse([H|T],Z,Acc) :- reverse(T,Z,[H|Acc]).
```
nennen:
```
?- reverse([a,b,c],X,[]).
```
Für weitere Informationen Lesen Sie bitte: http://www.learnprolognow.org/lpnpage.php?pagetype=html&pageid=lpn-htmlse25
- Vielen Dank für diese Antwort, es hat mir wirklich geholfen. Ich habe eine Frage: was ist der Z-variable verwendet?
- Z ist das Ergebnis.
InformationsquelleAutor Cornel Marian
7

Prolog-Listen sind einfache Datenstrukturen: ./2
- Die leere Liste ist der atom [].
- Eine Liste von einem element, [a] ist eigentlich dieser Struktur: .(a,[]).
- Eine Liste aus zwei Elementen, [a,b] ist eigentlich diese Struktur: .(a,.(b,[]))
- Eine Liste mit drei Elementen, die [a,b,c] ist eigentlich diese Struktur: .(a,.(b,.(c,[])))
- und so weiter.
Die eckige Klammer notation ist syntaktischen Zucker ersparen Sie verbringen Ihr Leben Klammern eingeben. Nicht zu vergessen, dass es einfacher auf die Augen.

Aus dieser erhalten wir den Begriff der Kopf von der Liste (das datum in der äußersten ./2 Struktur) und die Schwanz der Liste (Teilliste enthaltenen äußersten ./2 Datenstruktur.

Dies ist im wesentlichen, die gleiche Daten-Struktur, die Sie sehen, für eine klassische einfach-verkettete Liste in C:
```
struct list_node
{
  char payload ;
  struct list_node *next ;
}
```
wo die next Zeiger ist entweder NULL oder eine andere Verzeichnis-Struktur.

So, dass wir die einfachen [naiv] Umsetzung von reverse/2:
```
reverse( [] , []    ) .  % the empty list is already reversed.
reverse[ [X] , [X]  ) .  % a list of 1 item is already reversed. This special case is, strictly speaking, optional, as it will be handled by the general case.
reverse( [X|Xs] , R ) :- % The general case, a list of length >= 1 , is reversed by
  reverse(Xs,T) ,        % - reversing its tail, and
  append( T , [X] , R )  % - appending its head to the now-reversed tail
  .                      %
```
Diese gleichen Algorithmus für die Umkehrung eine einfach-verkettete Liste in eine konventionelle Programmiersprache.

Dieser Algorithmus ist jedoch nicht sehr effizient: es weist O(n²) Verhalten, für den Anfang. Es ist auch nicht tail-rekursiv, was bedeutet, dass eine Liste von ausreichender Länge bewirkt, dass ein stack-überlauf.

Sollte man beachten, dass zum Anhängen eines Elements an eine prolog-Liste erfordert das Durchlaufen der gesamten Liste, voranstellt, ist eine triviale operation, aufgrund der Struktur eines prolog-Liste. Wir können das anfügen eines Elements an eine bestehende Liste so einfach wie:
```
prepend( X , Xs , [X|Xs] ) .
```
Einem gemeinsamen idiom in prolog ist die Verwendung eines Arbeiter Prädikat mit einer Akku. Dies macht die reverse/2 Umsetzung sehr viel effizienter und (vielleicht) ein wenig leichter zu verstehen. Hier kehren wir die Liste durch setzen unsere Akkumulator, wie eine leere Liste. Wir iterieren über die Liste "Quelle". Wie begegnen wir Element in der Liste Quelle die wir voranzustellen, um die umgekehrte Liste, wodurch die umgekehrte Liste, wie wir gehen.
```
reverse(Xs,Ys) :-            % to reverse a list of any length, simply invoke the
  reverse_worker(Xs,[],Ys) . % worker predicate with the accumulator seeded as the empty list

reverse_worker( []     , R , R     ).    % if the list is empty, the accumulator contains the reversed list
reverse_worker( [X|Xs] , T , R     ) :-  % if the list is non-empty, we reverse the list
  reverse_worker( Xs , [X|T] , R )       % by recursing down with the head of the list prepended to the accumulator
  .
```
Jetzt haben Sie eine reverse/2 Umsetzung läuft in O(n) Zeit. Es ist auch tail-rekursiv, was bedeutet, dass es kann eine Liste von beliebiger Länge, ohne Blasen seinen stack.

InformationsquelleAutor Nicholas Carey
2

Erwägen Sie die Verwendung einer DCG statt, die ist viel einfacher zu verstehen:
```
reverse([])     --> [].
reverse([L|Ls]) --> reverse(Ls), [L].
```
Beispiel:
```
?- phrase(reverse([a,b,c]), Ls).
Ls = [c, b, a].
```
- Was ist eine DCG? Ich verstehe nicht die Abkürzung.
- Siehe die DCG-tag Beschreibung für weitere Informationen und die dcg - tag für Fragen und Antworten!
- "Erwägen Sie die Verwendung einer DCG statt, die ist viel einfacher zu verstehen" --- die DCG ist schwer zu verstehen, keine Verwendung vorgibt, sonst .
- funktioniert gut mit reverse([a,b,c],Q] aber! nicht-Terminierung mit reverse(P,[a,b,c])
InformationsquelleAutor mat
1

Was genau ist RevT in diesem Fall? Ich weiß es darstellen soll, das Gegenteil von T oder den rest der gegebenen Liste, aber ich weiß nicht, wie es könnte jeder beliebige Wert, da ich noch nicht zugewiesen, es nichts. Sie tut nur dem gleichen Zweck dienen wie RevList aber für jeden rekursiven Aufruf?

Variablen in Prolog sind 'Platzhalter' für die Beziehungen' Argumente. Was wir wissen, nach einem erfolgreichen Aufruf ist es genau, dass die angegebenen Argumente halten Sie für , dass Beziehung.

Dann RevT einen Wert haben wird, wenn der Aufruf erfolgreich ist. Insbesondere das Letzte argument des Aufrufs conc(RevT, [H], RevList), wenn die Liste ist nicht leer. Andernfalls wird die leere Liste.

Auch, warum ich [H] statt nur H in meinem conc () - Funktion aufrufen? Nicht H beziehen sich auf den Kopf der Liste (ex: [H])? Oder ist es einfach beziehen sich auf das Element am Kopf der Liste (nur H)?

Ja, H bezieht sich auf die erste Element (in der Regel genannt element) von der Liste, dann müssen wir 'Umformen', dass es eine Liste (nur 1 element), wie erforderlich, durch conc/3, das ist ein ganz anderes Verhältnis zu Listen.

InformationsquelleAutor CapelliC
1

Nur ein Hinweis auf testen reverse/2 Prädikat Definitionen, zu lang und passt einen Kommentar.

Umkehrung einer Liste ist die "Hallo Welt" - Beispiel für die Einführung von QuickCheck, was bedeutet, dass Sie können es verwenden, für die Unterstützung bei der Prüfung Ihrer definition. Zunächst definieren wir eine Eigenschaft das gilt für die reverse/2 Prädikat: umdrehen einer Liste zweimal geben müssen, die auf der ursprünglichen Liste, die wir übersetzen:
```
same_list(List) :-
    reverse(List, Reverse),
    reverse(Reverse, ReverseReverse),
    List == ReverseReverse.
```
Verwendung von Logtalk ist lgtunit tool QuickCheck Umsetzung:
```
% first argument bound:
| ?- lgtunit::quick_check(same_list(+list)).
% 100 random tests passed
yes

% both arguments unbound
| ?- lgtunit::quick_check(same_list(-list)).
% 100 random tests passed
yes
```
Oder einfach:
```
% either bound or unbound first argument:
| ?- lgtunit::quick_check(same_list(?list)).
% 100 random tests passed
yes
```
Aber wir brauchen eine andere Eigenschaft-definition zu testen, mit dem zweiten argument gebunden:
```
same_list_2(Reverse) :-
    reverse(List, Reverse),
    reverse(List, ListReverse),
    Reverse == ListReverse.
```
Können wir jetzt tun:
```
% second argument bound:
| ?- lgtunit::quick_check(same_list_2(+list)).
% 100 random tests passed
yes
```
Aber beachten Sie, dass diese Eigenschaft-basiert/randomisierte Tests prüfen nicht für die nicht-terminierende Fällen, da diese nur auftreten, wenn die backtracking nach der ersten Lösung.

InformationsquelleAutor Paulo Moura

Folgenden ist die typische Implementierung von reverse/2 .
Es hat jedoch das problem, wie markiert Balg mit "nicht-Kündigung" .

?- ['/dev/tty'] .

reverse(_source_,_target_) :-
reverse(_source_,_target_,[])  .

reverse([],_target_,_target_)  .

reverse([_car_|_cdr_],_target_,_collect_) :-
reverse(_cdr_,_target_,[_car_|_collect_])  .

end_of_file.

?- reverse([],Q) .
Q = []

?- reverse([a],Q) .
Q = [a]

?- reverse([a,b],Q) .
Q = [b,a]

?- reverse([a,b,c],Q) .
Q = [c,b,a]

?- reverse(P,[]) .
P = [] ? ;
%% non-termination ! %%
^CAction (h for help): a

?- reverse(P,[a]) .
P = [a] ? ;
%% non-termination ! %%
^CAction (h for help): a

?- reverse(P,[a,b]) .
P = [b,a] ? ;
%% non-termination ! %%
^CAction (h for help): a

?- reverse(P,[a,b,c]) .
P = [c,b,a] ? ;
%% non-termination ! %%
^CAction (h for help): a

InformationsquelleAutor Kintalken

-1

:- op(2'1,'fy','#') .
:- op(2'1,'fy','##') .
:- op(2'1,'fy','###') .

'reverse/2' .

/*
Im folgenden ist eine Implementierung von reverse/2
dass ich nur erfunden, die nicht darunter leiden
aus einer nicht-Kündigung problem für reverse(P,[]) .
*/

'Umsetzung' .

    reverse(_source_,_target_) :-
    reverse(_source_,_target_,_source_,_target_,[],[]) .

    reverse(_source_,_target_,[],[],_target_,_source_)  .

    reverse(_source_,_target_,[_source_car_|_source_cdr_],[_target_car_|_target_cdr_],_source_collect_,_target_collect_) :-
    reverse(_source_,_target_,_source_cdr_,_target_cdr_,[_source_car_|_source_collect_],[_target_car_|_target_collect_])  .

'testen' .

"- Tests : Teil 1' .

    /*
    ?- reverse([],Q) .
    Q = []

    ?- reverse([a],Q) .
    Q = [a]

    ?- reverse([a,b],Q) .
    Q = [b,a]

    ?- reverse([a,b,c],Q) .
    Q = [c,b,a]

"- Tests : Teil 2' .

    /*
    ?- reverse(P,[]) .
    P = []

    ?- reverse(P,[a]) .
    P = [a]

    ?- reverse(P,[a,b]) .
    P = [b,a]

    ?- reverse(P,[a,b,c]) .
    P = [c,b,a]
    */

"Prüfung : Teil 3' .

    /*
    ?- reverse(P,Q) .
    P = Q = [] ? ;
    P = Q = [_A] ? ;
    P = [_A,_B],
    Q = [_B,_A] ? ;
    P = [_A,_B,_C],
    Q = [_C,_B,_A] ? ;
    P = [_A,_B,_C,_D],
    Q = [_D,_C,_B,_A] ? ;
    P = [_A,_B,_C,_D,_E],
    Q = [_E,_D,_C,_B,_A] ? ;
    P = [_A,_B,_C,_D,_E,_F],
    Q = [_F,_E,_D,_C,_B,_A] ? ;
    P = [_A,_B,_C,_D,_E,_F,_G],
    Q = [_G,_F,_E,_D,_C,_B,_A] ? ;
    P = [_A,_B,_C,_D,_E,_F,_G,_H],
    Q = [_H,_G,_F,_E,_D,_C,_B,_A] ? ;
    P = [_A,_B,_C,_D,_E,_F,_G,_H,_I],
    Q = [_I,_H,_G,_F,_E,_D,_C,_B,_A] ? ;
    P = [_A,_B,_C,_D,_E,_F,_G,_H,_I,_J],
    Q = [_J,_I,_H,_G,_F,_E,_D,_C,_B,_A] ? ;
    P = [_A,_B,_C,_D,_E,_F,_G,_H,_I,_J,_K],
    Q = [_K,_J,_I,_H,_G,_F,_E,_D,_C,_B,_A] ? ;
    P = [_A,_B,_C,_D,_E,_F,_G,_H,_I,_J,_K,_L],
    Q = [_L,_K,_J,_I,_H,_G,_F,_E,_D,_C,_B,_A] ? ;
    P = [_A,_B,_C,_D,_E,_F,_G,_H,_I,_J,_K,_L,_M],
    Q = [_M,_L,_K,_J,_I,_H,_G,_F,_E,_D,_C,_B,_A] ? ;
    P = [_A,_B,_C,_D,_E,_F,_G,_H,_I,_J,_K,_L,_M,_N],
    Q = [_N,_M,_L,_K,_J,_I,_H,_G,_F,_E,_D,_C,_B,_A] ? ;
    P = [_A,_B,_C,_D,_E,_F,_G,_H,_I,_J,_K,_L,_M,_N,_O],
    Q = [_O,_N,_M,_L,_K,_J,_I,_H,_G,_F,_E,_D,_C,_B,_A] ? ;
    P = [_A,_B,_C,_D,_E,_F,_G,_H,_I,_J,_K,_L,_M,_N,_O,_P],
    Q = [_P,_O,_N,_M,_L,_K,_J,_I,_H,_G,_F,_E,_D,_C,_B,_A] ? ;
    P = [_A,_B,_C,_D,_E,_F,_G,_H,_I,_J,_K,_L,_M,_N,_O,_P,_Q],
    Q = [_Q,_P,_O,_N,_M,_L,_K,_J,_I,_H,_G,_F,_E,_D,_C,_B,_A] ? ;
    P = [_A,_B,_C,_D,_E,_F,_G,_H,_I,_J,_K,_L,_M,_N,_O,_P,_Q,_R],
    Q = [_R,_Q,_P,_O,_N,_M,_L,_K,_J,_I,_H,_G,_F,_E,_D,_C,_B,_A] ? ;
    P = [_A,_B,_C,_D,_E,_F,_G,_H,_I,_J,_K,_L,_M,_N,_O,_P,_Q,_R,_S],
    Q = [_S,_R,_Q,_P,_O,_N,_M,_L,_K,_J,_I,_H,_G,_F,_E,_D,_C,_B,_A] ? ;
    P = [_A,_B,_C,_D,_E,_F,_G,_H,_I,_J,_K,_L,_M,_N,_O,_P,_Q,_R,_S,_T],
    Q = [_T,_S,_R,_Q,_P,_O,_N,_M,_L,_K,_J,_I,_H,_G,_F,_E,_D,_C,_B,_A] ? ;
    P = [_A,_B,_C,_D,_E,_F,_G,_H,_I,_J,_K,_L,_M,_N,_O,_P,_Q,_R,_S,_T,_U],
    Q = [_U,_T,_S,_R,_Q,_P,_O,_N,_M,_L,_K,_J,_I,_H,_G,_F,_E,_D,_C,_B,_A] ? 
    */

InformationsquelleAutor Kintalken

Schreibe einen Kommentar

Du musst angemeldet sein, um einen Kommentar abzugeben.