可以将文章内容翻译成中文,广告屏蔽插件可能会导致该功能失效(如失效,请关闭广告屏蔽插件后再试):
问题:
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.
回答1:
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?
回答2:
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.
回答3:
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].
回答4:
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...