Prolog中的子列表谓词

Question

Prolog中的子列表谓词

recursionprologlogic

4

我正在尝试在Prolog中定义一个谓词sublist(X,Y)，当列表X的元素按照与X中相同的顺序出现在列表Y中时为真。

我的方法是取X的头部，在Y中找到第一个实例，然后在该实例之前将列表切断，然后重复这个过程直到尾部等于空列表。

我已经编写了帮助谓词cut(X,Y,Z)，如果Z是在列表Y中切掉X之前的所有内容所得到的列表，则为真。

我的代码如下：

cut(_,[],[_|_]) :- false.
cut(X,[H|T],[H|T]) :- X = H, !.
cut(X,[_|T],Y) :- cut(X,T,Y).

sublist([],[]).
sublist([],[_|_]).
sublist([A|B],C) :- cut(A,C,Z), sublist(B,Z).

当我查询时

?- sublist(L,[1,2,3]).

与其给出[1,2,3]的所有子列表，Prolog会给我以下输出：

L = [] ;
L = [1] ;
L = [1, 1] ;
L = [1, 1, 1] ;
L = [1, 1, 1, 1] ;
L = [1, 1, 1, 1, 1] ;
L = [1, 1, 1, 1, 1, 1] ;
L = [1, 1, 1, 1, 1, 1, 1] ;
L = [1, 1, 1, 1, 1, 1, 1, 1] ;
L = [1, 1, 1, 1, 1, 1, 1, 1, 1] ;
L = [1, 1, 1, 1, 1, 1, 1, 1, 1|...] ;
L = [1, 1, 1, 1, 1, 1, 1, 1, 1|...] ;
L = [1, 1, 1, 1, 1, 1, 1, 1, 1|...]

我没看出我的错误在哪里，有人能给我指出来吗？

- Kermit

1

你不需要规则 cut(_,[],[_|_]) :- false. 只要它不存在，查询看起来像 cut(_,[],[_|_]). 的将会失败，因为它不匹配一个成功的规则。你尝试过使用 trace 吗？或者你只是尝试测试 cut/3 本身吗？你创建 cut/3 而不是使用 select/3 有什么原因吗？ - lurker

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Willem Van Onsem · Accepted Answer

简短回答: 如果 cut/3 找到一个元素，它不会弹出列表。

第一个回答 L = []. 是第二个子句的结果。现在，下一个答案是通过最后一个子句生成的。所以发生了以下情况：

sublist(A,[1,2,3]) :- % C = [1,2,3]
    cut([A|B],[1,2,3],[H|T]) :- % H = 1, T = [2,3], Z = [1,2,3]
        A = H, % A=1
        !.
    sublist(B,<b>[1,2,3]</b>).

因为cut/3的第二个子句被触发，所以第二个和第三个参数是等价的，因此cut/3不会从列表中“弹出”任何元素。

解决这个问题并保证进展的一种方法是使用以下方式从列表中弹出元素：

cut(_,[],[_|_]) :- false.
cut(<b>H</b>,[H|T],<b>T</b>) :-
    !.
cut(X,[_|T],Y) :-
    cut(X,T,Y).

我还顺便将从句中的X替换为H，使其更加优雅。现在生成的代码如下：

?- sublist(L,[1,2,3]).
L = [] ;
L = [1] ;
L = [1, 2] ;
L = [1, 2, 3] ;
false.

请注意，答案并不生成所有的列表：例如L = [2,3]也是一个有效的答案。这不起作用的原因是cut/3有!，因此不允许引入其他元素。您可以使用以下方法解决：

cut(_,[],[_|_]) :- false.
cut(H,[H|T],T).
cut(X,[_|T],Y) :-
    cut(X,T,Y).

现在我们获得：

?- sublist(L,[1,2,3]).
L = [] ;
L = [1] ;
L = [1, 2] ;
L = [1, 2, 3] ;
L = [1, 3] ;
L = [2] ;
L = [2, 3] ;
L = [3] ;
false.

然而，您可以非常优雅地解决问题，而无需使用任何帮助谓词。我们可以首先构建一个验证/创建列表的谓词:

list([]).
list([_|T]) :-
    list(T).

接下来我们说明，如果X为空，则您并不关心右侧的列表是什么类型：

sublist([],L) :-
    list(L).

最后，如果X不为空，我们需要在某个地方获取X的头部HX。如果我们找到了它，我们可以选择“接受”它并弹出两个列表，或者我们可以决定寻找另一个HX，例如：

sublist([HX|TX],[HX|TY]) :-
    sublist(TX,TY).
sublist(X,[_|TY]) :-
    X = [_|_],
    sublist(X,TY).

最后一条语句中的 X = [_|_] 不是必需的，但它可以防止与 sublist([], X) 子句生成重复结果。

或者将其整合在一起：

list([]).
list([_|T]) :-
    list(T).

sublist([],L) :-
    list(L).
sublist([HX|TX],[HX|TY]) :-
    sublist(TX,TY).
sublist(X,[_|TY]) :-
    X = [_|_],
    sublist(X,TY).

这将生成：

?- sublist(L,[1,2,3]).
L = [] ;
L = [1] ;
L = [1, 2] ;
L = [1, 2, 3] ;
L = [1, 3] ;
L = [2] ;
L = [2, 3] ;
L = [3] ;
false.

或者：

?- sublist([1,2,3],L).
L = [1, 2, 3] ;
L = [1, 2, 3, _G2440] ;
L = [1, 2, 3, _G2440, _G2443] ;
L = [1, 2, 3, _G2440, _G2443, _G2446] ;
L = [1, 2, 3, _G2440, _G2443, _G2446, _G2449] ;
L = [1, 2, 3, _G2440, _G2443, _G2446, _G2449, _G2452] ;
L = [1, 2, 3, _G2440, _G2443, _G2446, _G2449, _G2452, _G2455] ;
L = [1, 2, 3, _G2440, _G2443, _G2446, _G2449, _G2452, _G2455|...] ;

或者：

?- sublist([1,2,3],[1,2,4,5,3,6]).
true ;