Adding elements in two lists as numbers

Question

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).
link([Head|Tale],L2,L3):- link(Tale,L2,L), L3=[Head|L].

inve([],[]):-!.
inve([X|Xs],L):- inve(Xs,L2), link(L2,[X],L).


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.

Answer 1

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].