Prolog program with lists

Question

I have to solve as a homework the following problem in turbo prolog: "Determine the product of a number represented as digits in a list to a given digit. E.g.: [1 9 3 5 9 9] * 2 --> [3 8 7 1 9 8] " .

My line of thinking into solving this problem is that I first compute the product, and then I put its digits into the list.Only I can't really figure this last part.Here is my source code so far:

domains

list=integer*

predicates

    length(list,integer)

powerten(integer,integer)

product(integer,list,integer) /* this predicate computes the product */

    /* the product,powerten and length are taken care of */


addDigit(integer,list) /* this predicate should decompose the number in its digits and put them in the list */


productList(integer,list,list)

clauses

     length([],0).

     length([_|T],L):-

            length(T,L1),

            L=L1+1.

powerten(0,1):-!.

powerten(L,N):-
    L1=L-1,
    powerten(L1,N1),
    N=N1*10.

product(_,[],0):-!.

product(NR,[H|T],RESULT ):-
    length([H|T],LEN),
    L2=LEN-1,

    powerten(L2,N),
    product(NR,T,R1),
    RESULT=R1+H*N*NR.




addDigit(0,[]):-!.


addDigit(NR,[NR|_]):-

    NR>0,
    DIGIT = NR MOD 10,
    NR1=NR DIV 10,
    addDigit(NR1,_).        


productList(NR,L1,L2):-

     /* this is the "main" predicate . Its arguments are NR - the first factor, L1- the 
         initial list, whose digits make the second factor, L2 - the result list which            
          contains  the digits of he result */

            product(NR,L1,RESULT),

            addDigit(RESULT,L2).

As you can see all is well until the addDigit predicate. I just can't find a way to add the digits of the product into the the final list. Can anyone help me with a solution? Thanks.

Answer 1

That seems complicated to me. The problem is to basically do long-form multiplication, the way that you'd do it on paper. If you first reverse the list (using the built-in reverse/2 predicate), things become much simpler:

%--------------------------------------------------------------%
% Mult/3: multiply a integer, represented as a list of digits, %
%         by an integer value N, producing an integer, also    %
%         represented as a lsit of digits.                     %
%--------------------------------------------------------------%
multiply( Ds , N , Result) :-
  reverse(Ds,Rs) ,
  multiply( Rs , N , 0 , T ) ,
  reverse( T , Result )
  .

%
% the worker predicate that does all the work
%
multiply( [] , _ , C , []      ) :-    % if the list is exhausted
  C =< 0                               %   and the carry is 0,
  .                                    %   we're done. C'est fini.
multiply( [] , _ , C , [C] ) :-        % if the list is exhausted
  C > 0 ,                              %   and the carry is 1-9, then
  C < 10                               %   The last digit in the result is the carry
  .                                    %   We're done. C'est fini.
multiply( [] , _ , C , [R|Rs] ) :-     % If the list is exhausted,
  C >= 10 ,                            %   and the carry is 10+,
  R is C rem 10 ,                      %   the next digit in the result is the carry modulo 10
  Q is C div 10 ,                      %   take the quotient
  multiply( [] , _ , Q , Rs )          %   and recurse down with the quotient as the carry
  .                                    %
multiply( [D|Ds] , N , C , [R|Rs] ) :- % if the list is NOT exhausted,
  T is D*N + C ,                       %   compute the product for this digit
  R is T rem 10 ,                      %   the next digit in the result is that product modulo 10
  Q is T div 10 ,                      %   the next carry is the quotient
  multiply( Ds , N , Q , Rs )          %   recurse down
  .                                    $ Easy!

Answer 2

addDigit seems wrong to me: you use only the first, and leave the tail unspecified ! try

addDigit(NR,[DIGIT|Ns]):-
    NR>0,
    DIGIT = NR MOD 10,
    NR1 = NR DIV 10,
    addDigit(NR1, Ns).