PROLOG Liste umdrehen

A

AceKiller73

0
Hab ein Problem:

Wir machen im Informatik LK jetzt Prolog.

Wir sollen ein Programm schreiben, was eine Liste umdreht dh. 1. Element als Letztes usw.

Klappt aber irgendwie nicht so wie ich will :P

Code: 
umdrehen([Kopf | Rest], L2) :-
   %append(L2, Kopf, Neu),
   Neu = [Kopf | L2],
   umdrehen(Rest, Neu).
umdrehen([], L2).

Hoffe jemand kann helfen.

MFG
Ace
 
Nunja, die Abbruchbedingung sollte im Code als erstes stehen (erspart manche unangenehme Überraschungen ;) ).

Dann der Reihe nach:
oben kommt man in das Prädikat rein,
erste Variable ist die Listenzerlegung, zweite L2 soll wohl das Ergebis zurückgeben und ist damit unbekannt (ungebunden).
Nun:
Neu = [Kopf | L2]
damit ist Neu = Verbindung von Kopf(bekannt) und L2 (unbekannt).

dann rufst du "umdrehen" wieder auf, mit (Rest=bekannt, Listenrest) und Neu(besteht aus Kopf und unbekannter Variable).

Wenn die Liste durch ist (das erste Parameter also = []) ist die Abbruchbedingung erreicht. Dann wird die zweite Variable mit der Übergabe unifiziert (ist immer möglich und daher wahr) und wieder nach oben gereicht. Als Ausgabe bekommt man korrekterweise ein "true" da die ungebundene Variable L2 im (umdrehen([],L2)) mit dem übergebenen Parameter unifiziert werden konnte ;)


Da gibt es nun mehrere Wege.
Der intuitive: man schreibt sich ein Prädikat, welches ein Element an eine Liste anhängen kann. Dann kann man diesen beim Umdrehen nutzen:
Code: 
umdrehen([H],[H]).  %Liste mit 1 element ist automatisch umgedreht
umdrehen([H|T],Result) :- umdrehen(T,Teilliste),anhängen(H,Teilliste,Result).     %drehe zuerst die restlichen Elemente um (und gib eine Teilliste zurück) und hänge dann H an die umgedrehte Teilliste - Ergebnis ist eine komplett umgedrehte Teilliste
da jeder "umdrehen" Aufruf seine Arbeit korrekt macht - also das erste Element aus der Übergebenen Teilliste an eine schon umgedrehte Ergebnisliste anhängt, gibt es am Ende auch eine komplett umgedrehte Liste zurück.

Die nicht ganz so intuivie Lösung wäre:

angenommen, "umgedreht" bekommt vom "Vateraufruf" eine zu umdrehende Teilliste, eine schon korrekt umgedrehte Teilliste und braucht nur ein Element aus der nicht umgedrehten Liste zu bearbeiten - also dieses mit der umgedrehten Liste zu verknüpfen. Dann ruft es sich selbst auf, bis das Ende erreicht ist. Prinzip:
Code: 
Hauptliste: [a,b,c,d], Teilliste: [] (da noch nichts umgedreht wurde)
             ^
             Neue Teilliste= a,[]=[a].
             
Hauptliste: [b,c,d], Teilliste: [a] (1 Element)
             ^
             neue Teilliste = b,[a]= [b,a].
             
Hauptliste: [c,d], Teilliste: [b,a] (nun schon 2)
             ^
             neue Teilliste = c,[b,a]= [b,a,c].
             
             usw.
Hauptliste: [], Teilliste: [d,c,b,a] (bisherige Teilliste)
             ^
             neue Teilliste = [],[d,c,b,a].
Hauptliste leer -> fertig, Teilliste enthält Lösung.
1.ist die Hauptliste leer, haben wir in der umgedrehten Teilliste alle Elemente und müssen sie nur "zurückreichen"
2.ist die Hauptliste nicht leer, hänge an das erste Element die "umgedrehte" Teilliste und gibt diese als neue "umgedrehte" Teilliste weiter.
3. man braucht noch irgendeine Variable um das Ergebnis zurückzureichen:

rev([],Rev,Rev). %Hauptliste leer, Rev ist unser Ergebnis, äquivalent wäre auch rev([],RevSubList,Result):-Result=RevSubList.
dann:
rev([Head|Tail],RevSubList,Result):-
rev(Tail,[Head|RevSubList],Result). % also das erste Element nehmen und zusammen mit der umgekehrten Teilliste weiterreichen.

fertig.
 
Um antworten zu können musst du eingeloggt sein.
Zurück
Oben