CODEWITHSUNDEEP
listprolog
user721588
user721588

Reputation:

Sum of elements in list in Prolog

list_sum([], 0).
list_sum([Head | Tail], TotalSum) :-
    list_sum(Tail, Sum1),
    Total = Head + Sum1.

This code returns true. If I replace Total = Head + Sum1 with Total is Head + Sum1, then it will return the value. But what I should replace it with to get the result like this:

?- list_sum([1,2,0,3], Sum).
Sum = 1+2+0+3 ; % not to return value 6!!!

Upvotes: 20

Views: 97395

Answers (5)

Rok Kralj
Rok Kralj

Reputation: 48725

The answer is simple:

sum_list([], 0).
sum_list([H|T], Sum) :-
   sum_list(T, Rest),
   Sum is H + Rest.

This code works in only one direction - this means - it does not allow you to generate lists with that specific sum. But since the set of such lists is infinite, that would not be practical anyways.

Upvotes: 37

Rohan
Rohan

Reputation: 91

The program is

list_sum([],0).

list_sum([Head|Tail], TotalSum):-
list_sum(Tail, Sum1),
TotalSum is Head+Sum1.

now if the query is 

?- list_sum([1,2,3,4], Sum).

answer is

Sum = 10

Upvotes: 6

repeat
repeat

Reputation: 18726

In Prolog (+)/2 is a binary infix operator. This allows us to write A+B instead of +(A,B).

?- current_op(_,yfx,+).   % left-associative binary infix operator
true.

(+)/2 associates to the left, so 1+2+3 is a short for (1+2)+3.

(.)/2 associates to the right, so [1,2,3] is short for .(1,.(2,.(3,[]))).

To get parenthesization right, we use an auxiliary predicate with an extra "accumulator" argument:

list_sum([X|Xs],S) :-
   list_sum0_sum(Xs,X,S).

list_sum0_sum([],    S ,S).
list_sum0_sum([X|Xs],S0,S) :-
   list_sum0_sum(Xs,S0+X,S).

Sample query:

?- list_sum([1,2,0,3],S).
S = 1+2+0+3.

Upvotes: 2

Nicholas Carey
Nicholas Carey

Reputation: 74257

If you want to transform a list of numbers into an additive expression, from

[1,2,3]

to

1 + 2 + 3

you could do something like this, using something like a difference list:

list_to_additive_expr( [] , 0 ).
list_to_additive_expr( [X|Xs] , X + RHS ) :-
  sum_of( Xs , RHS ).

Alternatively, you could use an accumulator:

list_to_additive_expr( Xs , Expr ) :-
  list_to_additive_expr( Xs , 0 , Expr )
  .

list_to_additive_expr( []     , Expr , Expr ) .
list_to_additive_expr( [X|Xs] , RHS , Expr ) :-
  sum_of( Xs , X + RHS , Expr )
  .

I believe you'll find the first style is not properly tail recursive and so won't get optimized into a loop via tail recursion optimization (TRO) — and so, if the list is sufficiently long, will get a stack overflow. The second approach should have TRO applied and should work for lists of any length.

What is TRO, you might ask? Here's Wikipedia with an answer for you:

In computer science, a tail call is a subroutine call that happens inside another procedure and that produces a return value, which is then immediately returned by the calling procedure. The call site is then said to be in tail position, i.e. at the end of the calling procedure. If a subroutine performs a tail call to itself, it is called tail-recursive. This is a special case of recursion.

Tail calls are significant because they can be implemented without adding a new stack frame to the call stack. Most of the frame of the current procedure is not needed any more, and it can be replaced by the frame of the tail call, modified as appropriate (similar to overlay for processes, but for function calls). The program can then jump to the called subroutine. Producing such code instead of a standard call sequence is called tail call elimination, or tail call optimization.

Upvotes: 1

gusbro
gusbro

Reputation: 22585

Note that in the second clause of your procedure TotalSum is never instantiated. You should have received a warning by the interpreter when consulting your code.

Here's my suggestion:

list_sum([Item], Item).
list_sum([Item1,Item2 | Tail], Total) :-
    list_sum([Item1+Item2|Tail], Total).

The first clause deals with the base case, when there is only one element left in the list, that is your result.

The second clause deals with the recursion step. It grabs the first two items of the list and performs a recursive call replacing those two items with a new term Item1+Item2.

Upvotes: 13

Related Questions