Get product of the list items by using recursion in Prolog?

Question

How do you get a product of the list items by using recursion?

If I ask:

product([s(0), s(s(0)), s(s(0))], S).

The result should be:

S = s(s(s(s(0)))).

But I geep geting wrong results. Or no results.

I tried:

product([], 0).
product([], Res).
product([H1, H2|T], Res) :- T\=[], mul(H1, H2, Res), product(T, Res).
product([H|T], Res) :- mul(H, Res, X), product(T, X).

mul is multiplication and it works fine.

If I use trace i can see that it finds th result but than it failes for some reason.

Call: (10) product([], s(s(s(s(0))))) ? creep
Fail: (10) product([], s(s(s(s(0))))) ? creep

Any idea anyone?

Answer 1

I think you'll find that this does the trick:

product([], 0).
product([H], H).
product([H1, H2|T], Res) :-
    mul(H1, H2, H),
    product([H|T], Res).

The first predicate is a trivial base case.

The second is where the list only contains a single element - so that's the answer.

The third is where you have a list of two or more elements - simply perform the mul/3 on the first two and then recursively call product/2. This will eventually match predicate 2 and complete.

Your sample input does yield s(s(s(s(0)))).

Please in the future include the definition for mul/3. I had to search the internet to find one.

%Addition
sum(0,M,M). %the sum of an integer M and 0 is M.
sum(s(N),M,s(K)) :- sum(N,M,K). %The sum of the successor of N and M is the successor of the sum of N and M.

%Multiplication
%Will work for mul(s(s(0)),s(s(0)),X) but not terminate for mul(X,Y,s(s(0)))
mul(0,M,0). %The product of 0 with any integer is 0
mul(s(N),M,P) :- 
    mul(N,M,K), 
    sum(K,M,P). %The product of the successor of N and M is the sum of M with the product of M and N. --> (N+1)*M = N*M + M