[HaBo]

Pazuzu · 13.11.10, 16:06

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:

Code:

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:

Code:

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

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

**CDW** · 15.11.10, 02:12

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:

Code:

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-Xj...page&q&f=false

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

Code:

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:

Code:

flat([],[])

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

Code:

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

:

Code:

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:

Code:

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:

Code:

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

Nochmal der komplette Code:

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:

Code:

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

Code:

flatt([], Zwischenliste, Zwischenliste).

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

Code:

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

Code:

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

nochmal kompletter Code mit Cuts:

Code:

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

Beispielaufruf:

Code:

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

Anzeige

- Anzeige -

13.11.10, 16:06	#1 (permalink)
Pazuzu Registriert seit: 13.11.10 Likes: 0	Prolog: Problem mit Listen Anzeige 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: Code: 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: Code: Liste2= [ [1,2], [3], [4,5,6], [7,8] ] Frage: wie kann ich das am besten lösen? Danke, Paz

15.11.10, 02:12	#2 (permalink)
CDW Moderator Registriert seit: 20.07.05 Likes: 202	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: Code: 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-Xj...page&q&f=false Daher steht von der Syntax her nur diese "Zerlegung" der Listen zur Verfügung: Code: 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: Code: flat([],[]) Ansonsten müssen wir das erste Element unserer Liste "entschachteln", dann den Rest und beide Listen zusammenführen: Code: 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 : Code: 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: Code: 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: Code: 110 ?- flat([[1,2],10,[3,[[[4],8]],[5]]],X). X = [1, 2, 10, 3, 4, 8, 5]. Nochmal der komplette Code: 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: Code: 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 Code: flatt([], Zwischenliste, Zwischenliste). Ansonsten: Unser Ergebnis ist der "entschachtelte" Rest der Liste zusammen mit dem "entschachtelten" ersten Element/Teilliste: Code: 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 Code: flat2(Element, Zwischenliste, [Element\|Zwischenliste]). nochmal kompletter Code mit Cuts: Code: flat2([], Zwischenliste, Zwischenliste):-!. flat2([H\|T], Zwischenliste, Ergebnis):- flat2(T, Zwischenliste, T_List), !, flat2(H, T_List, Ergebnis),!. flat2(Element, Zwischenliste, [Element\|Zwischenliste]). Beispielaufruf: Code: 69 ?- flat2([[1,4],9,[3,[5,6,[8]]]],[],X). X = [1, 4, 9, 3, 5, 6, 8]. __________________ Noch mal, für alle Pseudo-Geeks: 1+1=0. -> 10 wäre Überlauf! Selig, wer nichts zu sagen hat und trotzdem schweigt.

Themen-Optionen
Druckbare Version zeigen Jemanden per E-Mail auf dieses Thema hinweisen
Ansicht
Linear-Darstellung Zur Hybrid-Darstellung wechseln Zur Baum-Darstellung wechseln

[HaBo]

Prolog: Problem mit Listen