As a newbie in Prolog, I learned that tail recursion is optimized. Therefore, I am trying to convert the following program to tail-recursive ones.
sum([], 0).
sum([H|T], N):-
sum(T, X),
N is X + H.
Here is what I've tried, and it's obvious that I missed something in my logics:
sum(List,Sum):-
sum1(List,0,Sum).
sum1([Element|List],Accumulator,Sum):-
(NewAccumulator is Accumulator + Element,
sum1(List,NewAccumulator,Sum);
List=[] -> Sum = Accumulator
).
The problem in my program is adding all the numbers except the last one in the list. How can I improve this program? Thanks.
I agree with TA_intern's solution, but here is an addition to show you why your program did go wrong.
The following program leaves as much of your code as possible, but is correct:
sum(List,Sum):-
sum1(List,0,Sum).
sum1([Element|List],Accumulator,Sum):-
NewAccumulator is Accumulator + Element,
(sum1(List,NewAccumulator,Sum);
List=[] -> Sum = NewAccumulator
).
You had List=[] -> Sum = Accumulator
, that means that in case the tail of your list was empty, you took Accumulator
, which is the sum of all previous elements before Element
.
An alternative that preserves even more of your code is:
sum1([Element|List], Accumulator, Sum) :-
( NewAccumulator is Accumulator+Element,
sum1(List, NewAccumulator, Sum)
; List=[]
-> Sum is Accumulator+Element
).
However, I personally would prefer TA_intern's solution.