14 marzo 2007

Si scriva un programma Prolog che prende in ingresso una lista L di numeri interi positivi ed un numero N (di input o di output) e produce in uscita una possibile espressione EX tale che

1. EX è una espressione che rappresenta la somma degli elementi della lista, nell'ordine dato
2. la valutazione di EX fornisca come risultato N.

Esempio:

?- equiv([1,2,3,4,5,6],EX,N).
yes
EX = 1+2+3+4+5+6
N=21
?- equiv([1,2,3],EX,6).
yes
EX = 1+2+3

io l'avevo risolto così:

equiv([], _, 0).
equiv([H|T], EX, N):- equiv(T, H+EX, N1), N is N1+H.

Non riesco a capire dove sta la sostanziale differenza tra la mia soluzione e la soluzione proposta nel compito che comporta che nel mio caso non venga visualizzata l'espressione EX come somma dei numeri che compongono la lista di input.

Il problema è che la variabile EX non viene legata a nulla, per cui alcuni Prolog non mostrano il suo binding.

In effetti la seconda clausola insospettisce un po'. Da un punto di vista logico (dichiarativo), possiamo leggerla come: "Se io so che una lista T è equivalente all'espressione H+EX, allora la lista [H|T] è equivalente a EX"

Ad esempio, se una certa lista è equivalente a 1+2+3, allora aggiungendo l'elemento 1 alla lista, ottengo l'espressione 2+3. Aggiungo un elemento alla lista ed ottengo un'espressione più corta.

Credo che lei abbia immaginato EX come un parametro di "ingresso" per il predicato, per cui ha scritto la somma nella chiamata ricorsiva, mentre è richiesto che sia un parametro di output (se ragioniamo in maniera operazionale).

La struttura del suo programma va bene, ma il termine H+EX andava nella testa della clausola, non nella chiamata ricorsiva. Essendo un parametro di output, anche nella prima clausola dovremo dire qual è il suo valore, non potrà essere una variabile.