Prolog - суммирование чисел из двух списков

Question

Я пытаюсь написать программу пролога, которая суммирует элементы из двух списков и представляет результат в другом списке.

Например:

List1:

[1, 3, 4, 2] 

List2:

[5, 1, 3, 0] 

Результат:

[6, 4, 7, 2] 

До сих пор у меня есть это:

list_sum([],[],[]). 
list_sum([H1|T1],[H2|T2],L3):-list_sum(T1,T2,[X|L3]), X is H1+H2. 

?-list_sum([1,2,3,4],[1,2,3,4],R),write(R). 

Answer 1

Вы почти находитесь. Ваша проблема заключается в том, что результат суммы должен быть помещен в главу второго предложения, а не в рекурсивный вызов!

list_sum([H1|T1],[H2|T2],[X|L3]):-list_sum(T1,T2,L3), X is H1+H2. 

Обратите внимание, что, как вы написали это, L3, который «возвращаются» в результате список, в котором вы удалили голова (X) от возвратного степенного вызова; тогда как вы имели в виду обратное: добавить элемент (X) в результирующий список.

Answer 2

Результат должен быть списком, поэтому вы не можете просто сказать X is H1+H2, потому что X не является списком, и вы только сопоставляете голову списков с одной переменной. также list_sum([],[],0) не подходит по той же причине. ответ выглядит следующим образом:

sum([],[],[]). 
sum([H1| T1], [H2| T2], [ResH| ResT]) :- 
     sum(T1, T2, ResT), 
     ResH is H1+H2. 

, но когда вы используете свой собственный код, первый X сопоставляется с H1 + H2, на втором рекурсивного вызова Х имеет значение и не может быть согласована с руководителем Т1 + Т2 , поэтому он выводит no.

Answer 3

Что сказал @gusbro. Кроме того, вы должны изменить порядок операций и добавить несколько дополнительных особых случаев иметь дело со списками различной длины:

list_sum([]  , []  , [] ) . 
list_sum([]  , [Y|Ys] , [Z|Zs]) :- Z is 0+Y , list_sum([] , Ys , Zs) . 
list_sum([X|Xs] , []  , [Z|Zs]) :- Z is X+0 , list_sum(Xs , [] , Zs) . 
list_sum([X|Xs] , [Y|Ys] , [Z|Zs]) :- Z is X+Y , list_sum(Xs , Ys , Zs) . 

Вы должны переместить оценку (Z is X+Y) в моем примере выше, так что Z оценивается до рекурсия. Это решает две вещи:

• во-первых, это делает предикат хвостовой рекурсией, то есть решение является итеративным и, следовательно, не потребляет пространство стека. В вашем коде оценки не выполняются до тех пор, пока не будет завершена вся рекурсия. Каждая промежуточная сумма хранится в стеке и оценивается справа налево на вашем пути назад. Это означает, что вы ударите свой стек в большом списке.

• Во-вторых, оценка каждого результата перед рекурсией означает, что вы сбой быстро. Первая сумма, которая не объединяется с результатом, не позволяет выполнить всю операцию. Ваше решение не работает медленно. Рассмотрите 10 000 000 списков товаров, в которых первый элемент не суммируется с первым элементом в списке результатов: вы пройдете все 10 000 000 предметов, затем —, предполагая, что вы не взорвали свой стек. — вы начинаете оценивать суммы справа налево. Ваш предикат не потерпит неудачу до самой последней оценки.

Answer 4

Если вы используете SWI-Prolog можно использовать MapList и модуль лямбда нашел там: http://www.complang.tuwien.ac.at/ulrich/Prolog-inedit/lambda.pl:

:- use_module(library(lambda)). 

list_sum(L1, L2, L3) :- 
    maplist(\X^Y^Z^(Z is X + Y), L1, L2, L3). 

Answer 5

это один вкладыш в SWI-Пролог:

list_sum(X,Y,S) :- maplist(plus, X,Y,S). 

И работает также «назад»:

?- maplist(plus, [1,2,3],Y,[3,4,5]). 
Y = [2, 2, 2]. 

Answer 6

domains 
list=integer* 
predicates 
add(list,list,list) 
clauses 
add([],[],[]). 
add([V1X|X],[V1Y|Y],[V1Z|Z]):-add(X,Y,Z),V1Z=V1X+V1Y.