[Prolog] Implementazione della funzione member

[e-commerce84]

Ciao a tutti,
ho da poco iniziato a studiare per un esame che comprende l'uso del Prolog e sono un tantinello disperato con la visione dichiarativa di tale linguaggio.

Un esempio proposto è l'implementazione di una propria funzione member2 che, come la funzione member, restiuisce TRUE se un elemento appartiene alla lista e falso se l'elemento non appartiene alla lista.

Il codice proposto è semplicemente questo:


/* FATTO: (CASO BASE) L'elemento X appartiene alla lista se è in testa alla lista */
member2(X, [X|_]).

/* REGOLA: Se non è in testa è nella TAIL */
member2(X,[_|T]):- member2(X,T).


A grandi linee ho capito come funziona questo semplice programmino ma ho dei dubbi...please...se c'è qualcuno che ne sà qualcosa mi aiuti...

Il FATTO rappresenta il CASO BASE DELLA RICORSIONE

Sostanzialmente dicendo:
member2(X, [X|_]).

stò dicendo che la proposizione member2 è VERA se l'elemento X unifica con la head della lista nel quale stò cercando l'elemento X cercato.

La REGOLA rappresenta il caso generale in cui l'elemento cercato non è nella HEAD della lista quindi praticamente elimino il primo elemento dalla lista e ricorsivamente guardo se l'elemento X ricercato è nella HEAD della restante parte della lista:


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


La cosa che non mi è ben chiara è come funziona esattamente tale operazione...

in pratica penso che nella head della regola member2(X,[_|T]) fà si che X unifica con la variabile anonima _ (che unifica con tutto).

Poi chiama il body della regola member2(X,T)

A questo punto Prolog controlla se c'è un fatto del tipo:
member2(X, [X|_]).

con X che è sempre il nostro elemento da cercare ed il secondo membro [X|_] dove X è il primo elemento della TAIL di prima e vede se il fatto è verificato...se è verificato risponde TRUE, altrimenti richiama ricorsivamente

Ci può stare come raggionamento?

La cosa che però mi risulta assolutamente oscusa in questo ragionamento è la seguente: da quello che sò quando ho una regola del tipo:

HEAD :- BODY

significa che stò dicendo: affinchè HEAD sia verificata, deve essere verificata BODY

Ok...in questo caso però (se fosse come dico io) BODY viene verificata DOPO che la HEAD ha tolto il primo elemento dalla lista...come mai?

Grazie mille

Andrea

[marco.r]

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


Il ragionamento e' un po' piu' semplice se vuoi.


HEAD :- BODY

significa che stò dicendo: affinchè HEAD sia verificata, deve essere verificata BODY

Ok...in questo caso però (se fosse come dico io) BODY viene verificata DOPO che la HEAD ha tolto il primo elemento dalla lista...come mai?

Head non toglie elementi dalla lista. In prolog gli elementi non vengo mai aggiunti o tolti.
Si tratta solo di unificare (con delle eccezioni se vuoi, ma la regola generale e' quella).
Ti riscrivo il caso generico in forma piu' estesa

member2(X,Y):-
Y = [_|T],
member2(X,T).


(Se mi ricordo correttamente la notazione) e' una formulazione assolutamente identica.
E va letta cosi'
"X e' un element di Y se sono verificate le seguenti condizioni:
1 - Y e' una lista, del cui primo elemento non mi frega niente, ma tutto il resto lo chiamo T
2 - X e' un elemento di T"
Come vedi non c'e' alcuna aggiunta o rimozione, si tratta semplicemente di identificare alcune variabili (o parti di), con altre.

Analogamente potresti pensare il caso base come

member2(X, Y):-
Y = [X|_].

Ovvero "X e' un elemento di Y se il primo elemento di Y e' X stesso"
(ancora una volta, spero di ricordarmi correttamente la notazione, ma spero sia comunque chiaro il discorso)

[e-commerce84]

Grazie mille per il chiarimento...ho capito cosa intendi dire anche se purtroppo il tuo codice và in errore in SWI Prolog (vedendo il trace mi viene da pensare che ci possa essere qualcosa che non và quando fai l'assegnazione Y = [_|T] ...non sò se si usi il carattere =, io sapevo che per fare le assegnazioni si usa is ma facendo tipo Y is [_|T] [/b] sbrocca comunque :muro: :muro: :muro: DISPERAZIONE :muro: :muro: :muro: Se ti venisse qualche idea...sarebbe molto figo :D

Già che ci sono ne approfitto un altro po' per vedere se ho capito bene un altro esempio relativo alla concatenazione di 2 stringhe:

E' richiesto che dato: myappend(L1,L2,L3), a fine esecuzione si ha che L1*L2 (L2 concatenato ad L1)

Il codice è il seguente:


/* FATTO: CASO BASE: La lista vuota concatenata alla lista L è uguale alla lista L */
myappend([], L, L).

/* REGOLA */

myappend([X|L1], L2, [X|L]) :- myappend(L1,L2,L).


Da quello che ho capito, anche alla luce di quello che mi hai detto te:

FATTO = CASO BASE DELLA RICORSIONE: Corrisponde al caso in cui la prima lista è vuota e la seconda no --> La concatenazione delle due liste sarà sicuramente uguale alla seconda lista L2.

REGOLA = CASO GENERALE:

A questo punto, andandomi a vedere il trace di ciò che avviene nelle variabili mi pare di capire funzioni così (facciamo un esempio su di un caso concreto):


myappend([a,b], [c,d], L3).
|
|
\/
NON è il caso base, quindi ricado nella regola che consuma un elemento dalla prima lista
|
|
\/
myappend([b], [c, d], L3)
|
|
\/
NON è il caso base, quindi ricado nella regola che consuma un elemento dalla prima lista
myappend([], [c, d], L3)
|
|
\/
Sono nel caso base, applico il caso base [b]myappend([], L, L). Quindi L3 viene UNIFICATA CON [c,d]
|
|
\/
myappend([], [c, d], [c, d])

Una volta che ho raggiunto il caso base torno indietro ricorsivamente ed "applico la HEAD della regola...tornando indietro di uno step avrei:

myappend([b], [c, d], L3) e la HEAD della regola era: myappend([X|L1], L2, [X|L])

quindi il primo parametro è [X|L1] che corrisponde a [b|[]], il terzo invece sarà [X|[c,d]]

Ed io lo interpreto come X = b, prendi b e sbattilo al posto della X nel terzo parametro che diventa così [b,c,d]

Probabilmente continuo a sbagliare modo di pensare e stavo appunto cercando una forma estesa tipo la tua...

Avevo pensato a qualcosa del genere (ma non riuscendo a far girare questi esempi in forma estesa booo):


myappend(L1,L2,L3) :-
Y = [X|L1].
myappend(Y,L2,L3).


La mia idea sarebbe la seguente chiamo la funzione su L1 ed L2 da concatenare.
Nella prima istruzione estraggo un elemento dalla lista L1 e richiamo la funzione myappend su Y (L1 senza la sua head)...questa cosa viene fatta fintanto che Y non è la lista vuota [], a questo punto si esegue il caso base ed L3 si unifica ad L2 (quindi contiene gli stessi elementi)...ed ora si fà backtracking ma non riesco a capire come vengono messe in testa gli elementi di L1 che sono stati estratti uno ad uno...

Oddio...sono disperato...ma è normale che ragionare in questo modo sia così difficile (eppure in programmazione tipo Java et similia me la cavo benino...)