[ H | 怎么做？ _ ] 和 [ _ | T ] 在谓词中起作用？

Question

我仍在学习 Prolog，我偶然发现了这段代码，我不太清楚自己是否理解正确。

代码：

% Takes the spiders friends and returns a list with persons who don't know each other.
getConspirators( [], Res, Res).

getConspirators( [H|T], CConspirators, Res):-
  append( [H|T], CConspirators, PK),
  knowsAtleastOne( PK),
  % Gets all the friends of the possible conspirator H.
  allFriends( H, PFriends),
  subtract( T, PFriends, Pprim),
  getConspirators( Pprim, [H|CConspirators], Res).

getConspirators( [_|T], CConspirators, Res) :-
  getConspirators( T, CConspirators, Res).

% Checks if any person Y or Y's friends know anybody in PK.
knowsAtleastOne( PK):-
    forall( person(Y), (memberchk(Y,PK) ; friendCons(Y,PK)) ).

% Checks if a person X's friends know any of the conspirators.
friendCons( X, Conspirators):-
    friend( X, Y),
    memberchk( Y, Conspirators),
    !.

（这不是整个程序，只是其中的一小段）

我不确定我是否理解了 getConspirators( [H|T], CConspirators, Res) :- 和 getConspirators( [_|T], CConspirators, Res) :- 部分 getConspirators 谓词。他们看起来几乎一样！现在，我知道“_”符号的意思是“字面上的任何值”（AKA Prolog 不关心它是什么值）。但是Prolog如何通过代码知道在运行时选择哪种情况呢？我的理论是，当且仅当 getConspirators( [H|T], CConspirators, Res) :- 案例在某个地方失败（returns false）时，Prolog 才会运行 getConspirators( [_|T], CConspirators, Res) :- 案例。我理解正确吗？

Answer 1

这里涉及三个要素：回溯、统一和列表符号。我将用一个更简单的例子来解释这三个：

moon(europa).
moon(ganymede).

planet(jupiter).
planet(saturn).

我们知道木卫二和木卫三是（木星的）两个卫星，木星和土星是行星。当我们查询已知的行星时，我们写：

?- planet(X).
X = jupiter ;  % type ; for the next answer
X = saturn.    % there's no more answer, hence .

当 prolog 寻找适合变量被相应替换的查询的规则头时，就会发生统一。例如，没有使 moon(X) = planet(Y) 相等的替换，但有一个使 planet(jupiter) = planet(X) 相等的替换，即 X=jupiter。这就是您获得第一个解决方案的方式。对于第二种解法，Prolog需要统一第二个规则头，即planet(saturn) = planet(X)。因为这是在第一个选项被完全枚举之后完成的，所以我们称之为回溯。

现在我们可以专注于（链接的）列表。一个列表要么是空的 ([])，要么它有第一个元素 X 放在尾列表 Xs ([X|Xs]) 前面。 Prolog 对列表 [X | [Y | [] ]] 也有更好的表示法，即 [X,Y]。在内部，它们是相同的。当我们现在要收集星体列表objects时，我们可以制定如下三个规则：

astral_objects([]).        % The empty list is a list of astral objects.

astral_objects([X|Xs]) :-  % The list [X | Xs] is a list of astral objects if...
    moon(X),               % ... its first element X is a moon
    astral_objects(Xs).    % ... and the remaining list Xs is a list of astral objects

astral_object([X|Xs]) :-   % Likewise for planets
    planet(X),
    astral_objects(Xs).

当我们为 two-element 列表制定查询时，我们得到 objects:

的所有组合

?- astral_object([A,B]).
A = B, B = europa ;
A = europa,
B = ganymede ;
A = europa,
B = jupiter ;
A = europa,
B = saturn ;
A = ganymede,
B = europa ;
A = B, B = ganymede ;
A = ganymede,
B = jupiter
%...

通过统一，只有规则 2 和 3 适用。在这两种情况下，我们都有 astral_objects([X|Xs]) = astral_objects([A,B])。请记住，对于 [A|[B]]，[A,B] 是 shorthand，对于 X=A 和 Xs=[B]。 body 的第一条规则将 X 与相应的 moon/planet 统一起来，递归步骤描述了尾部。同样，我们统一 astral_objects([X|Xs]) = astral_objects([B])，导致 X=B 和 Xs = []。现在递归步骤将只匹配空列表的终端情况，我们已经完全探索了这条路。

现在如果我们寻找一个任意的星体列表会发生什么 objects？

?- astral_object(Xs).
Xs = [] ;
Xs = [europa] ;
Xs = [europa, europa] ;
Xs = [europa, europa, europa] ;
Xs = [europa, europa, europa, europa] ;
Xs = [europa, europa, europa, europa, europa] 
%... does not terminate

头 astral_objects(Xs) 匹配所有三个身体。返回终端案例的替代后，它一遍又一遍地下降到第一条规则。由于列表的长度不受限制，因此在尝试第三条规则之前有无数种解决方案可供寻找。为避免这种情况，您可以在尝试使列表满足谓词之前公平地枚举列表：

?- length(Xs,_), astral_object(Xs).
Xs = [] ;
Xs = [europa] ;
Xs = [ganymede] ;
Xs = [jupiter] ;
Xs = [saturn] ;
Xs = [europa, europa] ;
Xs = [europa, ganymede] ;
Xs = [europa, jupiter] ;
Xs = [europa, saturn] ;
Xs = [ganymede, europa]
%...

它仍然没有终止，但您会看到列表的长度递增，因此种类繁多。

Answer 2

问的问题是"the getConspirators([H|T], CConspirators, Res) :- _body_ and the getConspirators([_|T], CConspirators, Res) :- _body_ parts ... My theory is that Prolog runs the getConspirators([_|T], CConspirators, Res) :- case if and only if the getConspirators([H|T], CConspirators, Res) :- case fails (returns false)"

你的理论是错误的。他们两个都会匹配。唯一的区别是，对于 getConspirators([H|T], CConspirators, Res) :- _body_ 的情况，列表的第一个元素将作为名为 H 的变量在 body 中可用。但是对于 getConspirators([_|T], CConspirators, Res) :- _body_，列表的第一个元素将无法在 body 中作为命名变量使用。如本代码所示，解释 _ 含义的一种好方法是 "a variable that I do not care to refer to later" .

[ H | 怎么做？ _ ] 和 [ _ | T ] 在谓词中起作用？

How do [ H | _ ] and [ _ | T ] in predicates work?

predicate

prolog

clause