How to sum up multiple lists in Prolog

user_14536465 0
Viewed 186

This is a problem suma( [ [ 1, 2, 3, 4 ], [ 2, 3, 4, 5 ], [ 3, 4, 5, 6 ] ], X ), and i need to get this result X = [ 10, 14, 18 ]. I don't have any idea how to figure this out. Please help

prolog
2 Answers

maplist/3 and foldl/4 and yall notation (the last one available in SWI-Prolog) are your friends.

suma(ListOfLists,ListOfSums) :-
   maplist(
      ([Sublist,Sum]>>
          (foldl(
              [AccumIn,X,AccOut]>>(AccOut is AccumIn + X),
              Sublist,
              0,
              Sum))),
      ListOfLists,
      ListOfSums).

Thus:

?- suma( [ [ 1, 2, 3, 4 ], [ 2, 3, 4, 5 ], [ 3, 4, 5, 6 ] ], X ).
X = [10, 14, 18].

This is less logic programming than functional programming, but if one has a Swiss Army Knife, one might as well use it!

  • maplist/3: Calls the goal that is on argument position 0 for every pair [Sublist,Sum] where Sublist is an element of the list on argument position 1 (i.e. ListOfLists) and Sum is an element of the list on argument position 2 (i.e. ListOfSums), both elements being at the same position in their respective lists.
  • The goal called takes [Sublist,Sum] and calls foldl/4, which "folds-left" the list Sublist using the goal on argument position 0, starting with value 0 and resulting in value Sum.
  • The folding operation is simply arithmetic addition via [AccumIn,X,AccOut]>>(AccOut is AccumIn + X).

This can be more extensively written as:

suma(ListOfLists,ListOfSums) :-
   maplist(
      p2,            % will be called with 2 parameters
      ListOfLists,
      ListOfSums).

p2(Sublist,Sum) :-
   foldl(
      p3,            % will be called with 3 parameters
      Sublist,
      0,
      Sum).

p3(AccumIn,X,AccOut) :-
   AccOut is AccumIn + X.

We can run some plunit test cases for good measure (actually, the problem to solve should be stated with the below, TDD and all that):

:- begin_tests(sum_over_sublists).

test("empty list of lists",true(R == [])) :-
   suma([],R).

test("all sublists contain one value",true(R == [1,2,3])) :- 
   suma([[1],[2],[3]],R).
   
test("one sublist is empty",true(R == [1,0,3])) :- 
   suma([[1],[],[3]],R).
   
test("standard case #1",true(R == [6,15,24])) :- 
   suma([[1,2,3],[4,5,6],[7,8,9]],R).
   
test("standard case #2",true(R == [10,14,18])) :-
   suma([[1,2,3,4],[2,3,4,5],[3,4,5,6]],R).

:- end_tests(sum_over_sublists).

And so:

?- run_tests.
% PL-Unit: sum_over_sublists ..... done
% All 5 tests passed
true.
user_8844630 

%! sum(Xs,SUM)
%
% calculate the total sum of the items in list `Xs` .

sum(Xs,SUM)
:-
sum(Xs,0,SUM)
.

sum([],SUM0,SUM0) .

sum([X0|Xs],SUM0,SUM)
:-
SUM1 is SUM0 + X0 ,
sum(Xs,SUM1,SUM)
.


/*
?- sum([1,2,3,4],SUM).
SUM = 10.

?- sum([2,3,4,5],SUM).
SUM = 14.

?- sum([3,4,5,6],SUM).
SUM = 18.
*/


%! suma(Xss0,SUM)
%
% calculate the total sum of the items in list of lists `Xss` .

suma([],0) .

suma([Xs0|Xss0],SUM)
:-
sum(Xs0,SUM0) ,
suma(Xss0,SUM1) ,
SUM is SUM0 + SUM1
.


/*
?- suma([[1,2,3,4],[2,3,4,5]],SUM).
SUM = 24.

?- suma([[1,2,3,4],[2,3,4,5],[3,4,5,6]],SUM).
SUM = 42.
*/
user_77013500
Related