Sum up a list using Prolog

Question

I want to sum all list elements greater than some given number. Here's the description:

sumup(L, N, GREATN, GEN) sums up the members of list L which are greater than GREATN to a variable N and puts these members into the list GEN.

Sample query:

?- sumup([8, 6, 10, 3, 9, 12], N, 7, GEN).
GEN = [8, 10, 9, 12],                             % expected answer
N = 39.                                           % 8+10+9+12 = 39

Following is my code:

sum_list([], 0).
sum_list([H|T], Sum) :- 
    H > 3,
    sum_list(T, Rest),
    Sum is H + Rest.
sum_list([H|T], Sum) :-
    H < 3,
    write('').

I've tried the recursive way but I failed. How can I fix it?

Answer 1

Looking at your question and your code, I noticed a few things:

• While you speak of "numbers" several times, your samples are integer-only. May we neglect non-integer numbers (float, rational) and handle integers only? I guess so.
• There is an auto-loaded SWI-Prolog library(lists) predicate sum_list/2.
  Calling your predicate sum_list/2 is an unfortunate choice. Let's pick another name!

• Your definition of sum_list/2 comprises three clauses:

  1. sum_list([], 0). Okay!

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

     Notice H > 3? Why hardcode the constant integer 3?

  3. sum_list([H|T], Sum) :- H < 3, write('').

     • That clause is not recursive. We need to see all list elements to calculate the sum, not stop at the first list element H that fulfills H < 3!

     • What's the use of write('')? I don't see any.

     • What good is the goal H < 3? Like above, why hardcode the integer 3?

     • Clause #2 covers H > 3. Clause #3 covers H < 3. What about H = 3?

---

In this answer we use clpfd, which is present in swi-prolog.

Here's a straight-forward definition of sumup/4 based on clpfd. While it could be improved in several ways (better determinism, accumulator-style, possibly some clever redundant constraints could also help), but for the time being it's a nice first shot:

:- use_module(library(clpfd)).

sumup([], 0, _, []).
sumup([Z|Zs], S0, P, [Z|Xs]) :-
   Z  #> P,
   S0 #= S+Z,
   sumup(Zs, S, P, Xs).
sumup([Z|Zs], S, P, Xs) :-
   Z #=< P,
   sumup(Zs, S, P, Xs).

Sample query as given by the OP:

?- sumup([8,6,10,3,9,12], N, 7, GEN).
   N = 39, GEN = [8,10,9,12]             % expected answer
;  false.                                % leftover useless choicepoint

Answer 2

No need to write recursive code! Just use tfilter/3, (#<)/3, and clpfd:sum/3 like this:

:- use_module(library(clpfd)).

sumup(Zs, S, P, Xs) :-
   tfilter(#<(P), Zs, Xs),
   sum(Xs, #=, S).

Sample query:

?- sumup([8,6,10,3,9,12], S, 7, Xs).
S = 39, Xs = [8,10,9,12].                       % expected result

Note that above query succeeds deterministically—a clear improvement over this previous answer!

---

Bonus! As the implementation of sumup/4 is monotonic, we know that the solution of above query is also part of the solution set of every generalization of the query. Look for yourself!

?- sumup([8,6,10,3,9,12], S, E, Xs).
   S = 48, E in inf..2  , Xs = [8,6,10,3,9,12]
;  S = 45, E in   3..5  , Xs = [8,6,10,  9,12]
;  S = 39, E in   6..7  , Xs = [8,  10,  9,12]  % <==== solution of above query
;  S = 31, E in   8..8  , Xs =     [10,  9,12]
;  S = 22, E in   9..9  , Xs =     [10,    12]
;  S = 12, E in  10..11 , Xs =            [12]
;  S =  0, E in  12..sup, Xs =              []
;  false.

Answer 3

In SWI-Prolog you can use a fold and simply query:

L=[8, 6, 10, 3, 9, 12], include(<(7),L,Gen), foldl(plus,Gen,0,N).

so that sumup would be written as

sumup(L,N,GreatN,Gen) :-
    include(<(GreatN),L,Gen),
    foldl(plus,Gen,0,N).

plus/3 is an arithmetic predicate that works well in our case.