Prolog - finding the product of a list

Question

I'm super new to prolog (swi prolog) so sorry if this is a dumb question. Also this is a uni assignment. I was asked to find the product of a list and this is what I came up with:

product([],1).
product([H|T], Product) :-
    product( T, Product1),
    Product is H * Product1.

For the longest I had the base case as:

product([],0).

But that makes everything zero. However, when testing the base case of product([],Product), I get one - which is incorrect. Any hints to a solution will be appreciated.

Answer 1

I agree to the viewpoint expressed by @Boris, but I think that if you want 0 as a result for an empty lists, you could exploit pattern matching, one of distinctive features of Prlog:

product([], 0).
product([N], N).
product([H|T], Product) :-
    product(T, Product1),
    Product is H * Product1.

Since the base case introduced overlaps with the recursive clause, a cut is needed, to avoid

?- product([2,3,5],X).
X = 30 ;
X = 0.

So please change my suggestion as required.

edit to avoid the cut, an alternative pattern could be

product([], 0).
product([N], N).
product([H,I|T], Product) :-
        product([I|T], Product1),
        Product is H * Product1.

now second and third clauses don't overlap anymore, but could be that your Prolog isn't smart enough to optimize the predicate...

Answer 2

As often when describing relations involving lists, it makes sense to start with describing two cases: One for the empty list, and one for lists involving at least one element.

In the second clause, you can use foldl/4 and a small auxiliary predicate. For example:

list_product([], 1).
list_product([L|Ls], P) :-
        foldl(product_, Ls, L, P).

product_(A, B, P) :- P is A*B.

And in fact you can equivalently write this as:

list_product(Ls, P) :- foldl(product_, Ls, 1, P).

The product of the empty list is sensibly defined as 1 so that, when building the product over several lists, empty lists blend in naturally and do not change any results.

Examples:

?- list_product([1,2,3,4], P).
P = 24.

and:

?- maplist(list_product, [[1,2],[],[3,4]], Ps), list_product(Ps, P).
P = 24,
Ps = [2, 1, 12].

Answer 3

This is not incorrect: 1 is the identity element of "numbers" under multiplication. You can for example abstract away the operation, and the loop, to have something along the lines of:

list_op_product(L, Op, P) :-
    identity_element(Op, IE),
    reverse(L, R), % no foldr in SWI-Prolog, at least
    foldl(Op, R, IE, P).

So you only need to define identity_element/2 and the operation itself. So, addition and multiplication would be something like:

identity_element(add, 0).
identity_element(mult, 1).

add(X, Y, R) :- R is X + Y.
mult(X, Y, R) :- R is X * Y.

And then you can say:

?- list_op_product([2,3,4], add, Sum).
Sum = 9.

?- list_op_product([2,3,4], mult, Product).
Product = 24.

Similarly, the identity element of string concatenation is the empty string. So, if you just add the following clause to identity_element/2:

identity_element(atom_concat, '').

You can now say:

?- list_op_product([a,b,c], atom_concat, R).
R = abc.

Of course, most of this is unnecessary, but it shows the point.

As for the other answer: there is maybe a cleaner way than a cut to avoid incorrect answers:

product([], 0).
product([H|T], P) :-
    product_1(T, H, P).

product_1([], P, P).
product_1([H|T], H0, P) :-
    product_1(T, H, P0),
    P is P0 * H0.

So now:

?- product([2,3,5], P).
P = 30.

?- product([], P).
P = 0.

But this feels wrong. You should still have a base case:

product([], 1).

This clause of product/2 simply defines what your identity element is; this is why it is still better to leave the 1 there and not replace it with a 0! However, you will do one multiplication less for non-empty lists (you won't have the last * 1). This is a valid and easy-to-make optimization. If you try to find the product of a type that does not have an identity element at all: then, product([], X) is not defined. You can either leave out the clause, then ?- product([], X) will fail. Or, you can maybe throw an error?

Answer 4

I would suggest that the product of an empty list should be 1.

First reason, as CapelliC's answer shows, if you require it to be 0, then you have a logical discontinuity. The predicate needs special handling to deal with a 0 product versus a 1.

There's no special reason for the product of an empty list to be 0. The fact:

foo([], X).

Describes a relation foo between [] and X. What should X be? Just because the list is empty doesn't mean that the logical answer is 0.

Let's look at another perspective. Suppose I have two lists of numbers,L1 and L2. And suppose the products of these lists are p1 andp2, respectively. Then if I have:

append(L1, L2, L), product(L, X).

What should X be? I would think it would be p1 x p2. If L1 = [2, 3] and L2 = [4, 5], then we have p1 = 6, p2 = 20. L = [2, 3, 4, 5], whose product is 120, which is 6 x 20. So far so good.

Now suppose L2 = []. Then L = [2, 3]. If product(L2, 0), then I'd have p2 = 0, and p1 x p2 = 0. But product(L, 6). so the logic breaks down and we have mathematical or logical discontinuity. However, if product([], 1)., then this all works as expected.

In an arithmetic sense, algebraic identity is what you have by default if there is nothing. For sums, the identity is 0, and I can write a as a + 0 + ... + 0 and still have a. Likewise, a can be written a x 1 x ... x 1. So it makes mathematical sense for product([], 1). to be true.