Recursivitate pe liste

Sumar

În Prolog nu avem for loops. Singura modalitate de a parcurge iterativ o listă este recursivitatea. Fiecare listă are două părți: capul (head, primul element) și coada (tail, restul listei).

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

Pattern-ul

my_predicate([], ...) :- base_case(...).
my_predicate([H | T], ...) :- ..., my_predicate(T, ...), ... .

• Cazul de bază: ce se întâmplă când lista e vidă (sau are un singur element).
• Cazul recursiv: descompune lista în [H | T], prelucrează H, recurge pe T, combină rezultatele.

Exemple

Lungimea unei liste:

list_length([], 0).
list_length([_ | T], Length) :-
    list_length(T, LengthTail),
    Length is LengthTail + 1.

Suma elementelor:

list_sum([], 0).
list_sum([H | T], Sum) :-
    list_sum(T, SumTail),
    Sum is SumTail + H.

Apartenență (member):

elements_of(X, [X | _]) :- !.
elements_of(X, [_ | T]) :-
    elements_of(X, T).

Două liste în paralel (zip / dot product):

dot([], [], 0) :- !.
dot([H1 | T1], [H2 | T2], Result) :-
    dot(T1, T2, ResultTail),
    Result is ResultTail + H1 * H2.

Atenție la cap și coadă

Din breviar:

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

[H | T] = [1].      % H = 1, T = []
[H | T] = [].       % EROARE
[A, B | T] = [a, b, c, d].   % A = a, B = b, T = [c, d]
[A, B | T] = [a].   % EROARE — B nu se poate instanția

Idiomuri

Acumulator pentru calcule eficiente — vezi Fibonacci cu memoizare (Lab 2):

fib(F, _, N, N, F) :- !.
fib(F1, F0, Index, N, F) :-
    F2 is F1 + F0,
    NewIndex is Index + 1,
    fib(F2, F1, NewIndex, N, F).

efficient_fib(N, F) :- fib(1, 1, 1, N, F).

Transformare element cu element (map):

scalarMult(_, [], []) :- !.
scalarMult(X, [H | T], [HR | TR]) :-
    HR is X * H,
    scalarMult(X, T, TR).