Prolog Language
Ragionamento sui dati

Osservazioni

ricorsione

Il prologo non ha iterazione, ma tutta l'iterazione può essere riscritta usando la ricorsione. La ricorsione appare quando un predicato contiene un obiettivo che si riferisce a se stesso. Quando si scrivono tali predicati in Prolog, uno schema ricorsivo standard ha sempre almeno due parti:

• Clausola base (non ricorsiva) : in genere le regole del caso base rappresenteranno l'esempio / i più piccoli possibili del problema che si sta tentando di risolvere: un elenco senza membri o un solo membro o se si Lavorando con una struttura ad albero, potrebbe trattarsi di un albero vuoto o di un albero con un solo nodo, ecc. Descrive in modo non ricorsivo la base del processo ricorsivo.

• Clausola ricorsiva (continua) : contiene qualsiasi logica necessaria, inclusa una chiamata a se stessa, ricorsione continua.

Ad esempio, definiremo il predicato noto append/3 . Visto in termini dichiarativi, append(L1,L2,L3) vale quando la lista L3 è il risultato di liste aggiunte L1 e L2 . Quando proviamo a capire il significato dichiarativo di un predicato, proviamo a descrivere le soluzioni per le quali il predicato è valido. La difficoltà qui sta nel cercare di evitare ogni dettaglio ricorrente passo dopo passo, tenendo sempre presente il comportamento procedurale che il predicato dovrebbe mostrare.

% Base case
append([],L,L).

% Recursive clause
append([X|L1],L2,[X|L3]) :- append(L1,L2,L3).

Il caso base dichiara dichiaratamente che "ogni L aggiunto alla lista vuota è L", nota che questo non dice nulla sul fatto che L sia vuoto - o addirittura che sia una lista (ricorda che in Prolog tutto si riduce a termini):

?- append(X,some_term(a,b),Z).
X = [],
Z = some_term(a, b).

Per descrivere la regola ricorsiva, sebbene Prolog esegua le regole da sinistra a destra, omettiamo la testa per un secondo e guardiamo prima il corpo - leggendo la regola da destra a sinistra:

    append([X|L1],L2,[X|L3]) :- append(L1,L2,L3).

Ora diciamo che se il corpo sostiene: "supponendo che append(L1,L2,L3) contenga"

    append([X|L1],L2,[X|L3]) :-  append(L1,L2,L3). 

Quindi lo fa anche la testa: "allora anche append([X|L1],L2,[X|L3]) "

In inglese semplice ciò si traduce semplicemente in:

Supponendo che L3 sia la concatenazione di L1 e L2, quindi [X seguito da L3] è anche la concatenazione di [X seguito da L1] e L2.

In un esempio pratico:

"Supponendo [1,2,3] è la concatenazione di [1] e [2,3], quindi [a, 1,2,3] è anche la concatenazione di [a, 1] e [2,3]. ”

Ora esaminiamo alcune domande:

È sempre consigliabile testare inizialmente il predicato con la query più generica anziché fornire un caso di scenario specifico. Pensaci: grazie all'unificazione di Prolog, non siamo tenuti a fornire dati di prova, semplicemente li consegniamo a variabili libere!

?- append(L1,L2,L3).
L1 = [],
L2 = L3 ;                                   % Answer #1
L1 = [_G1162],
L3 = [_G1162|L2] ;                          % Answer #2
L1 = [_G1162, _G1168],
L3 = [_G1162, _G1168|L2] ;                  % Answer #3
L1 = [_G1162, _G1168, _G1174],
L3 = [_G1162, _G1168, _G1174|L2] ;          % Answer #4
...

Sostituiamo la notazione variabile _G1162 con lettere alfabetiche per ottenere una panoramica migliore:

?- append(L1,L2,L3).
L1 = [],
L2 = L3 ;                                   % Answer #1
L1 = [_A],
L3 = [_A|L2] ;                              % Answer #2
L1 = [_A, _B],
L3 = [_A, _B|L2] ;                          % Answer #3
L1 = [_A, _B, _C],
L3 = [_A, _B, _C|L2] ;                      % Answer #4
...

Nella prima risposta, il caso base è stato abbinato al modello e il Prolog ha istanziato L1 alla lista vuota e L2 e L3 unificati dimostrando che L3 è la concatenazione della lista vuota e L2.

Alla risposta n. 2, attraverso il backtrack cronologico, la clausola ricorsiva entra in gioco e Prolog prova a dimostrare che alcuni elementi nella testa di L1 concatenati con L2 sono L3 con lo stesso elemento nella sua testa di lista. Per fare ciò, una nuova variabile libera _A è unificata con la testa di L1 e L3 ha dimostrato di essere ora [_A|L2] .

Viene creata una nuova chiamata ricorsiva, ora con L1 = [_A] . Ancora una volta, Prolog prova a dimostrare che alcuni elementi posizionati nella testa di L1 , concatenati con L2 sono L3 con lo stesso elemento nella sua testa. Notare che _A è già la testa di L1 , che corrisponde perfettamente alla regola, quindi ora, attraverso la ricorsione, Prolog mette _A davanti a una nuova variabile libera e otteniamo L1 = [_A,_B] e L3 = [_A,_B|L2]

Vediamo chiaramente che il pattern ricorsivo si ripete e può facilmente vedere che, ad esempio, il risultato del 100 ° step in ricorsione sarà simile a:

L1 = [X1,X2,..,X99],
L3 = [X1,X2,..,X99|L2]

Nota: come è tipico per il buon codice Prolog, la definizione ricorsiva di append/3 ci fornisce non solo la possibilità di verificare se una lista è la concatenazione di altre due liste, ma genera anche tutte le risposte possibili soddisfacendo le relazioni logiche con o elenchi parzialmente istanziati.

Accedere agli elenchi

Membro

member/2 ha un member(?Elem, ?List) firma member(?Elem, ?List) e indica true se Elem è un membro di List . Questo predicato può essere utilizzato per accedere a variabili in un elenco, in cui vengono recuperate diverse soluzioni tramite il backtracking.

Query di esempio:

?- member(X, [1,2,3]).
X = 1 ;
X = 2 ;
X = 3.

?- member(X,[Y]).
X = Y.

?- member(X,Y).
Y = [X|_G969] ;
Y = [_G968, X|_G972] ;
Y = [_G968, _G971, X|_G975] ;
Y = [_G968, _G971, _G974, X|_G978]
...

Pattern matching

Quando gli indici a cui devi accedere sono piccoli, la corrispondenza dei modelli può essere una buona soluzione, ad esempio:

third([_,_,X|_], X).
fourth([_,_,_,X|_], X).