4

老实说，我是 Prolog 新手，所以请原谅我的无知。

我有一个简单的谓词来计算列表中原子的出现次数，如下所示：

count(L, B, C) :-
    L = [], C = 0, !;
    L = [H|T], H \= B, count(T, B, C), !;
    L = [H|T], H = B, count(T, B, C1), C is C1 + 1.

以下查询返回正确的结果：

?- count([a, c, g, t], a, C).
C = 1.

?- count([a, c, g, t], c, C).
C = 1.

?- count([a, c, g, t], g, C).
C = 1.

?- count([a, c, g, t], t, C).
C = 1.

但是，如果我试图找到所有可能的解决方案，它只会给出一个。

?- count([a, c, g, t], X, C).
X = a,
C = 1.

我如何得到它来提供所有的解决方案？我虽然它可能与 cut 运算符有关，但删除它似乎也不起作用。

4

4 回答 4

4

削减确实是一个问题：例如尝试最一般的查询

?- count(Ls, L, C).

并看到它只产生一个解决方案，尽管显然应该有无限多，因为第一个参数可以是任意长度的列表。所以首先删除所有削减。另一个问题是(\=)/2，它不是一个真正的关系：只有当它的论点有根据时它才是正确的。代替(\=)/2，使用更通用的谓词dif/2，它在 SWI-Prolog 以及其他系统中可用，并将其参数限制为不同的术语。然后，您的谓词将在各个方向上起作用。

编辑：我扩展了“全方位可用”这一点。考虑以下版本list_term_count/3，它将列表与该列表中术语的出现次数相关联，除了使用dif/2约束：

list_term_count([], _, 0).
list_term_count([L|Ls], L, N) :-
        list_term_count(Ls, L, N0),
        N #= N0 + 1.
list_term_count([L|Ls], E, N) :-
        dif(L, E),
        list_term_count(Ls, E, N).

我们可以以最一般的方式使用它，即不指定所有参数，并获得正确的答案：

?- list_term_count(Ls, E, N).
Ls = [],
N = 0 ;
Ls = [E],
N = 1 .

为了公平地列举所有解决方案，我们可以使用length/2：

?- length(Ls, _), list_term_count(Ls, E, N).
Ls = [],
N = 0 ;
Ls = [E],
N = 1 ;
Ls = [_G167],
N = 0,
dif(_G167, E) .

请注意dif/2作为剩余目标出现的约束，它约束列表的元素与Ewhen Nis不同0。这就是我们如何表达无限的术语集，除了与 不同之外，不受任何其他方式的限制E。

任何其他实例化模式也是可以接受的。例如：

?- list_term_count([a], E, N).
E = a,
N = 1 ;
N = 0,
dif(E, a).

或者例如：

?- list_term_count([X], a, N).
X = a,
N = 1 ;
N = 0,
dif(X, a).

这种普遍性是在程序中使用纯单调谓词的好处之一。使用纯目标还允许我们非常自由地重新排序它们。

于 2013-09-15T00:10:17.190 回答
2

我认为您正在探索 Prolog 的“黑暗面”：聚合。

实际上，您的 count/3 谓词可能是 - 由库（聚合）提供 -

count(L, B, C) :-
    aggregate(count, member(B, L), C).

作为一种基于relational数据模型的语言，我们类似于期待 SQL 提供的常见好处，从更简单的开始：

select count( distinct B ) from L

如果您检查库实现（例如通过），您将体会到将面向“一个元组”的 Prolog执行模型?- edit(aggregate/3).推广到“面向集合”的执行模型所需的复杂性。

于 2013-09-15T06:04:57.513 回答
1

意外的行为来自 Prolog 的统一，它总是试图成功。

读 H \= B作not(H = B). B不受约束时，H = B总会成功，因为统一是可能的，所以not(...)总会失败。结果，递归只会发生在第三个分支中，在B被绑定到之后H。

让我们想象H \= B一个 unbound 会成功B，并且递归发生了。现在，如果再次出现相同的元素H，它可能会被绑定到B这次，这将为您提供每个值的多个结果。例如，count([a,a],X,C)将返回X = a, C = 1. X = a, C = 2.. 当然不是你想要的。

但是，如果我试图找到所有可能的解决方案，它只会给出一个。

?- count([a, c, g, t], X, C). X = a, C = 1.

你会说什么是“所有可能的解决方案”？是无限的值，X其C为零（Protip：try ?- X.）。还是您的意思是列表中的所有值？

您的问题有一个非常简单的解决方案：只需确保在到达B时绑定即可\=。实现这一点的最简单方法是简单地更改谓词的顺序，即将不等式移到末尾。

% count(?List, ?Element, ?Count)
count([], _, 0).
count([E|R], E, C) :-
     count(R, E, C0),
     C is C0+1.
count([F|R], E, C) :-
     count(R, E, C),
     F \= E.

优化留给读者作为练习。

最后一点：在你真正理解它们之前不要使用cuts( !)，大多数时候你无论如何都不需要它们。

于 2013-09-17T12:05:05.777 回答
0

好吧，这似乎奏效了。

base(a).
base(c).
base(g).
base(t).

count(L, B, C) :-
    base(B),
    (
        L = [], C = 0;
        L = [H|T], H = B, count(T, B, C1), C is C1 + 1;
        L = [H|T], H \= B, count(T, B, C)
    ).

这是有道理的，因为 Prolog 没有任何其他方法可以知道我认为 B 的域是什么。我只是很惊讶它没有以原始方式给我“参数没有充分实例化”错误。另外，如果我包括 cut 运算符，它就不起作用，我目前还无法解释。

于 2013-09-14T22:25:49.910 回答