Блог

Главная - Вопросы по программированию - Как суммировать несколько списков в Prolog

Как суммировать несколько списков в Prolog

#prolog

#пролог

Вопрос:

Это проблема suma( [ [ 1, 2, 3, 4 ], [ 2, 3, 4, 5 ], [ 3, 4, 5, 6 ] ], X), и мне нужно получить этот результат X = [10, 14, 18]. Я понятия не имею, как это выяснить. Пожалуйста, помогите

Ответ №1:

maplist/3 и foldl/4 и все обозначения (последние, доступные в SWI-Prolog) — ваши друзья.

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

Таким образом:

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

Это менее логическое программирование, чем функциональное программирование, но если у кого-то есть швейцарский армейский нож, его можно использовать!

  • maplist/3 : Вызывает цель, которая находится в позиции аргумента 0 для каждой пары [Sublist,Sum] , где Sublist является элементом списка в позиции аргумента 1 (т.Е. ListOfLists ) и Sum является элементом списка в позиции аргумента 2 (т.Е. ListOfSums ), Причем оба элемента находятся в одной и той же позиции в своих соответствующих списках.
  • Вызываемая цель принимает [Sublist,Sum] и вызывает foldl/4 , которая «сворачивает влево» список Sublist , используя цель в позиции аргумента 0, начиная со значения 0 и приводя к значению Sum .
  • Операция складывания — это просто арифметическое сложение с помощью [AccumIn,X,AccOut]>>(AccOut is AccumIn X) .

Это может быть более подробно записано как:

 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.

Мы можем запустить несколько plunit тестовых примеров для хорошей оценки (на самом деле, проблема, которую нужно решить, должна быть указана ниже, TDD и все такое):

 :- 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).

И так:

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

Комментарии:

1. Я также думаю, что Prolog нуждается в небольшом расширении для альтернативной работы с позиционными параметрами и именованными параметрами, чтобы можно было писать foldl(start=0,list=Sublist,result=Sum,goal=p3) так, как это можно делать в цепочках правил, таких как CLIPS.

2. Если вы все равно переходите на SWI, вы также можете использовать его sum_list/2 (который действительно должен вызываться list_sum/2 для отражения порядка аргументов).

3. @IsabelleNewbie «Фиксирует» использование foldl/N ?

4. Да, и с помощью library(yall) . maplist(sum_list, Xss, Sums) короче, чем ваше решение, и переносится, по крайней мере, на GNU Prolog. Не поймите меня неправильно, в хвастовстве нет ничего library(yall) плохого! Мне просто показалось интересным, что в данном конкретном случае вы делаете слишком много работы самостоятельно.

Ответ №2:

 
%! 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.
*/

Комментарии:

1. Но результат последнего примера должен быть [ 10, 14, 18 ] , а не 42 . Вы должны суммировать по отдельным подспискам, а не по всем элементам всех подсписков.

2. @DavidTonhofer что-то нужно оставить для домашней работы .