Как я могу удалить каждое вхождение подсписка из списка в прологе?

Question

Это код для удаления или удаления элемента из данного списка:

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

Answer 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.

Нету. Так что еще есть возможности для потенциального улучшения...

Answer 2

Эта логически чистая реализация основана на предикатах 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] получая Xs0 и ничего не добавить к Zs,

3. Если он отсутствует (случай 2), мы удаляем X от [X|Xs] и добавить X в Zs,

4. Мы остаемся на остальной части [X|Xs] пока больше не осталось предметов для обработки.

---

Вперед к некоторым запросам!

1. Вариант использования, который вы задали в своем вопросе:

   ?- list_sublist_removed ([1,2,3,4,2,2,5,6,1,2,1], [ 1,2 ], L).
   L = [3,4,5,6,1]. % преуспевает детерминистически
   

2. Два запроса, которые пытаются найти удаленный подсписок:

   ?- list_sublist_removed ([1,2,3,4,2,2,5,6,1,2,1], Sub [3,4,5,6,1]).
   Sub = [ 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]?...
   

Answer 3

<rant>

Столько лет я изучаю Пролог, но все же он заслуживает некоторых сюрпризов... вашу проблему довольно просто решить, когда вы знаете библиотеку списков и у вас есть определенный режим (например, тот, который вы опубликовали в качестве примера). Но также может быть довольно сложным для обобщения, и мне неясно, можно ли "перенести" подход, предложенный @repeat, основанный на предложении @false (if_/3 и friends), на простой старый Prolog (а-ля Clocksin) -Мелкий, просто чтобы сказать).

</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] ...