如何实现支持所有参数模式的Prolog列表元素删除谓词

改进实现方案 #

原来的谓词出现无限递归的核心原因有两个：

1. 使用了\=做不等判断：该谓词仅当两个参数都足够绑定可判断相等时才生效，若参数未绑定会直接失败，且不会保留约束信息
2. 不等判断放在递归调用之后：当第二个参数为自由变量时，Prolog会无限匹配删除头元素的子句，永远不会执行到不等判断逻辑

支持所有参数模式的实现 #

使用dif/2延迟不等约束替换\=，并将约束前置到递归之前即可：

deleted(_, [], []).
% 匹配头元素等于待删除元素的情况，直接跳过当前头递归处理尾部
deleted(X, [X|T], R) :-
    deleted(X, T, R).
% 匹配头元素不等于待删除元素的情况，保留当前头后递归处理尾部
deleted(X, [H|T], [H|R]) :-
    dif(X, H),
    deleted(X, T, R).

dif/2是绝大多数主流Prolog实现（SWI-Prolog、SICStus、GNU Prolog等）原生支持的约束谓词，会延迟到两个参数足够绑定时才做相等性检查，全程保证两个参数不相等。

效果验证 #

原来会栈溢出的查询现在可以正常返回所有正确解：

?- deleted(a, Y, [b]).
Y = [b] ;
Y = [a, b] ;
Y = [b, a] ;
Y = [a, a, b] ;
Y = [a, b, a] ;
Y = [b, a, a] ;
... % 所有包含且仅包含一个b、其余元素都是a的列表，按长度递增依次返回

?- deleted(X, Y, [b]).
Y = [b],
dif(X, b) ;
Y = [X, b],
dif(X, b) ;
Y = [b, X],
dif(X, b) ;
Y = [X, X, b],
dif(X, b) ;
... % 所有包含且仅包含一个b、其余元素都等于X且X不等于b的列表，按长度递增依次返回

原来的所有可正常运行的查询不受影响，依然可以得到正确结果。

内容的提问来源于stack exchange，提问作者Géry Ogam