EMZETT.
Login

Emzett Wiki

Prolog: Listen und rekursive Strukturen

Properties1
tagsprogrammiersprachen, prolog

4 Min. Lesezeit

Kurz: Eine Liste ist entweder leer [] oder [Kopf|Rest]:

Teil des Kurses Prolog

Kapitel 3 von 8 im Kurs Prolog. Mit Fortschritt, Quiz und Zertifikat auf der Lernseite.

Listen und Kopf|Rest

Eine Liste ist entweder leer [] oder [Kopf|Rest]:

main :-
    L = [1, 2, 3, 4, 5],
    L = [Kopf|Rest], writeln(Kopf), writeln(Rest),
    length(L, N), writeln(N),
    nth0(0, L, E0), nth1(1, L, E1), writeln(E0-E1),
    last(L, Letztes), writeln(Letztes),
    reverse(L, R), writeln(R),
    append([1, 2], [3], A), writeln(A),
    msort([c, a, b, a], M), writeln(M),
    sort([c, a, b, a], S), writeln(S),
    sort(0, @>=, [3, 1, 2, 3], Absteigend), writeln(Absteigend),
    sumlist(L, Summe), writeln(Summe),
    max_list(L, Max), min_list(L, Min), writeln(Min-Max),
    numlist(1, 5, NL), writeln(NL),
    sum_list([1.5, 2.5], FS), writeln(FS).

Ausgabe:

1
[2,3,4,5]
5
1-1
5
[5,4,3,2,1]
[1,2,3]
[a,a,b,c]
[a,b,c]
[3,3,2,1]
15
1-5
[1,2,3,4,5]
4.0

member, append und select: rückwärts nutzbar

Prolog-Prädikate sind relational: Dasselbe Prädikat prüft, erzeugt oder zerlegt.

main :-
    ( member(2, [1, 2, 3]) -> writeln('2 ist enthalten') ; true ),
    findall(X, member(X, [a, b, c]), Alle), writeln(Alle),
    findall(A-B, append(A, B, [1, 2]), Zerlegungen), writeln(Zerlegungen),
    append(Vorne, [3], [1, 2, 3]), writeln(Vorne),
    select(b, [a, b, c], Ohne), writeln(Ohne),
    findall(P, permutation([1, 2, 3], P), Perms), writeln(Perms),
    exclude([X1]>>(X1 mod 2 =:= 0), [1, 2, 3, 4, 5, 6], Ungerade), writeln(Ungerade),
    subtract([1, 2, 3, 4], [2, 4], Diff), writeln(Diff),
    delete([a, b, a, c], a, OhneA), writeln(OhneA),
    list_to_set([a, b, a, c, b], Menge), writeln(Menge).

Ausgabe:

2 ist enthalten
[a,b,c]
[[]-[1,2],[1]-[2],[1,2]-[]]
[1,2]
[a,c]
[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
[1,3,5]
[1,3]
[b,c]
[a,b,c]

Eigene Listenprädikate

mein_laenge([], 0).
mein_laenge([_|T], N) :- mein_laenge(T, N1), N is N1 + 1.
 
mein_append([], L, L).
mein_append([K|T], L, [K|R]) :- mein_append(T, L, R).
 
mein_reverse(L, R) :- rev_akk(L, [], R).
rev_akk([], A, A).
rev_akk([K|T], A, R) :- rev_akk(T, [K|A], R).
 
summe([], 0).
summe([K|T], S) :- summe(T, S1), S is S1 + K.
 
enthalten(X, [X|_]).
enthalten(X, [_|T]) :- enthalten(X, T).
 
verdopple([], []).
verdopple([K|T], [D|R]) :- D is K * 2, verdopple(T, R).
 
main :-
    mein_laenge([a, b, c], N), writeln(N),
    mein_append([1], [2, 3], A), writeln(A),
    mein_reverse([1, 2, 3], R), writeln(R),
    summe([1, 2, 3, 4], S), writeln(S),
    ( enthalten(b, [a, b]) -> writeln(ja) ; writeln(nein) ),
    verdopple([1, 2, 3], V), writeln(V).

Ausgabe:

3
[1,2,3]
[3,2,1]
10
ja
[2,4,6]

Higher-Order: maplist, foldl, include

quadrat(X, Y) :- Y is X * X.
addiere(X, A0, A) :- A is A0 + X.
 
main :-
    maplist(quadrat, [1, 2, 3, 4], Q), writeln(Q),
    maplist([X, Y]>>(Y is X + 10), [1, 2, 3], Plus10), writeln(Plus10),
    foldl(addiere, [1, 2, 3, 4], 0, Summe), writeln(Summe),
    include([X]>>(X > 2), [1, 2, 3, 4], Gross), writeln(Gross),
    exclude([X]>>(X > 2), [1, 2, 3, 4], Klein), writeln(Klein),
    maplist([A, B, C]>>(C is A * B), [1, 2, 3], [4, 5, 6], Produkte), writeln(Produkte),
    sumlist(Produkte, Skalarprodukt), writeln(Skalarprodukt),
    pairs_keys_values(Paare, [a, b, c], [1, 2, 3]), writeln(Paare),
    nb_setval(zaehler, 0),
    forall(member(_, [x, y, z]), (nb_getval(zaehler, V), V1 is V + 1, nb_setval(zaehler, V1))),
    nb_getval(zaehler, Z), writeln(Z).

Ausgabe:

[1,4,9,16]
[11,12,13]
10
[3,4]
[1,2]
[4,10,18]
32
[a-1,b-2,c-3]
3

Strings und Atome

main :-
    atom_length(hallo, L), writeln(L),
    atom_concat(hal, lo, A), writeln(A),
    atom_chars(abc, Zeichen), writeln(Zeichen),
    atom_codes(ab, Codes), writeln(Codes),
    upcase_atom(hallo, Gross), writeln(Gross),
    atom_string(At, "text"), writeln(At),
    string_concat("Hallo ", "Welt", S), writeln(S),
    string_length(S, SL), writeln(SL),
    split_string("a,b,c", ",", "", Teile), writeln(Teile),
    atomic_list_concat([a, b, c], '-', Verbunden), writeln(Verbunden),
    atomic_list_concat(Zerlegt, '-', 'x-y-z'), writeln(Zerlegt),
    sub_atom(hallo, 1, 3, _, Teil), writeln(Teil),
    number_codes(N, "42"), N2 is N + 1, writeln(N2),
    format("~s~n", [[72, 105]]),
    format("~a|~t~w~10||~n", [ab, 12]),
    format("~e ~3f ~q~n", [1234.5, 2.0, 'Hallo Welt']).

Ausgabe:

5
hallo
[a,b,c]
[97,98]
HALLO
text
Hallo Welt
10
[a,b,c]
a-b-c
[x,y,z]
all
43
Hi
ab|     12|
1.234500e+03 2.000 'Hallo Welt'

Merke

  • Listen sind [] oder [Kopf|Rest]; viele Bibliotheksprädikate (append, member, select) arbeiten in beide Richtungen
  • Eigene Prädikate: Basisfall plus rekursiver Fall, oft mit Akkumulator
  • maplist, foldl, include, exclude mit Lambda ([X]>>...) für Funktionen höherer Ordnung
  • Atome, Strings und Zeichenlisten lassen sich mit eingebauten Prädikaten umwandeln

Übungsaufgabe

Schreibe duplikate_entfernen/2 mit eigenen Regeln und vergleiche es mit list_to_set/2.

Quiz zur Selbstkontrolle

Weiter im Kurs

Zurück: Arithmetik und Vergleiche

Weiter: Backtracking, Cut und Kontrolle

Alle Kapitel: Prolog im Überblick

Graphansicht

Backlinks