Добавление двух списков, представляющих числа в прологе

Question

Задача гласит: числа представлены списками (например, 123 = [1, 2, 3]), напишите предикат, который добавляет два таких числа. (например, sum([4, 5, 6], [9], [4, 6, 5])).

Я думал, как выразить это рекурсивно, но что меня заставляет, когда размеры массивов меняются. Кажется, что это было бы просто, если бы массивы были возвращены, так что HEAD фактически является последним элементом. Потому что для меня проблема в том, что моя сумма выглядит так, что:

[4, 5, 6] 
+ 
    [9] 

вместо

[4, 5, 6] 
+ 
     [9] 

Что может быть надлежащим образом написать такой предикат? Мне нужны некоторые указатели или ссылки на помощь ...

Answer 1

Вот моя реализация:

sum(L1,L2,OutL):- 
     reverse(L1,List1),reverse(L2,List2), 
     add_lists(List1,List2,0,List3), 
     reverse(List3,OutL). 

add_lists([],[],0,[]). 
add_lists([],[],1,[1]). 
add_lists([],[H|T],C,[H1|T]):-H1 is H+C. 
add_lists([H|T],[],C,[H1|T]):-H1 is H+C. 
add_lists([H|T],[H1|T1],C,[H2|T2]):-NH is H1+H, 
         (NH > 10 -> NC is 1,H2 is NH+C-10; H2 is NH+C,NC is 0), 
          add_lists(T,T1,NC,T2). 

Идея заключается в том, чтобы обратить вспять списки для того, чтобы добавить правильные позиции и избежать проблем вы ссылались. Кроме того, вы просто держать кэрри, который является 1, если добавление больше, чем 10, где вы уменьшаете 10.

Пример:

?- sum([4, 5, 6], [9], L). 
L = [4, 6, 5] ; 
false.