13 Giugno 2002

Si scriva un programma Prolog che rimpiazzi in una lista L1 tutte le occorrenze di una costante C1 con un'altra C2 producendo una nuova lista L2 e indichi in N il numero di sostituzioni eseguite.

Il predicato che realizza tale programma avrà cinque argomenti:

replace_all(L1,C1,C2,L2,N)

Ecco alcuni esempi di funzionamento:

?-
replace_all([a,b,a,c,a,d],a,mike,Result,N).
Result = [mike,b,mike,c,mike,d] 
N=3

?- replace_all([],b,foo,Result,N).
N=0
Result = []

?- replace_all([a,b,a,c,a,d],prolog,logic,Result).
Result = [a,b,a,c,a,d] 
N=0

Soluzione proposta:

replace_all([],C1,C2,[],0).
replace_all([C1|L1],C1,C2,[C2|L2],N1):-
        !,replace_all(L1,C1,C2,L2,N), N1 is N+1. 
replace_all([C|L1],C1,C2,[C|L2],N):-
                   replace_all(L1,C1,C2,L2,N).

Domanda:

Ci chiedevamo se il predicato cut all'inizio della seconda chiamata fosse necessario e se incrementando la var N1 prima di effettuare la chiamata

replace_all(L1,C1,C2,L2,N)

comporta un errore.

Il cut serve per evitare di fare backtracking sulla terza clausola.

Nel corpo della seconda, non potete anticipare N1 is N+1 perché N è istanziato dalla chiamata precedente di replace_all. N1 is N+1 fallirebbe, se messo prima di replace_all, poiché N sarebbe ancora  non legata a valore.