更新时间:2023-12-04 21:06:58
This logically pure implementation is based on the predicates if_/3
and (=)/3
.
首先,我们构建prefix_of/2
的修订版:
First, we build a reified version of prefix_of/2
:
prefix_of_t([],_,true).
prefix_of_t([X|Xs],Zs,T) :-
prefix_of_t__aux(Zs,X,Xs,T).
prefix_of_t__aux([],_,_,false).
prefix_of_t__aux([Z|Zs],X,Xs,T) :-
if_(X=Z, prefix_of_t(Xs,Zs,T), T=false).
然后,转到主谓词list_sublist_removed/3
:
list_sublist_removed([],[_|_],[]).
list_sublist_removed([X|Xs],[L|Ls],Zs) :-
if_(prefix_of_t([L|Ls],[X|Xs]), % test
(Zs = Zs0, append([L|Ls],Xs0,[X|Xs])), % case 1
(Zs = [X|Zs0], Xs0 = Xs)), % case 2
list_sublist_removed(Xs0,[L|Ls],Zs0).
关于list_sublist_removed/3
的递归子句的一些操作说明:
A few operational notes on the recursive clause of list_sublist_removed/3
:
首先(测试),我们检查[L|Ls]
是否为[X|Xs]
的前缀.
如果存在(情况1),我们将其剥离[X|Xs]
,得到Xs0
,并且未添加任何内容到Zs
.
If it is present (case 1), we strip it off [X|Xs]
yielding Xs0
and add nothing to Zs
.
如果不存在(情况2),我们将X
剥去[X|Xs]
并将X
添加到Zs
.
If it is absent (case 2), we strip X
off [X|Xs]
and add X
to Zs
.
我们递归[X|Xs]
的其余部分,直到没有其他项目要处理为止.
We recurse on the rest of [X|Xs]
until no more items are left to process.
继续进行一些查询!
Onwards to some queries!
您在问题中给出的用例:
The use case you gave in your question:
?- list_sublist_removed([1,2,3,4,1,2,5,6,1,2,1],[1,2],L).
L = [3,4,5,6,1]. % succeeds deterministically
两个查询试图找到已删除的子列表:
Two queries that try to find the sublist that was removed:
?- list_sublist_removed([1,2,3,4,1,2,5,6,1,2,1],Sub,[ 3,4,5,6,1]).
Sub = [1,2] ? ;
no
?- list_sublist_removed([1,2,3,4,1,2,5,6,1,2,1],Sub,[1,3,4,5,6,1]).
no
接下来,让我们在此查询中找到一个合适的Ls
:
?- list_sublist_removed(Ls,[1,2],[3,4,5,6,1]).
% a lot of time passes ... and nothing happens!
不终止!这是不幸的,但在期望之内,因为解决方案集是无限的.但是,通过先验约束Ls
的长度,我们可以获得所有预期结果:
Non-termination! This is unfortunate, but within expectations, as the solution set is infinite. However, by a-priori constraining the length of Ls
, we can get all expected results:
?- length(Ls,_), list_sublist_removed(Ls,[1,2],[3,4,5,6,1]).
Ls = [ 3,4,5,6,1] ?
; Ls = [1,2, 3,4,5,6,1] ?
; Ls = [3, 1,2, 4,5,6,1] ?
; Ls = [3,4, 1,2, 5,6,1] ?
; Ls = [3,4,5, 1,2, 6,1] ?
; Ls = [3,4,5,6, 1,2, 1] ?
; Ls = [3,4,5,6,1, 1,2 ] ?
; Ls = [1,2, 1,2, 3,4,5,6,1] ? ...