Prolog - Product List Search

Question

I'm a super newbie to prolog (swi proog), so sorry if this is a stupid question. Also this is an uni assignment. I was asked to find a product listing, 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 a base case like:

 product([],0). 

But it does all zero. However, when testing the base case of product([],Product) , I get one - this is not true. Any hints of a solution would be appreciated.

Answer 1

This is not true: 1 is an element of identification of "numbers" during multiplication. You can, for example, distract the operation and the loop to have something line by line:

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

Therefore, you need to define identity_element/2 and the operation itself. Thus, adding and multiplying will look something like this:

 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 string concatenation identification element is an empty string. So, if you just added the following sentence to identity_element/2 :

 identity_element(atom_concat, ''). 

Now you can say:

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

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

As for the other answer : perhaps 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 that seems wrong. You should have a base case:

 product([], 1). 

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

Answer 2

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

The first reason, as CapelliC's answer shows, if you need it to be 0, then you have a logical gap. The predicate requires special processing to work with product 0 compared to 1.

There are no special reasons why the product of an empty list is 0. The fact that

 foo([], X). 

Describes the relationship foo between [] and X What should be X ? Just because the list is empty does not 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 and p2 , respectively. Then if I have:

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

What should be X ? 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] , the product of which is 120, i.e. 6 x 20 . So far so good.

Now suppose L2 = [] . Then L = [2, 3] . If product(L2, 0) , then I would have p2 = 0 and p1 x p2 = 0 . But product(L, 6). , so logic breaks, and we have a mathematical or logical gap. However, if product([], 1). then everything works as expected.

In an arithmetic sense, an algebraic identity is what you are 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 . Similarly, a can be written ax 1 x ... x 1 . Thus, the mathematical value for product([], 1). must be true.

Answer 3

As often when describing the relations associated with lists, it makes sense to start with a description of two cases: one for an empty list and one for lists with at least one element.

In the second sentence, you can use foldl/4 and a small helper predicate. For instance:

 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 an empty list is reasonably defined as 1, so when creating a product for several lists, empty lists naturally mix 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 4

I agree with the point of view expressed by @Boris, but I think that if you want to get 0 in empty lists, you can use pattern matching, one of the distinguishing features of Prlog:

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

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

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

Therefore, please modify my offer as necessary.

to avoid a cut, an alternative pattern may be

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

now the second and third sentences no longer overlap, but it may be that your Prolog is not smart enough to optimize the predicate ...