Prolog - Wie bekomme ich die Summe der Elemente einer Liste?

Question

Ich bin sehr neu zu Prolog und ich versuche, ein kleines Programm zu schreiben, das, eine Liste gegeben, die Summe der Elemente der Liste zurückgibt. Im Anschluss an alle Beispiele, die ich habe zu einer Lösung führte mich gesehen, die wie folgt aussieht:

addup([],0). 
addup([FirstNumber | RestOfList], Total) :- 
    addup(RestOfList, TotalOfRest), 
    Total is FirstNumber + TotalOfRest. 

Aber wenn ich testen, dass die Lösung mit diesen Werten:

?- addup([1,2,3,4],0). 

bekomme ich nur Müll Werte von es wie _34521.

Dann habe ich versucht, eine zweite Lösung, die wie folgt aussieht:

sum([], 0). 
sum([H|T], N):- 
    X is H+N, 
    sum(T, X). 

Dieser ist in der Lage, die Zahlen richtig zu addieren, aber es ist nicht in der Lage den Endwert von X passieren, was die richtige Antwort ist für den Testfall, in N. So:

?- sum([1,2,3,4], 0). 

ich erhalte eine Antwort von 6, um den endgültigen Wert von N, und den zweiten bis zum vorletzten Wert von X, statt 10, der Endwert von X Jede Hilfe und/oder Erklärung, warum keine dieser Lösungen funktioniert, wäre sehr willkommen. Vielen Dank.

Answer 1

Erstens ist die Summe einer leeren Liste 0 - das ist der Basisfall, den Sie bereits hatten.

Zweitens ist die Summe N eines Elements H und eine Liste T ist die Summe aus der Liste T-H hinzugefügt. Prolog arbeitet auf Vereinheitlichung, so sagt dies, dass N ist vereinheitlicht mit der Summe von H und T, wo die Summe von T ist vereinheitlicht mit X mit sum(T,X).

sum([], 0). 
sum([H|T], N):- 
    sum(T, X), 
    N is X + H. 

Das gibt:

?- sum([1,2,3,4],N). 
N = 10. 

In Ihrer ursprünglichen Frage, ?- sum([1,2,3,4], 0). sagt tatsächlich „das wahr ist, wenn die Summe der Liste [1,2,3,4] ist 0“ - Sie eine Variable als zweites Argument übergeben müssen zu sum mit der Antwort vereinheitlicht werden.

Weitere Informationen:

_34521 ist eine Darstellung einer ungebundenen Variable - das sagt, dass es eine Variable ist, sondern dass sie noch nicht mit einem Wert vereinheitlicht.

zweitrangig:

Für eine entsprechend lange Liste, die Umsetzung oben wird aus Stapelspeicher laufen, da jeder Rahmen der Rekursion gespeichert werden müssen, so dass die Zugabe von unten nach oben passieren kann.

sum(L, N):- 
    sum(L, 0, N). 

sum([],N,N). 
sum([H|T],A,N) :- 
    A1 is A + H, 
    sum(T,A1,N). 

..., die die Signatur des Originalmethode behält, Umwickeln sum/3: Um einen Stapelfehler zu vermeiden, können wir einen tail-rekursive Akkumulator wie so verwenden.Da im Hauptteil der Regel kein Auswahlpunkt vorhanden ist (da A + H für ein gegebenes A und H immer gleich ist und die Liste entweder leer ist oder nicht), löscht Prolog jedes Bild, wenn es den Bereich verlässt (da es nichts mehr zu tun gibt) und nach der Fertigstellung zu dem ursprünglichen Anrufer zurückkehren wird.

Vereinfachtes Stack für sum([1,2,3],N) jeweils:

nicht-tail-rekursive:

rest-of-stack 
rest-of-stack,sum([1|[2,3]],_1001) 
rest-of-stack,sum([1|[2,3]],_1001),sum([2|[3]],_1002) 
rest-of-stack,sum([1|[2,3]],_1001),sum([2|[3]],_1002),sum([3|[]],_1003) 
rest-of-stack,sum([1|[2,3]],_1001),sum([2|[3]],_1002),sum([3|[]],_1003),sum([],0) 
rest-of-stack,sum([1|[2,3]],_1001),sum([2|[3]],_1002),sum([3|[]],3) 
rest-of-stack,sum([1|[2,3]],_1001),sum([2|[3]],5) 
rest-of-stack,sum([1|[2,3]],6) 
rest-of-stack 

tail-rekursive:

rest-of-stack 
rest-of-stack,sum([1,2,3],_1001) 
rest-of-stack,sum([1|[2,3]],0,_1001) 
rest-of-stack,sum([2|[3]],1,_1001) 
rest-of-stack,sum([3|[]],3,_1001) 
rest-of-stack,sum([],6,6) 
rest-of-stack 

anzumerken, dass der Schwanz-rekursive Stapel eine begrenzte hat Tiefe für jede Länge der Liste (abhängig davon, was sie aufruft), wobei der nicht-tail-rekursive Stapel zu einer Tiefe geht, die direkt proportional zu der Länge der Liste ist.

Daher wird ein Aufruf wie N is 10^7,length(L,N),maplist(=(1),L),sum(L,N). (wie von @ false ausgelöst) wahrscheinlich ohne Tail-Rekursion fehlschlagen und wahrscheinlich damit erfolgreich sein.