How to calculate a sum of sequence of numbers in P

问题:

The task is to calculate a sum of natural numbers from 0 to M. I wrote the following code using SWI-Prolog:

my_sum(From, To, _) :- From > To, !.
my_sum(From, To, S) :-
  From = 0,
  Next is 1,
  S is 1,
  my_sum(Next, To, S).
my_sum(From, To, S) :-
  From > 0,
  Next is From + 1,
  S is S + Next,
  my_sum(Next, To, S).

But when I try to calculate:

my_sum(0,10,S), writeln(S).

I got False instead of correct number. What is going wrong with this example?

回答1:

this is surely false for Next \= 0: S is S + Next. Another more fundamental problem is that you're doing the computation in 'reverse' order. That is, when From > To and the program stop, you don't 'get back' the result. Then you should add an accumulator (another parameter, to be propagated to all recursive calls) and unify it with the partial sum at that last step...

Anyway, should be simpler:

my_sum(From, To, S) :-
  From < To,
  Next is From + 1,
  my_sum(Next, To, T),
  S is T + From.
my_sum(N, N, N).

| ?- my_sum(2, 4, N).
N = 9

回答2:

I'd write the predicate along these lines, using a worker predicate with an additional accumulator:

sum(X,Y,Z) :-
  integer(X)   ,
  integer(Y)   ,
  sum(X,Y,0,Z)
  .

sum(X,X,T,Z) :- Z is T+X .
sum(X,Y,T,Z) :- X < Y , X1 is X+1 , T1 is T+X , sum(X1,Y,T1,Z) .
sum(X,Y,T,Z) :- X > Y , X1 is X-1 , T1 is T+X , sum(X1,Y,T1,Z) .

This implementation is simple, bi-directional, meaning that sum(1,3,X) and sum(3,1,X) both yield 6 as a result (1+2+3), and tail recursive, meaning that it should be able to handle a range of any size without a stack overflow.

回答3:

As it happens, there's a purely analytic solution as well:

sum(N, Sum) :- Sum is N * (N+1) / 2.

In use:

?- sum(100, N).
N = 5050.

You used the loop tag so this probably isn't an answer you desire, but it's good to prefer this kind of solution when one exists.

回答4:

predicates
 sum(integer,integer)

clauses
 sum(0,0).
 sum(N,R):-
     N1=N-1,
     sum(N1,R1),
     R=R1+N.