Prolog:为什么我的谓词返回 false? [英] Prolog: why my predicate returns false?

问题描述

所以我写了一个谓词来计算一个元素在列表列表中出现的次数.

so I wrote a predicate that counts how many times an element occurs in a list of lists.

count([], _, 0).                                  #base case

count([[Elem|Rest]|OtherLists], Elem, Count) :-   #Elem is the head of sublist
    !,
    count([Rest|OtherLists], Elem, NewCount),
    succ(NewCount, Count).

count([[_|Rest]|OtherLists], Elem, Count) :-      #Elem is not the head of sublist
    count([Rest|OtherLists], Elem, Count).

count([[]|OtherLists], Elem, Count) :-            #Head sublist is an empty list
    count(OtherLists, Elem, Count).

现在，如果我使用以下内容查询谓词:

Now that if I query the predicate with the following:

count([[1,2,3],[4,1,5],[4,6,1]], 1, X).

count([[1,2,3],[4,1,5],[4,6,1]], 1, X).

它返回 X = 3，这是正确的，但如果我继续查询，它也会说假".

it returns X = 3, which is correct, but it will also say 'false' if I continue with the query.

所以它正确计算元素，但我不能在其他谓词中使用这个谓词，因为它最终返回 FALSE.

So it counts elements correctly, but I cannot use this predicate inside other predicates since it eventually returns FALSE.

我做错了什么?

推荐答案

当 Prolog 在寻找解决方案的过程中遇到选择点"(代码中可以回过头来寻求更多可能解决方案的地方)时，它将显示解决方案并提示您提供更多可能的解决方案.如果没有找到，则显示false".这不是您的逻辑中的任何错误.这是 Prolog 的工作方式.

When Prolog encounters a "choice point" (a place in the code where it can come back to seek more possible solutions) in the process of finding a solution, it will show the solution and prompt you for more possible solutions. If it finds no more, it displays "false". This is not any kind of error in your logic. It's the way Prolog works.

删除选择点并不总是可取的.这取决于您对谓词的目标是什么.使用切割去除选择点的危险在于，选择点可能是通往有效替代解决方案的路径，而切割会阻止您的程序找到这些解决方案.

It is not always desirable to remove the choice point. It depends upon what your goals are for the predicate. The danger in removing choice points using cuts is that the choice point may be a path to valid alternative solutions, and the cut prevents your program from finding those solutions.

让我们尝试在您的答案中使用新提议的削减来更新您的程序:

Let's try your updated program with the new proposed cut in your answer:

| ?- count([[1,2,3],[4,1,5],[4,6,1]], 1, X).

X = 3

yes
| ?- count([[1,2,1,3],[4,1,5],[4,6,1]], 1, X).

X = 4

yes
| ?- count([[1,2,1,3],[4,1,5],[4,6,1],[1]], 1, X).

X = 5

到目前为止，一切都很好.这些看起来像是完整且正确的答案.我相信只要第一个参数完全绑定没有变量，您的额外剪切(包括您的原始剪切)将产生正确的答案.让我们尝试一个更有趣的查询:

So far, so good. These look like complete and correct answers. I believe your additional cut (and including your original cut) will yield a correct answer as long as the first argument is fully bound with no variables. Let's try a more interesting query:

2 ?- count([[A,2,B],[C,1,D]], 1, X).
A = B, B = C, C = D, D = 1,
X = 5.

3 ?-

谓词找到了一种解决方案.然而，不是还有更多吗?这个呢?

The predicate found one solution. However, aren't there more? What about this one?

A = _ % something other than 1
B = C, C = D, D = 1,
X = 4.

这也是一个正确的解决方案，但谓词找不到它.

This would be a correct solution as well, but the predicate fails to find it.

另外，这个查询怎么样?

Also, what about this query?

2 ?- count([[1,2,1,3],[4,1,5],[4,6,1],[1]], E, X).
E = 1,
X = 5.

3 ?-

同样，只找到了一种解决方案.但不是还有更多吗?E = 4 和 X = 2 怎么样?

Again, only one solution found. But aren't there more? What about E = 4 and X = 2?

如果我们从原始谓词中删除所有削减以尝试获得所有正确的解决方案，那么我们也会得到不正确的解决方案:

If we remove all of the cuts from the original predicate in an attempt to get all of the correct solutions, then we get incorrect solutions as well:

2 ?- count([[1,2],[3,1,4],[1]], 1,X).
X = 3 ;
X = 2 ;
X = 2 ;
X = 1 ;
X = 2 ;
X = 1 ;
X = 1 ;
X = 0 ;
false.
2 ?- count([[1,2,1,3],[4,1,5],[4,6,1],[1]], E, X).
E = 1,
X = 5 ;
E = 1,
X = 4 ;
E = 1,
X = 3 ;
...

因此，如果需要更多通用性，则需要构建更有效的解决方案.

So if more generality is desired, a more effective solution needs to be constructed.

count_occurrences_lol([], _, 0).
count_occurrences_lol([List|Lists], X, Count) :-
    count_occurrences(List, X, C1),        % Count occurrences in this list
    count_occurrences_lol(Lists, X, C2),   % Count occurrences in remaining sublists
    Count is C1 + C2.                       % Total the counts

count_occurrences([], _, 0).
count_occurrences([X|Xs], X, Count) :-
    count_occurrences(Xs, X, C1),
    Count is C1 + 1.
count_occurrences([X1|Xs], X, Count) :-
    dif(X1, X),
    count_occurrences(Xs, X, Count).

现在我们得到以下内容:

Now we get the following:

3 ?- count_occurrences_lol([[1,2],[3,1,4],[1]], 1,X).
X = 3 ;
false.

正如预期的那样，只有一种解决方案.以及以下内容:

Just one solution, as expected. And the following:

5 ?- count_occurrences_lol([[A,2,B],[C,1,3]], 1, X).
A = B, B = C, C = 1,
X = 4 ;
A = B, B = 1,
X = 3,
dif(C, 1) ;
A = C, C = 1,
X = 3,
dif(B, 1) ;
A = 1,
X = 2,
dif(B, 1),
dif(C, 1) ;
B = C, C = 1,
X = 3,
dif(A, 1) ;
B = 1,
X = 2,
dif(A, 1),
dif(C, 1) ;
C = 1,
X = 2,
dif(A, 1),
dif(B, 1) ;
X = 1,
dif(A, 1),
dif(B, 1),
dif(C, 1) ;
false.

3 ?- count_occurrences_lol([[1,2,1,3],[4,1,5],[4,6,1],[1]], E, X).
E = 1,
X = 5 ;
E = 2,
X = 1 ;
E = 3,
X = 1 ;
E = 4,
X = 2 ;
E = 5,
X = 1 ;
E = 6,
X = 1 ;
X = 0,
dif(E, 1),
dif(E, 1),
dif(E, 6),
dif(E, 4),
dif(E, 5),
dif(E, 1),
dif(E, 4),
dif(E, 3),
dif(E, 1),
dif(E, 2),
dif(E, 1).

4 ?-

如预期的几种可能的解决方案.

Several possible solutions as expected.

这篇关于Prolog:为什么我的谓词返回 false?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！