# Adding elements in two lists as numbers

The problem is adding two lists as numbers L1 = [1,9,9] and L2 = [0,9,9]:

?- sum([1,9,9],[0,9,9], Lo).
Lo = [2,9,8]


But I also wanted to add this:

?- sum([8,1,9],[1,8,2],Lo).
Lo = [1, 0, 0, 1].


I used the backtracking method I've learned:

link([],L,L).

inve([],[]):-!.

sum(L1,L2,L3):- inve(L1,LI1),inve(L2,LI2), sumID(LI1,LI2,L), inve(L,[Li|LIs]),
Li > 9, Li2 is Li-10 , L3 = [1,Li2|LIs] ,!.
sum(L1,L2,L3):- inve(L1,LI1),inve(L2,LI2), sumID(LI1,LI2,L), inve(L,L3),!.

sumID([],[],[]):- !.
sumID([X|[Xs|Xss]],[Y|Ys],[L|Ls] ):- XY is X+Y , XY > 9 , Head is XY - 10,
L = Head, Xs1 is Xs + 1,
sumID([Xs1|Xss], Ys, LTail) ,Ls = LTail,!.

sumID([X|Xs],[Y|Ys],[L|Ls]):- L is X+Y, sumID(Xs,Ys,LTail),
Ls = LTail.


A friend told me to invest list and add from *Left to Right*, and later invest the final list. How can I improve this solution in order not to be so long? I'd appreciate a better idea to solve this problem, too. I made it in more than 2 hours and in the exam this is supposed to be in 20min.

When describing lists, always consider using DCGs. In this case, try for example:

sum(Xs0, Ys0, Ls) :-
reverse(Xs0, Xs),
reverse(Ys0, Ys),
phrase(sum(Xs, Ys, 0), Ls0),
reverse(Ls0, Ls).

sum([], [], Carry) -->
(   { Carry > 0 } -> [Carry]
;   []
).
sum([X|Xs], [Y|Ys], Carry0) -->
{ N0 is X + Y + Carry0,
(  N0 > 9 ->  N is N0 - 10, Carry = 1
;  N = N0, Carry = 0
) },
[N],
sum(Xs, Ys, Carry).


Exampe queries and their results:

?- sum([1,9,9], [0,9,9], Ls).
Ls = [2, 9, 8].

?- sum([8,1,9], [1,8,2], Ls).
Ls = [1, 0, 0, 1].

• About DCGs, I know what you mean by ''always'' ,but can you translate into normal definite clauses in Prolog without "{ } , --> ". For now, is not required DCGs, i'd appreciate normal clauses because I don't understand it very well. – YonCho Apr 3 '15 at 5:59
• Just let the Prolog system do this for you: In SWI-Prolog, use ?- listing(sum//3). to get the expanded version. To use the expanded version in your program, copy&paste it instead of the DCG version, and write sum(Xs, Ys, 0, Ls0, []) instead of phrase(sum(Xs, Ys, 0), Ls0). – mat Apr 3 '15 at 10:38