Ersetze fortlaufende Duplikate

Question

Eliminiere aufeinanderfolgende Duplikate von Listenelementen.

für diese Meine Lösung ist:

compress([X,X|Xs], Q) :- 
    compress([X|Xs], Q). 
compress([X,Y|Xs], Q) :- 
    X \= Y, 
    compress([Y|Xs], QR), 
    append([X], QR, Q). 
compress([X|[]], Q) :- 
    compress([], QR), 
    append([X], QR, Q). 
compress([], []). 

Und aufgrund der Tatsache, ich bin Anfänger und ich habe keine Erfahrung in einem logischen Paradigma ich Sie bitten, sagen, was ich verbessern kann und warum meine Lösung nicht ist so gut wie es sein kann.

Zum Beispiel, X \= Y sieht nicht gut für mich.

Answer 1

Wir beginnen mit dem Namen des Prädikats.

Warum verwenden Sie einen Imperativ, um eine Beziehung zu bezeichnen? Ein gutes Prolog-Programm ist in alle   Richtungen verwendbar, während ein Imperativ immer eine bestimmte Richtung oder eine Art der Verwendung vorschlägt. Wählen Sie daher deklarative   Name und Ziel für die Allgemeinheit und logical-purity.

Als nächstes, was über die allgemeinste query:

?- compress(Ls, Cs). 
ERROR: Out of local stack 

Nicht sehr schön! Wir erwarten, dass dies zumindest einige Antworten liefert.

Was passiert, wenn wir verwenden iterative Vertiefung:

 
?- length(Ls, _), compress(Ls, Cs). 
Ls = Cs, Cs = [] ; 
Ls = Cs, Cs = [_G841] ; 
Ls = [_G841, _G841], 
Cs = [_G841] ; 
Ls = [_G841, _G841, _G841], 
Cs = [_G841] . 

Hm! Ein paar Antworten fehlen! Was ist mit dem Fall, wo die Elemente verschiedene sind? Wie Sie bereits intuitiv erwarten, führt die Verwendung unreiner Prädikate zu solchen Effekten.

Deshalb verwenden prolog-dif, d.h. dif/2, um anzuzeigen, dass zwei verschiedene Begriffe sind. Es ist in allen   Richtungen verwendbar!

Darüber hinaus sind DCGs (dcg) oft hilfreich bei der Beschreibung von Listen.

Also insgesamt, was dazu:

 
compression([])  --> []. 
compression([L|Ls]) --> [L], compression_(Ls, L). 

compression_([], _) --> []. 
compression_([X|Xs], L) --> 
     ( { X = L }, 
      compression_(Xs, L) 
     ; { dif(X, L) }, 
      [X], 
      compression_(Xs, X) 
     ). 

Wir verwenden die Schnittstelle Prädikat phrase/2 mit der DCG zu arbeiten.

Anwendungsbeispiele:

 
?- phrase(compression(Ls), Cs). 
Ls = Cs, Cs = [] ; 
Ls = Cs, Cs = [_G815] ; 
Ls = [_G815, _G815], 
Cs = [_G815] . 

?- length(Ls, _), phrase(compression(Ls), Cs). 
Ls = Cs, Cs = [] ; 
Ls = Cs, Cs = [_G865] ; 
Ls = [_G865, _G865], 
Cs = [_G865] ; 
Ls = Cs, Cs = [_G1111, _G1114], 
dif(_G1114, _G1111) . 

es von hier an! Verbessere den Determinismus, finde einen noch besseren Namen usw.

 
?- phrase(compression([a,a,b,b,b,c,c,c,c,d]), Xs). 
Xs = [a, b, c, d]; 
false. 

Mit ; false die SWI prolog-toplevel zeigt an, dass das Ziel nicht deterministisch erfolgreich war:

Answer 2

Aufbauend auf the answer by @mat (+1), warum nicht Determiniert für Fälle wie diese verbessern.

Wir können compression_//2 verbessern, indem if_//3 — die dcg analog if_/3 mit:

 
compression_([], _) --> []. 
compression_([X|Xs], L) --> 
 if_ (X  = L,       % is this item equal to previous one? 
     compression_(Xs, L),    % yes: old "run" goes on 
     ([X], compression_(Xs, X))).  % no: new "run" starts 

Beispielabfrage:

?- phrase(compression([a,a,b,b,b,c,c,c,c,d]), Xs). 
Xs = [a, b, c, d].       % succeeds deterministically