CODEWITHSUNDEEP
prologaccumulator
Woden
Woden

Reputation: 1386

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.

Upvotes: 1

Views: 438

Answers (2)

tiffi
tiffi

Reputation: 683

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.

Upvotes: 1

TA_intern
TA_intern

Reputation: 2422

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.

Upvotes: 2

Related Questions