Prolog - transforming to tail recursion

user_13126518 0
Viewed 87

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.

accumulator prolog
2 Answers

The problem is that you wrote the program wrongly. This would be correct:

sum(List, Sum) :-
    sum_1(List, 0, Sum).

sum_1([], Sum, Sum).
sum_1([H|T], Sum0, Sum) :-
    Sum1 is Sum0 + H,
    sum_1(T, Sum1, Sum).

but you could have googled some version of this here on stackoverflow.

This is also trivially a fold on a list:

sum([H|T], Sum) :-
    foldl(add, T, H, Sum).

add(X, Y, Z) :- Z is X + Y.
user_144119970

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.

user_65406060
Related