Prolog: Problem mit Listen

[Pazuzu]

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

 

[CDW]

Vornweg: ein 3 Zeiler ist zwar möglich, aber "tricky". Ein 6 Zeiler dagegen sollte recht intuitiv funktionieren
Man sollte sich im Klaren sein, dass die Schreibweise [a,b,c] nur ein "syntactic sugar" ist - intern ist eine Liste eine zusammengestelle Struktur nach diesem Muster:

101 ?- write_canonical([a,b,c]).
'.'(a, '.'(b, '.'(c, [])))
102 ?- X='.'(a,'.'(b,'.'(c,[]))).
X = [a, b, c].

http://books.google.de/books?id=w-X...&resnum=4&ved=0CCkQ6AEwAw#v=onepage&q&f=false

Daher steht von der Syntax her nur diese "Zerlegung" der Listen zur Verfügung:

103 ?- X=[1,2,3],[Head|Tail]=X.
X = [1, 2, 3],
Head = 1,
Tail = [2, 3].

104 ?- X=[[1,2,3],4,5],[Head|Tail]=X.
X = [[1, 2, 3], 4, 5],
Head = [1, 2, 3],
Tail = [4, 5].

Also immer das erste Element und Rest, wobei es keine Rolle spielt, ob das erste Element ein Atom oder etwas Zusammengesetztes ist.
----------------------

Verschachtelte Listen "entschachteln" Version 1:
Aufruf: flat(Liste, Ergebnis)
Ich gehe davon aus, dass die "übliche" Prolog Notation sowie Bezeichnungen [H|T] für Head|Tail bekannt sind.

der triviale Fall: die Liste ist leer:

flat([],[])

Ansonsten müssen wir das erste Element unserer Liste "entschachteln",
dann den Rest und beide Listen zusammenführen:

flat([],[]).
flat([H|T], Ergebnis):- flat(H,H_Flat),
                        flat(T,T_Flat),
                        append(H_Flat,T_Flat,Ergebnis).

Zum Zusammenführen nutzen wir 'append', welches bei den "großen" Prologinterpretern eigentlich dabei sein sollte (ansonsten ist es ein klassischer 2 Zeiler :wink: :

app([],X,X).
app([H|T],X,[H|Result]):- app(T,X,Result).

)

zum Schluss müssen wir noch den Fall abdecken, dass nur noch 1 Element einer (Teil)Liste übrig ist:

flat(H,[H]).

Etwas unschön:
aus 1 Element wird eine Liste mit 1 Element gebastelt - zugeständniss an "append", welches nur auf Listen angewendet werden kann.
Das sollte so schon funktionieren:

110 ?- flat([[1,2],10,[3,[[[4],8]],[5]]],X).
X = [1, 2, 10, 3, 4, 8, 5].

Nochmal der komplette Code:

flat([],[]).
flat([H|T], Ergebnis):- flat(H,H_Flat),!,
                        flat(T,T_Flat),!,
                        app(H_Flat,T_Flat,Ergebnis).
flat(H,[H]).

mit Cuts '!' (damit sagen wir, dass uns ein gültiges Ergebnis von flat Aufruf schon reicht)

Ist aber nicht unbedingt "hübsch" oder effizient.

-------------------------
Verschachtelte Lsiten "flatten" Version 2:

Anstatt stupide Listen zu erstellen und diese mit append anzuhängen, führen wir einfach eine Zwischenliste mit,
dabei sorgen wir einfach dafür, dass wir immer nur 1 entschachteltes Element mit der Zwischenliste verbinden müssen, um das gewünschte Ergebniss zu erhalten:

Sowas wie: flat2(Liste, Zwischenliste, Ergebnis).
Der Aufruf müsste dann so lauten:

flat2(Liste,[], Ergebnis)

Wir übergeben also die verschachtelte Liste und unsere Zwischenliste ist erstmal leer == []

Folgende Regeln müssen wir dann aufstellen:

Trivialer Fall:
wir haben das Ende einer verschachtelten Liste erreicht:
D.h unser Ergebnis ist die Zwischenliste

flatt([], Zwischenliste, Zwischenliste).

Ansonsten:
Unser Ergebnis ist der "entschachtelte" Rest der Liste zusammen mit dem "entschachtelten" ersten Element/Teilliste:

flat2([H|T], Zwischenliste, Ergebnis):- flat2(T, Zwischenliste, T_List),
                                        flat2(H, T_List, Ergebnis),!.

D.h zuerst "entschachteln" wir den Rest der Liste - zusammen mit der Zwischenliste haben wir ein vorläufiges Ergebnis in T_List. Dann "entschachteln" wir das erste Element - zusammen mit dem vorläufigen Ergebnis == T_List als Zwischenliste ergibt es das gewünschte Resultat - eine komplett entschachtelte Liste.

Fehl nun noch die letzte Regel:
Falls wir ein Element haben, welches in keine der beiden oberen Regeln passt, muss es wohl ein einzelnes, unverschachteltes Element sein - also ist unsere gesuchte "entschachtelte" Liste == dieses Element + vorläufige Zwischenliste

flat2(Element, Zwischenliste, [Element|Zwischenliste]).

nochmal kompletter Code mit Cuts:

flat2([], Zwischenliste, Zwischenliste):-!.
flat2([H|T], Zwischenliste, Ergebnis):- flat2(T, Zwischenliste, T_List), !,
                                        flat2(H, T_List, Ergebnis),!.
flat2(Element, Zwischenliste, [Element|Zwischenliste]).

Beispielaufruf:

69 ?- flat2([[1,4],9,[3,[5,6,[8]]]],[],X).
X = [1, 4, 9, 3, 5, 6, 8].