prologaccumulator

Prolog - transforming to tail recursion


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.


Solution

  • 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.