具有 if-the-else 与多个子句谓词的单个子句

Question

假设我想实现一个谓词，该谓词"返回"列表列表共享的所有元素的列表。

我可以将其实现为一个子句(对于逻辑编程来说看起来有点难看)：

shared_members(Members, Lists) :-
Lists = [] -> 
Members = []
; findall(M, (maplist(member(M), Lists)), Members).

或作为一组子句：

shared_members([], []). % possibly adding cut here to increase effciency
shared_members(Members, Lists) :-
findall(M, (maplist(member(M), Lists)), Members).

哪种实现被认为更有效？ 我知道这取决于Prolog的实现，但也许对这些案例的效率有一个普遍的立场。

Answer 1

在这种情况下，您甚至不需要第一个子句shared_member([], [])。如果Lists = []，findall/3调用将导致Members = []。

不过，这个问题仍然很有趣，所以我们暂时忽略这一点。您可以运行一些统计信息来确定时间效率。内存效率差异可以忽略不计。然而，给出的第二种方法被认为是Prolog中的规范方法。但它们在行为上也不等同。Prolog中的"if-else"，如p1 -> p2 ; p3削减所表示的那样，在评估p1后删除了选择点。相当于p1, !, p2 ; p3.

这就是为什么这很重要。我将使用一个人为的例子(它也不需要两个子句，但说明了这一点)。我将定义一个len/2谓词，如果第一个参数是第二个参数的长度，则该谓词为 true：

len(0, []).
len(N, L) :- length(L, N).

显然，与原始问题的情况一样，此处的第一个子句是多余的，但对于此说明很重要。如果我运行此查询，我会得到以下结果：

| ?- len(N, [a,b,c]).
N = 3
yes
| ?- len(3, L).
L = [_,_,_]
yes
| ?- len(N, L).
L = []
N = 0 ? ;
L = []
N = 0 ? ;
L = [_]
N = 1 ? ;
L = [_,_]
N = 2 ? ;
L = [_,_,_]
N = 3 ?

请注意，如果两个参数都是可变的，它将枚举解决方案。(此外，由于冗余的第一句，其中一个解决方案出现了两次。

让我们使用 "if-else" 重写这个谓词：

len(N, L) :-
(   L = []
->  N = 0
;   length(L, N)
).

我们将运行它：

| ?- len(N, [a,b,c]).
N = 3
yes

目前为止，一切都好。但。。。

| ?- len(3, L).
no
| ?- len(N, L).
L = []
N = 0
yes
| ?-

哎呀！这是完全不同的。发生了什么事？

在第二种方法中，( L = [] -> N = 0 ; length(L, N) )首先尝试统一L和[]。如果L是变量，则成功使用L = []。既然成功了，Prolog就试图统一N = 0。但是在查询len(3, L)中，N已经绑定到 3。所以N = 0失败了，整个子句都失败了。

在这种情况下，使用-> ;构造会大大降低实现的通用性，并在某些调用场景中产生不正确的结果。