Breviar — predicate predefinite în Prolog și referință teoretică

Portat după breviar.pl al profesorului Bogdan Macovei. Textul păstrează vocea originală — comentariile din .pl sunt aduse aici verbatim.

atom/1

Verifică dacă un string este atom în Prolog.

Atom = orice șir de caractere care începe cu literă mică, sau care e scris între simboluri ' '.

?- atom(X).        false
?- atom(myAtom).   true
?- atom('My Atom').  true

Reguli

În scrierea regulilor, folosim structura

Head :- Body.

Dacă Body e satisfăcut, atunci satisfacem și Head. (Head if Body)

  • Facts — conțin doar Head, sunt cunoștințele de bază.
  • Rules — cele care conțin Body. În Body, putem înlănțui cunoștințele prin:
    • , (ȘI = conjuncție)
    • ; (SAU = disjuncție)

Cut (!/0)

Pentru a limita recursia pe cazurile de bază, folosim !/0 — predicatul CUT. El este util când avem clauze scrise una sub alta — atunci se face disjuncție între clauze.

Dacă se satisface o clauză, Prolog încearcă satisfacerea celorlalte clauze imediat următoare. Pentru a opri acest mecanism, e util !.

base_case(params) :- !.

Operatori aritmetici

Uzuali:

+, -, *, /        (/ este pe floats)
//, div           (cât)
mod               (rest)
**                (exponențiere)

Egalități:

=       caută unificator
==      egalitate structurală
=:=     egalitate aritmetică

is/2 — atribuire aritmetică

?- X is 1 + 2.    atunci X = 3

is/2 funcționează când membrul drept este COMPLET instanțiat:

?- Y = 2, X is Y + 2.       răspunde Y = 2, X = 4
?- X is Y + 2.              eroare — "Arguments are not sufficiently instantiated"

Liste în Prolog

[se, reprezinta, prin, paranteze, patrate, si, cu, elemente, separate, prin, virgula]

Pot conține elemente de orice tip, amestecate oricum: [0, [], [X], f(X), Y] etc.

Notația utilă: [Head | Tail] (sau [H | T] în general, în probleme).

Head-ul unei liste vide conduce la eroare! Tail-ul listei vide este lista vidă.

[H | T] = [1]         atunci H = 1, T = []
[H | T] = []          atunci EROARE
[A, B | T] = [a,b,c,d]  atunci A = a, B = b, T = [c, d]
[A, B | T] = [a, b]   atunci A = a, B = b, T = []
[A, B | T] = [a]      atunci EROARE pentru că B e în Head (înainte de `|`) și nu se poate instanția

length/2

Returnează lungimea unei liste.

?- length([1, 2, 3], L).    atunci L = 3

member/2

Verifică dacă un element apare sau nu într-o listă.

?- member(b, [a, b, c, d]).   true
?- member(t, [a, b, c, d]).   false

union/3

Reuniunea a două liste, cu rezultatul o listă reprezentând o mulțime — elementele sunt distincte.

?- union([1, 2, 3, 2], [1, 4, 3, 2], L).    atunci L = [1, 4, 3, 2]

append/3

Concatenează două liste: mai întâi prima, apoi a doua.

?- append([1, 2, 3, 2], [1, 4, 3, 2], L).
atunci L = [1, 2, 3, 2, 1, 4, 3, 2]

string_chars/2

Split-uiește un șir de caractere într-o listă de caractere corespunzătoare.

?- string_chars(prolog, Res).     atunci Res = [p, r, o, l, o, g]

numlist/3

Primește două capete de interval și returnează lista întregilor din intervalul închis.

?- numlist(-2, 3, Res).    atunci Res = [-2, -1, 0, 1, 2, 3]

Dacă primul argument > al doilea, returnează false.

findall/3

findall(X, P, L) pune în L toți acei X astfel încât să respecte P.

divisorsPairs(A, B, List) :-
    numlist(A, B, Range),
    findall((X, Y),
            (member(X, Range), member(Y, Range), X mod Y =:= 0),
            List).

I.e. găsește toate perechile (X, Y) cu proprietatea că X aparține Range, Y aparține Range și restul împărțirii lui X la Y este 0 (adică Y este divizor al lui X) și pune toate aceste perechi în List.

reverse/2

reverse(ListInput, ListOutput)

Returnează în ListOutput reverse-ul listei ListInput.

predsort/3

Utilizat pentru sortare cu un comparator:

predsort(MyCompare, InputList, SortedList).

select/3

Utilizat pentru a elimina un element dintr-o listă.

?- select(10, [1, 2, 3], R).
false.

?- select(2, [1, 2, 3], R).
R = [1, 3] ;
false.

?- select(2, [1, 2, 3, 2, 4], R).
R = [1, 3, 2, 4] ;
R = [1, 2, 3, 4] ;
false.

?- select(2, [1, 2, 3, 2, 4, 2], R).
R = [1, 3, 2, 4, 2] ;
R = [1, 2, 3, 4, 2] ;
R = [1, 2, 3, 2, 4].

nth0/3 / nth1/3

Extrage elementul de pe un index dat dintr-o listă.

  • nth0 — indexare de la 0
  • nth1 — indexare de la 1
?- nth0(1, [a, b, c, d], Elem).
Elem = b

permutation/2

Primește o listă și returnează toate permutările posibile.

?- permutation([1, 2], [X, Y]).
X = 1, Y = 2 ;
X = 2, Y = 1 ;
false.

Predicate utile, dar care nu sunt definite în Prolog

sum/2 — suma dintr-o listă

sum([], 0) :- !.
sum([H | T], Res) :-
    sum(T, ResT),
    Res is ResT + H.

zip/3 — perechi de elemente de pe aceeași poziție

?- zip([1, 2, 3], [a, b, c], Res).
atunci Res = [(1, a), (2, b), (3, c)]

zip se oprește la lungimea celei mai scurte dintre cele două liste!

?- zip([1, 2, 3, 4], [a, b, c], Res).
atunci Res = [(1, a), (2, b), (3, c)]

?- zip([1, 2, 3], [a, b, c, d, e], Res).
atunci Res = [(1, a), (2, b), (3, c)]

zip([], _, []) :- !.
zip(_, [], []) :- !.
zip([H1 | T1], [H2 | T2], [(H1, H2) | TR]) :-
    zip(T1, T2, TR).

all_symb/2 — toate elementele egale cu un simbol dat

?- all_symb([a, a, a], a).    atunci true
?- all_symb([a, A, a], a).    atunci A = a, true (este satisfăcut când A = a)

all_symb([S], S) :- !.
all_symb([H | T], S) :-
    H = S,
    all_symb(T, S).

max/2 — maximul dintr-o listă

max([], 0) :- !.
max([H | T], MaxTail) :-
    max(T, MaxTail),
    MaxTail >= H, !.
max([H | T], H) :-
    max(T, MaxTail),
    H >= MaxTail.

remove_duplicates/2

Returnează lista primită ca prim argument, dar fără elemente duplicate.

remove_duplicates([], []) :- !.
remove_duplicates([H | T], [H | TR]) :-
    not(member(H, T)),
    remove_duplicates(T, TR), !.
remove_duplicates([_ | T], TR) :-
    remove_duplicates(T, TR).

Exemplu de BFS

succesor(1, 2).
succesor(1, 3).
succesor(1, 4).
succesor(2, 4).
succesor(2, 5).
succesor(3, 5).
succesor(3, 4).
succesor(4, 3).
objective(5).


extend([Node | Path], NewPath) :-
    findall([NewNode, Node | Path],
            (succesor(Node, NewNode), not(member(NewNode, [Node | Path]))),
            NewPath).

breadthfirst([[Node | Path] | _], [Node | Path]) :- objective(Node).
breadthfirst([Path | PathTail], Solution) :-
    extend(Path, ExtendedPath),
    append(ExtendedPath, PathTail, NewPath),
    breadthfirst(NewPath, Solution).

solve(Start, Solution) :-
    findall(S, breadthfirst([[Start]], S), Solution).

Exemplu de arbori și parcurgere

def(myTree,
    tree(1,
         tree(2, tree(4, nil, tree(7, nil, nil)), nil),
         tree(3, tree(5, nil, nil), tree(6, nil, nil)))).

% inordine
srd(nil, []).
srd(tree(Root, Left, Right), Result) :-
    srd(Left, ResultLeft),
    srd(Right, ResultRight),
    append(ResultLeft, [Root | ResultRight], Result).

Pentru UNIFICARE

unify_with_occurs_check/2 verifică dacă doi termeni pot unifica sau nu.

Atenție la specificația de limbaj! Variabilele din limbaj sunt și cele din Prolog, deci se scriu cu Majusculă.