Somma di una lista in Prolog

Question

Sto leggendo 'The Art of Prolog' libro e ho trovato un esercizio che legge 'Definisci la somma della relazione (ListOfintegers, Sum) che detiene se la somma è la somma della somma dei listOfinters, senza utilizzare un predicato ausiliario ".iHa trovato questa soluzione:

sum([],Sum).
sum([0|Xs], Sum):-sum(Xs, Sum).
sum([s(X)|Xs], Sum):-sum([X|Xs],s(Sum)).

.

che non funziona esattamente come vorrei che lo vorrei.

?- sum([s(s(0)),s(0),s(s(s(0)))],X).
true ;
false.

.

Mi aspettavo x essere

s(s(s(s(s(s(0))))))

.

Pensavo che il problema sia che devo "inizializzare" la somma a 0 nella prima "iterazione" ma sarebbe molto procedurale e purtroppo non sono abbastanza adatto a Prolog per fare quel lavoro. Qualche idea o suggerimento?

Answer 1

Il modo migliore per localizzare il problema è prima semplificare la tua query:

?- sum([0],S).

true
?- sum([],S).

true

.

Anche per quelli, ottieni una risposta che qualsiasi S lo farà. Come

?- sum([],s(s(0))).
yes

.

Poiché [] può essere gestito solo dal tuo fatto, un errore deve trovarsi in questo fatto. Hai dichiarato:

sum([], Sum).

.

Il che significa che la somma del [] è solo qualsiasi cosa. Probabilmente hai intenzione di 0.

Un altro errore si nasconde nell'ultima regola ... Dopo aver fissato il primo errore, otteniamo

?- sum([0],Sum).
Sum = 0
?- sum([s(0)],Sum).
no

.

Qui, l'ultima clausola è responsabile. Legge:

sum([s(X)|Xs], Sum):-sum([X|Xs],s(Sum)).

.

Le regole ricorsive sono relativamente ingannevoli da leggere in Prolog. Il modo più semplice per capirli è guardare il :- e capire che questa dovrebbe essere una freccia ← (quindi una freccia destra a sinistra) significato:

. fornito, che gli obiettivi sul lato destro sono veri

---

concludiamo ciò che si trova sul lato sinistro

Quindi, rispetto alla scrittura informale, le frecce puntano nella direzione opposta!

Per la nostra query, possiamo considerare il seguente istanziazione sostituzione Xs con [] e X con 0.

sum([s(0)| [] ], Sum) :- sum([0| []],s(Sum)).

.

Quindi questa regola recita ora a destra a sinistra: fornita, sum([0],s(Sum)) è vero, ... tuttavia, sappiamo che solo sum([0],0) tiene, ma non quell'obiettivo. Pertanto, questa regola non si applica mai! Quello che intendevi era piuttosto il contrario:

sum([s(X)|Xs], s(Sum)):-sum([X|Xs],Sum).

.

Answer 2

La tua prima clausola dovrebbe leggere

sum([], 0).

.

Con quel cambiamento, il rendimento vago true va via e sei lasciato con un problema: la terza clausola inverte la logica della sommazione.Dovrebbe essere

sum([s(X)|Xs], s(Sum)) :- sum([X|Xs], Sum).

.

Poiché il numero di termini s/1 nell'argomento sinistro a sum/2 dovrebbe essere uguale al numero di essi nell'argomento giusto.

Answer 3

Non sto seguendo la tua logica, cosa con tutte le strutture di s(X) Estrane di Seasinging Estraneo fluttuano.

Non sarebbe più facile e più semplice fare qualcosa del genere?

In primo luogo, definisci la tua soluzione in inglese semplice, quindi:

.
• La somma di un elenco vuoto è 0.
• La somma di un elenco non vuoto è ottenuto aggiungendo la testa dell'elenco alla somma della coda dell'elenco.

Da quella definizione, il Prolog segue direttamente:

sum( []     , 0 ) .  % the sum of an empty list is 0.
sum( [X|Xs] , T ) :- % the sum of an non-empty list is obtained by:
  sum( Xs , T1 ) ,   % - first computing the sum of the tail
  T is X + T1        % - and then, adding that the to head of the list
  .                  % Easy!

.