Prolog: Problem mit Listen

Hallo,

als Vorwarnung: bin noch noch ziemlicher Anfänger in Prolog – wahrscheinlich ist die Lösung zu meinem Problem ziemlich trivial und mit wenigen Zeilen zu machen… aber ich habe da gerade irgendwie ein ziemliches Brett vor dem Kopf.

Problem: ich habe eine „verschachtelte“ Liste von Listen (dh die „inneren“ Listen enthalten wiederum Listen als Elemente), also Bsp:

Liste= [[[1,2],[3]], [[4,5,6],[7,8]] ].

und möchte quasi die „inneren“ Listen auflösen, so dass eine „einfache“ Liste von Listen bleibt, sprich:

Liste2= [[1,2], [3], [4,5,6], [7,8] ].

Frage: wie kann ich das am besten lösen?

Danke, Paz

Hallo Paz,

mit „atomic“ kann man feststellen, ob man es mit nicht zusammengesetzten Daten zu tun hat. In diesem Fall, ob es Zahlen und keine Listen sind. Ist es so, hat man eine innere Liste gefunden (Zeile 2), sonst muss man das Prädikat mit den Elementen der Liste nochmal aufrufen (Zeile 3).

innenlisten([], []).
innenlisten([ILh|ILr], [[ILh|ILr]]) :- atomic(ILh), !.
innenlisten([Lh|Lr], Beide) :- innenlisten(Lh, LhInnen),
 innenlisten(Lr, LrInnen),
 append(LhInnen, LrInnen, Beide).

Gruß, Herodot

Ich hatte das Problem so noch nicht gehabt. Falls es sich nur um einen Liste von Listen mit Listen (einfache Schachtelung) als Elementen handelt, könnte das Folgendes vielleicht funktionieren:

  1. Leere Liste schaffen:
  2. Analog Leere Liste von Listen
  3. Klauseln , die Mitglieder der geschachtelten Liste einzeln einfügen (habe keine Vorschlag) , etwa so Es war Liste= [[[1,2],[3]], [[4,5,6],[7,8]] ].
    Es wird Liste2= [[1,2] , [3] , Mitglieder der ersten geschachtelten Liste einfügen
    und dann Liste 2=[[1,2] , [3] , [4,5,6],[7,8] Mitglieder der nächsten geschachtelten Liste anhängen usw.
    Ich bin im Moment auch sehr angespannt und kann nicht viel Zeit opfern, aber vielleicht helfen folgende Klauseln (alle selbst getestet), wobei nicht alle für dieses Problem , soweit geschildert, nötig sind:

liste([]).
liste(X):- =(X,[E|R]),liste®.
erstes([A|_],A).
kopf([A|_],[A]).
restliste([_|A],A).
mitglied(E,[E|_]).
mitglied(E,[_|Rest]):-mitglied(E,Rest).
letztes([A],A).
letztes([_|Rest],E):-letztes(Rest,E).
Falls die alte Liste gelöscht oder überschrieben werden soll, so hilft vielleicht

loesche([A|Rest],A,Neurest):-loesche(Rest,A,Neurest).
loesche([A|Rest],E,[A|Neurest]):-loesche(Rest,E,Neurest).
loesche([],_,[]).
ersetze([Alt|Rest],Alt,Neu,[Neu|Neurest]):-ersetze(Rest,Alt,Neu,Neurest).
ersetze([A|Rest],Alt,Neu,[A|Neurest]):-ersetze(Rest,Alt,Neu,Neurest).
ersetze([],_,_,[]).
vorndran(L,E,[E|L]).
vornwennneu(L,E,L):-mitglied(E,L).
vornwennneu(L,E,[E|L]).
hintendran([],Liste,Liste).
hintendran([X|Rest1],Liste2,[X|Rest3]):-hintendran(Rest1,Liste2,Rest3).

Sorry, aber ich bin seit Jahren nicht mehr in Sachen Prolog unterwegs; ich sollte das mal hier rausnehmen.

Stephan

Hi du,

brauchst du die Hilfe noch? Wenn ja.
Willst du eine Komplett Lösung oder einen Denkanstoß? Wenn es nur um den Denkanstoß geht, woran hängt es denn genau?

Hallo Paz!

Ok, ich geh zunächst mal davon aus, dass Dein Prolog-Dialekt über eine Funktion concat/3 verfügt, die zum Konkatenieren (Aneinanderhängen) von Listen dient. Also in etwa so:

  • concat([1],[2,3],X).

X = [1,2,3]

Ich geh außerdem davon aus, dass Du mit Rekursion vertraut bist.

Also ersten Schritt bauen wir ein Programm, das aus einer Liste von Listen (z.B. [[1],[2,3],[4]]) eine Liste von Einzelelementen (z.B. [[1,2,3,4]]) macht. (Wir sagen: eine _flache_ Liste.)

flat([H|T],F) :- flat(T,T1), concat(H,T1,F).
flat([],F) :- F=[].

Was hier passiert ist, dass die Liste von Listen [H|T] in zwei Bestandteile, nämlich die (flache) Liste H und die Liste von Listen T zerlegt wird. Die Liste von Listen T wird dann rekursiv zur flachen Liste T1 umgewandelt und die flachen Listen H und T1 am Ende mit concat/3 aneinandergehängt.

Natürlich müssen wir noch den Trivialfall abdecken, dass die übergebene Liste T leer ist. Dafür ist die zweite Regel zuständig.

Soll unser Programm auch mehrfach verschachtelte Listen auflösen können, brauchen wir noch eine zweite Rekursion, die auch die Liste H erstmal flach macht:

flat([H|T],F) :- flat(H,H1), flat(T,T1), concat(H1,T1,F).
flat([],[]).

Drittens ist ja in unserem Fall noch gefordert, dass die Rückgabeliste nicht selbst flach ist, sondern eine Liste von flachen Listen. Das heißt, wir brauchen noch ein zweites Prädikat, dass sich um die Liste auf der äußersten Ebene kümmert (und dem ich jetzt den einfallslosen Namen „p“ gebe).

p([H|T],R) :- flat(H,H1), p(T,T1), concat(H1,T1,R).
p([],[]).

Zusammengenommen ist es jetzt ein Vierzeiler geworden …

flat([H|T],F) :- flat(H,H1), flat(T,T1), concat(H,T1,F).
flat([],[]).
p([H|T],R) :- flat(H,H1), p(T,T1), concat(H1,T1,R).
p([],[]).

… der das gewünschte Ergebnis liefert:

  • p([[[1,2],[3]], [[4,5,6],[7,8]] ], X).

X = [[1,2], [3], [4,5,6], [7,8] ]