Sum of even and odd numbers of a list in Prolog

Question

What I need to do is to write a predicate that takes a list of numbers and returns a list consisting of two elements, the first one is the sum of the even numbers and the second one the sum of the odd numbers.

For example:

?- sum([5,4,9,8,1,7], L).
L = [12, 22].

So far I have written:

iseven(N) :-
    0 is mod(N,2).

Have you tried anything besides your `iseven/1` predicate? – lurker Jun 10 '17 at 13:09 — lurker, Jun 10 '17 at 13:09

coder · Accepted Answer · 2017-06-10T13:17:32.087

3

Since you've defined iseven/2 you could use it like:

sum([],[0,0]).
sum([H|T],[N1,N2]):- 
             sum(T,[N3,N4]),
             ( iseven(H) 

              ->  N1 is N3+H, N2 is N4
              ;   N2 is N4+H, N1 is N3

             ).

Example:

?-sum([5,4,9,8,1,7], L).
L = [12, 22].

A non if-then-else version using different clauses:

sum([],[0,0]).
sum([H|T],[N1,N2]):- sum(T,[N3,N2]), iseven(H), N1 is N3+H.
sum([H|T],[N1,N2]):- sum(T,[N1,N3]), \+ iseven(H), N2 is N3+H.

edited Jun 10 '17 at 13:17

answered Jun 10 '17 at 13:00

coder

12,832
5
39
53

This approach works perfectly, but I understand that this uses an if-then-else approach that we haven't taught (this is an exercise for a course of mine). – sarotnem Jun 10 '17 at 13:14
1

@sarotnem since this is a homework assignment you should try to understand the principle established in the original answer and come up with a solution. This is not a site where people are here to do all of your homework for you. The original solution uses principles you could adapt to come up with a non-if-then-else approach. – lurker Jun 10 '17 at 16:13
1

@lurker I tried to solve this for about 2 hours and I always ended up with an error. This happened because I was trying to implement a classic if-then-else solution without success of course. Believe it or not, after seeing this answer I understood the principle and applied it to similar homework I had! So I guess for me this way worked to learn :) – sarotnem Jun 10 '17 at 17:51
2

@saro: For the second solution, say `maplist(=(1),L),time(sum(L,[A,B])).` to see how the number of inferences doubles with each further 1! `length(L,100),maplist(=(1),L),time(sum(L,[A,B])).` takes certainly too much time. See [this](https://stackoverflow.com/a/19941560/772868) for the reason why. – false Jun 10 '17 at 18:56
2

@sarotnem you can easily sidestep the if-then-else construct by breaking it into two clauses, one with each of the conditions. So `iseven(X) -> p2 ; p3` can be written as a call to `foo(X)` and define `foo(X, ...) :- iseven(X), p2.` and `foo(X) :- isodd(X), p3.` – lurker Jun 10 '17 at 21:54

score 3 · Answer 2 · answered Jun 10 '17 at 23:36

You could also write this predicate using accumulators and if_/3. Furthermore you can incorporate the single goal of iseven/1 into the predicate:

list_sums(L,S) :-
   list_sums_(L,S,0-0).

list_sums_([],[E,O],E-O).
list_sums_([X|Xs],S,E0-O0) :-
   M is X mod 2,
   if_(M=0,(E1 is E0+X, O1 is O0),(E1 is E0, O1 is O0+X)),
   list_sums_(Xs,S,E1-O1).

Note how the accumulators are written as a pair (E-O). If you are free to choose a representation for the two sums, this pair notation would be an alternative to a list with two elements. Your example query yields the desired result:

?- list_sums([5,4,9,8,1,7],L).
L = [12, 22].

And the example from the comments terminates considerably faster:

?- length(L,100),maplist(=(1),L),time(list_sums(L,[A,B])).
% 703 inferences, 0.000 CPU in 0.000 seconds (100% CPU, 3426895 Lips)
L = [1, 1, 1, 1, 1, 1, 1, 1, 1|...],
A = 0,
B = 100.

However, due to the use of is/2 this is only working in one direction. If you'd like to use the predicate in the other direction as well, you could opt to use CLP(FD). In that case include the line

:- use_module(library(clpfd)).

in your source file and replace all occurrences of is/2 in list_sums_/3 by #=/2:

list_sums_([],[E,O],E-O).
list_sums_([X|Xs],S,E0-O0) :-
   M #= X mod 2,
   if_(M=0,(E1 #= E0+X, O1 #= O0),(E1 #= E0, O1 #= O0+X)),
   list_sums_(Xs,S,E1-O1).

Your example query still yields the same result and the example from the comments terminates in an acceptable time:

?- length(L,100),maplist(=(1),L),time(list_sums(L,[A,B])).
% 18,928 inferences, 0.004 CPU in 0.004 seconds (99% CPU, 4888152 Lips)
L = [1, 1, 1, 1, 1, 1, 1, 1, 1|...],
A = 0,
B = 100.

But the predicate works in both directions now. In some cases Prolog can find concrete answers without further ado:

?- list_sums([A,B],[2,1]).
A = 2,
B = 1 ;
A = 1,
B = 2 ;
false.

In other cases you get residual goals as an answer:

?- L=[A,B,C,D,E,F], list_sums(L,[12,22]).
L = [A, B, C, D, E, F],
A+B#=_G3306,
A mod 2#=0,
B mod 2#=0,
_G3306+C#=_G3342,
C mod 2#=0,
_G3342+D#=12,
D mod 2#=0,
E+F#=22,
E mod 2#=_G3402,
F mod 2#=_G3414,
_G3414 in 0..1,
dif(_G3414, 0),
_G3402 in 0..1,
dif(_G3402, 0) ;
...

In these cases you can restrict the elements of the list to some interval and use label/1 to get concrete numbers as solution. For example, you can ask for solutions with six numbers from zero to seven and Prolog will give you all 300 solutions:

?- length(L,6), L ins 0..7, list_sums(L,[12,22]), label(L).
L = [6, 6, 1, 7, 7, 7] ;
L = [6, 6, 3, 5, 7, 7] ;
...

score 1 · Answer 3 · answered Jun 10 '17 at 17:43

1

You can use a functionnal way :

one_sum(X, [SE,SO], [SE1, SO1]) :-
    (   X mod 2 =:= 0 ->
        SE1 is SE+X, SO1 = SO
    ;   SE1 = SE, SO1 is SO+X).

sum(L, S) :-
    foldl(one_sum, L, [0,0], S).

answered Jun 10 '17 at 17:43

joel76

5,565
1
18
22

Sum of even and odd numbers of a list in Prolog

3 Answers3