Prolog编写判断列表C为A与B差集的difference谓词方法

首先明确谓词需要满足的核心规则，对应给出的测试用例：

• 最终结果C的元素顺序和A中元素出现顺序完全一致
• A中所有出现在B里的元素必须全部移除，不能残留
• A中不在B里的元素必须全部保留，包括重复元素（这也是第二个测试用例返回false的原因：A有两个不在B中的5，C只传了一个5，不符合要求）

实现代码 #

用递归分情况处理即可，不需要依赖复杂的内置谓词：

% 辅助谓词：判断元素是否在列表中，若使用Prolog内置member/2可省略这部分
member(X, [X|_]).
member(X, [_|T]) :- member(X, T).

% 边界条件：空列表移除任意元素结果都是空列表
difference([], _, []).

% 情况1：当前A的头部元素在B中，直接移除，递归处理剩余尾部
difference([H|T], B, C) :-
    member(H, B),
    difference(T, B, C).

% 情况2：当前A的头部元素不在B中，放入结果C的头部，递归处理剩余尾部
difference([H|T], B, [H|CT]) :-
    \+ member(H, B),
    difference(T, B, CT).

测试用例验证 #

把上述代码加载到Prolog环境后，执行给出的测试查询结果完全符合预期：

• 查询difference([1,2,3,5],[1,2,3], [5]).，程序依次移除1、2、3，最后保留单个5，返回true
• 查询difference([1,2,3,5,5],[1,2,3], [5]).，程序判断两个5都不在B中，C需要包含两个5，传入的[5]长度和内容都不匹配，返回false
• 查询difference([4,7,6],[4,6], [7]).，程序依次移除头部的4、尾部的6，保留中间的7，返回true

实现说明 #

• 该实现不会对结果做自动去重，严格按照A中元素的出现顺序和数量生成结果
• 只要元素在B中存在就会被移除，不要求B中元素的顺序和重复次数
• 谓词是可逆的，既可以用来判断三个列表是否符合差集关系，也可以传入A和B计算得到C

内容的提问来源于stack exchange，提问作者Dav7538