如何在prolog中从列表中删除一个列表？

Question

我希望在Prolog中实现以下问题： 给定L1=[1,2,3,4]和L2=[2,3,4]，调用名为remove_list(L1,L2,L)的函数将从L1中删除L2，因此L将为[1]。 但是，如果第二个列表的元素不按照L1中的顺序排列，或更准确地说，第二个列表不是第一个列表的子集，则不会删除任何内容。 例如L1=[1,2,3,4,5] 和 L2=[2,3,6] 或 L2=[2,6] 或 L2=[4,3,2] 都会导致L=[1,2,3,4,5]。 非常感谢您提供的任何帮助。

- Alvi

Answer 1

使用递归可以构建谓词remove_list/3，这是在Prolog中处理列表时非常有用的工具。

remove_list([], _, []).
remove_list([X|Tail], L2, Result):- member(X, L2), !, remove_list(Tail, L2, Result). 
remove_list([X|Tail], L2, [X|Result]):- remove_list(Tail, L2, Result).

咨询：

?- remove_list([4,5,1,6,3], [1,4,7], L).
L = [5, 6, 3].

这个想法是将原始列表“L1”中的每个元素复制到最终列表“L”中，除非该元素是第二个列表“L2”的成员。
你的基本条款是停止条件，当原始列表“L1”为空时，在这种情况下忽略列表“L2”，结果始终为相同的空列表。（你不能从空列表中删除任何内容）。
第二个条款是，如果列表“L1”头部的元素是列表“L2”的成员，则不将该元素复制到最终列表“L”中，并使用列表“L”的尾部进行递归调用。
最后一个条款是将列表“L1”头部的元素复制到最终列表“L”中，并使用该列表的尾部进行递归调用。我们不需要goal member/2，因为我们在前一个条款中使用了cut。
编辑： 如果您想要从列表“L1”中删除包含在“L2”列表中的项目（无论顺序如何），请使用Lurker's solution或此其他解决方案。

remove_list(L, [], L):- !.
remove_list([X|Tail], [X|Rest], Result):- !, remove_list(Tail, Rest, Result).
remove_list([X|Tail], L2, [X|Result]):- remove_list(Tail, L2, Result).

这个新的解决方案会考虑列表"L2"中元素的顺序，但并不是严格意义上的顺序，也就是说，它可以穿插在原始列表"L1"中，这并不违反"L2"是"L1"子集的概念。

[2,4]是[1,2,3,4,5,6]集合的子集，但[2,4,7]不是：

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

?- remove_list([1,2,3,4,5,6], [4,2], L).
false.

?- remove_list([1,2,3,4,5,6], [2,4,7], L).
false.

现在，考虑到我们希望得到原始集而不是消极响应，在原始集中的任何一个元素可以被删除的情况下，我们使用辅助谓词：

rm_subset(L1, L2, L):-  remove_list(L1, L2, L),!.
rm_subset(L1, L2, L1).

咨询：

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

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

- Yasel

Answer 2

另一个可能的解决方案是使用delete/3谓词：

remove_elements(L, [H|T], R) :-
    delete(L, H, R1),
    remove_elements(R1, T, R).
remove_elements(L, [], L).

| ?- remove_elements([4,5,1,6,3], [1,4,7], L).

L = [5,6,3] ? ;

no
| ?-

编辑 我刚刚意识到我完全误读了这个问题。如果您希望按照所述保持“已删除”列表的顺序，则Boris'的评论对于append/3是正确的。append(A, B, C)表示如果您取A并附加B，则会得到C，并保留元素顺序。

因此，为了重新阐述所请求的解决方案：

remove_elements(L1, L2, L) :-
    append(A, B, L1),
    append(C, L2, A),
    append(C, B, L).

- lurker

---

现在我明白我也犯了同样的错误。我应该更仔细地阅读，我甚至认为Boris是错的，因为使用append/3不会删除元素，如果它们与原始列表中的顺序不同。我可能应该编辑我的答案... - Yasel

@Yasel - 如果你对原问题有其他解决方案的变体，我认为你应该更新你的答案并加入这个变体。 - lurker

我刚刚添加了一个新的解决方案，考虑到要删除的元素列表中的元素在原始列表中的顺序相同，但考虑到它们可能是交错的。 - Yasel

Answer 3

一般来说，如果你只想从另一个列表中删除多个元素，你可以直接使用：

subtract(+Set, +Delete, -Result)

其中set是一个无序列表，可能包含一些重复元素，而delete则是我们想要从set中删除的元素列表。

例如：

subtract([1,3,5,6,4,2,3], [1,2,3], R).
R = [5, 6, 4].

- ibda

---

请注意，subtract/3不是标准谓词。它作为库谓词在某些Prolog系统中可用。 - Paulo Moura