1

这是从给定列表中删除或删除元素的代码：

remove_elem(X,[],[]). 
remove_elem(X,L1,L2) :-
   L1 = [H|T],
   X == H,
   remove_elem(X,T,Temp),
   L2 = Temp. 
remove_elem(X,L1,L2) :- 
   L1 = [H|T],
   X \== H, 
   remove_elem(X,T,Temp),
   L2 = [H|Temp].

如何修改它，以便我可以从列表中删除每个出现的子列表？

当我试图将一个列表放入一个元素时，它只会删除该元素并且只删除一次。

应该是这样的：

?- remove([1,2],[1,2,3,4,1,2,5,6,1,2,1],L).   
L = [3,4,5,6,1].                        % expected result
4

3 回答 3

1

这种逻辑上纯粹的实现基于谓词if_/3和(=)/3。

首先，我们构建了一个具体化的版本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：

  1. 首先（测试），我们检查是否[L|Ls]是[X|Xs].

  2. 如果它存在（案例 1），我们将其从[X|Xs]yielding中剥离，Xs0并且不添加任何内容到Zs.

  3. 如果它不存在（情况 2），我们剥离X并[X|Xs]添加X到Zs.

  4. 我们对其余的进行递归，[X|Xs]直到没有更多的项目需要处理。

接下来是一些查询！

  1. 您在问题中给出的用例：

    ?- list_sublist_removed([ 1,2 ,3,4, 1,2 ,5,6,1,2,1],[ 1,2 ],L)。
L = [3,4,5,6,1]。% 确定性地成功

  2. 尝试查找已删除子列表的两个查询：

    ?- list_sublist_removed([ 1,2 ,3,4, 1,2 ,5,6,1,2,1],Sub,[ 3,4,5,6,1])。
子 = [ 1,2 ] ？;
不

?- list_sublist_removed([1,2,3,4,1,2,5,6,1,2,1],Sub,[1,3,4,5,6,1])。
不

  3. Ls接下来，让我们在这个查询中 找到一个合适的：

       
?- list_sublist_removed(Ls,[1,2],[3,4,5,6,1])。
% 很多时间过去了……什么也没发生！

    不终止！这是不幸的，但在预期之内，因为解决方案集是无限的。但是，通过先验约束 的长度Ls，我们可以获得所有预期的结果：

    ?- 长度（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] ？...
于 2015-04-04T18:07:37.887 回答
1

受@CapelliC 实现的启发，我基于以下代码编写了以下代码 and_t/3：

append_t([]    ,Ys,Ys, true).
append_t([X|Xs],Ys,Zs,Truth) :-
   append_aux_t(Zs,Ys,Xs,X,Truth).

append_aux_t([]    ,_ ,_ ,_,false).     % aux pred for using 1st argument indexing
append_aux_t([Z|Zs],Ys,Xs,X,Truth) :-
   and_t(X=Z, append_t(Xs,Ys,Zs), Truth).

一个append_t/4目标可以代替两个prefix_of_t/3目标append/3。

正因为如此，实现list_sublist_removed/3变得比以前简单一点：

list_sublist_removed([]    ,[_|_] ,[]).
list_sublist_removed([X|Xs],[L|Ls],Zs) :-
    if_(append_t([L|Ls],Xs0,[X|Xs]),
        (Zs =    Zs0 , Xs1 = Xs0),
        (Zs = [X|Zs0], Xs1 = Xs)),
    list_sublist_removed(Xs1,[L|Ls],Zs0).

还是确定性？

?- list_sublist_removed([1,2,3,4,1,2,5,6,1,2,1],[1,2],L).
L = [3,4,5,6,1].

是的！下面的呢？

?-  list_sublist_removed([1,2,3,4,1,2,5,6,1,2,1],X,[3,4,5,6,1]).
X = [1,2] ;                             % succeeds with useless choice-point
false.

没有。所以仍有改进的空间......

于 2015-07-09T03:00:21.353 回答
0

<rant>

这么多年我研究 Prolog，仍然值得一些惊喜......当你知道列表库并且你有一个特定的模式（比如你发布的那个例子）时，你的问题很容易解决。但概括起来也可能相当复杂，我不清楚@repeat 提出的基于@false 建议（if_/3 和朋友）的方法是否可以“移植”到普通的旧Prolog（a-la Clocksin -Mellish，只是说）。

</rant>

一个不太容易找到的解决方案，基于老式的 Prolog

list_sublist_removed(L, S, R) :-
    append([A, S, B], L),
    S \= [],
    list_sublist_removed(B, S, T),
    append(A, T, R),
    !
    ; L = R.

一些测试：

?- list_sublist_removed([1,2,3,4,1,2,5,6,1,2,1],[1,2],L).
L = [3, 4, 5, 6, 1].

?- list_sublist_removed([1,2,3,4,1,2,5,6,1,2,1],X,[3, 4, 5, 6, 1]).
X = [1, 2].

?- length(X,_), list_sublist_removed(X,[1,2],[3, 4, 5, 6, 1]).
X = [3, 4, 5, 6, 1] ;
X = [3, 4, 5, 6, 1, 2, 1] ...
于 2015-07-04T13:11:35.663 回答