Prolog如何实现可回溯的partstr/3谓词以查找指定长度连续子列表

我们可以把连续子列表的提取拆分为两个独立的列表操作逻辑，用递归实现非常直观：

• 第一步：从输入列表中取任意后缀（通过回溯可以得到所有可能的后缀）
• 第二步：从该后缀中提取长度为L的前缀，这个前缀就是符合要求的连续子列表A

步骤1：实现后缀提取谓词 #

我们先定义递归谓词suffix/2，用来返回输入列表的所有可能后缀：

% 输入列表本身就是它的一个后缀
suffix(Suffix, Suffix).
% 切掉输入列表的第一个元素，剩余子列表的后缀也是原列表的后缀
suffix(Suffix, [_|Tail]) :-
    suffix(Suffix, Tail).

调用示例：?- suffix(S, [1,2,3]). 会依次返回S=[1,2,3]、S=[2,3]、S=[3]。

步骤2：实现指定长度的前缀提取谓词 #

再定义递归谓词prefix/3，用来提取列表前L个元素作为前缀：

% 长度为0的前缀是空列表
prefix([], 0, _).
% 递归拼接前L个元素
prefix([Head|RestA], L, [Head|RestList]) :-
    L > 0,
    L1 is L - 1,
    prefix(RestA, L1, RestList).

调用示例：?- prefix(A, 2, [1,2,3]). 会返回A=[1,2]。

步骤3：拼接得到partstr/3谓词 #

把上面两个谓词组合，就得到我们需要的partstr/3：

partstr(InputList, L, A) :-
    % 先做参数合法性校验，避免L为负数
    L >= 0,
    suffix(Suffix, InputList),
    prefix(A, L, Suffix).

运行你给出的示例查询：

?- partstr([1,2,3], 2, A).

回溯结果依次为：

A = [1, 2]
A = [2, 3]
false

完全符合要求。如果查询时L未绑定，该谓词也可以返回所有可能的长度和对应的连续子列表。

内容的提问来源于stack exchange，提问作者user1