我无法理解函数子集(X，Y)是如何工作的

Question

有人能给我解释一下这段代码吗？我花了几个小时试图理解，但我无法理解。。。

subset([],[]).
subset([X|L],[X|S]) :- subset(L,S).
subset(L, [_|S]) :- subset(L,S).

Answer 1

假设你有一个列表[1,4]，那么有四种可能的解决方案：[1,4]、[1]、[4]和[]，所以如果你调用subset(L, [1,4])，我们得到：

?- subset(L, [1,4]).
L = [1, 4] ;
L = [1] ;
L = [4] ;
L = [].

Prolog谓词为空列表返回一个空列表，这确实是我们可以生成的唯一子列表：

sublist([], []).

对于至少有一个元素X的子列表，每次都有两种可能性：在结果中包括X，或者在结果中不包括X。在这两种情况下，我们在列表的尾部递归。因此，尾部包含其余元素，并且对于这些元素中的每一个，再次存在是否包括这些元素的决策点。

在伪代码中，评估树可能看起来像：

subset(L, [1,4]) :-
subset([1|L], [1|S]) :-
subset([4|L], [1|S]) :-
subset([], []).  % outer L=[1,4]
subset(L, [1|S]) :-
subset([], []).  % outer L=[1]
subset(L, [1|S]) :-
subset([4|L], [1|S]) :-
subset([], []).  % outer L=[4]
subset(L, [1|S]) :-
subset([], []).  % outer L=[]

Answer 2

我们可以(几乎(等效地重写它，将统一性从规则的标题中推出来，使代码的结构更直观：

subset(A,B) :- B=[], A=[].
subset(A,B) :- B=[X |    S], 
A=[X | L], 
subset(L, S).
subset(A,B) :- B=[_ |    S], 
A=     L, 
subset(L, S).

所以A是B的子集，如果

• B=[]和A=[]，或
• A包含B的第一个元素，等等。或
• A不包含B的第一个元素，等等

仅此而已。