Prolog - 第一个列表是第二个列表的子列表？

Question

例如：

isin([1,2,3], [1,0,1,2,3,0])

将产生 true，因为 123 位于 101230

我编写了以下代码：

isin([AH|AT],[AH|AT]).

isin([AH|AT],[BH|BT]):- AH = BH, isin(AT,BT), isin([AH|AT],BT).

似乎不起作用。尽量不要使用任何内置函数，顺便说一句，Prolog 有一个内置的 sublist(L1, L2) 函数。

如何使用 SWI-Prolog 编写针对内置函数的查询？我尝试直接编写：

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

但它返回一个未定义的过程错误。

另外，是否可以查看内置函数的编码方式以及如何编码？

Answer 1

sublist( [], _ ).
sublist( [X|XS], [X|XSS] ) :- sublist( XS, XSS ).
sublist( [X|XS], [_|XSS] ) :- sublist( [X|XS], XSS ).

Answer 2

如果您想

my_sublist( [2,3,4], [1,2,3,4,5] ) 

...成功，但

my_sublist( [1,3,5], [1,2,3,4,5] ) 

...失败，您可能需要考虑

my_sublist( Sublist, List ) :-
    append( [_, Sublist, _], List ).

注意，如果您将变量作为子列表传递，回溯将为您提供 List 的所有可能子列表的全面集合，但这将在一般包括空列表的多次重复（因为空列表可以在追加操作中与它们前面和后面的所有其他子列表组合）。

Answer 3

因为这似乎是家庭作业，所以我只会给您一些提示：

• 您似乎错过了空列表是另一个列表的子列表的情况。

• 您将“子列表从这里开始”和“子列表稍后开始”这两种情况混合到一个子句中。

  您

• 看来子列表的元素在较大列表中应该是连续的。为此，您需要两个谓词。本质上，您必须记住，当您拆开列表时，子列表已经开始。

没有内置的 sublist/2，只有一个 sublist/3 可以做不同的事情（带有谓词的过滤列表）。

Answer 4

使用 member 的另一个实现是：

sublist([],_).
sublist([X|Xs],Y) :- member(X,Y) , sublist(Xs,Y).

如果在列表中找到该元素，member/2 返回 true

member(X,[X|_]).
member(X,[_|Ys]):-member(X,Ys).

Answer 5

sublist(S, L) :-length(S, N),
                length(L, N1),
                N2 is N1 - N,
                length(P, N2),
                append( _ , S, P), 
                append(P, _ , L).

为了避免失败情况下的堆栈溢出，我们必须确定列表P的大小。

Answer 6

sublist([],[],_):-!.
sublist(_,[],_):-!.

sublist([H1|T1],[H2|T2],LV):-
H1 = H2,!,
sublist(T1,T2,LV).

sublist([H1|T1],[H2|_],LV):-
not(H1 = H2),
sublist(T1,LV,LV).

如果您尝试这些查询：

?-sublist([1,2,3,4,5],[1,2,3],[1,2,3]).
TRUE

?-sublist([1,2,3,4,5],[1,2,4],[1,2,4]).
FALSE

Answer 7

通过对 ДМИТРИЙ МАЛИКОВ 的答案进行一些修改，这是有效的，

preList([], L).
preList([H_s|T_s], [H_s|Tail]):-
    preList(T_s, Tail).

subList([H_s|T_s], [H_s|Tail]):-
    preList(T_s, Tail).

subList([H_s|T_s], [H_s|Tail]):-
    subList([H_s|T_s], Tail).
    
subList(Sub, [_|Tail]):-
    subList(Sub, Tail).

本质上，寻找子的第一个元素之间的匹配-list 和使用 subList 过程的主列表。当发生匹配时，转到 preList 过程并检查这是否是列表其余部分的前缀。如果是这样，决议就成功了。

如果没有，请返回并继续比较列表的其余部分以查找第一个元素匹配。

Answer 8

% prefix: Is the first list the prefix of the second?
% True if the two have the same head and the tail of the first
% is the prefix of the tail of the second.
prefix([X|T], [X|R]) :- prefix(T, R).
% True if the first list is the empty list.
prefix([], _).

% sublist: Is the first list a sublist of the second list?
% True if the two lists start with the same element and
% the tail of the first is a prefix of the tail of the second.
sublist([X|T], [X|R]) :- prefix(T, R), !.
% True if the first list is a sublist of the tail of the second.
sublist(L, [_|R]) :- sublist(L, R).
% True if the first list is the empty list.
sublist([], _).