prolog - Prolog:如何避免不削减成本地回溯？

Question

因此，我尝试在序言中编写谓词，以获取列表L1和列表L2并返回L1中所有不在L2中的所有元素的列表。这是我到目前为止所拥有的:

% Append an element to a list.
myappendelem(X,L,[X|L]).

% True if input list contains X.
mycontains([H | T], X) :-
    H == X;
    mycontains(T,X).

% Does the work for notin().
nocontains([],_,A,A).
nocontains([H|T],L,A,R):-
    mycontains(L,H),
    nocontains(T,L,A,R);
    myappendelem(H,A,AR),
    nocontains(T,L,AR,R).

% Returns all elements in L1 not in L2.
notin(L1,L2,R):-
    nocontains(L1,L2,[],X).

此方法有效，但是给出了多个答案，例如:

notin([5,1],[4,3,2,1],X).
X = [5];
X = [5,1].

这是一个问题，因为我正在使用此谓词对图形中的路径进行排序(L1是我可能去过的节点的列表，L2是我去过的节点)，以确保我不会再访问同一节点而不是一次陷入循环。但是这种实现使我陷入了一个循环，因为它在尝试使用第一个X并失败之后一直回溯到未更改的X，陷入了两个可以互相到达的节点之间的无限循环。我知道这很容易解决，只需在nocontains中添加削减即可，如下所示:

% Does the work for notin().
nocontains([],_,A,A).
nocontains([H|T],L,A,R):-
    mycontains(L,H),!,
    nocontains(T,L,A,R);
    myappendelem(H,A,AR),!,
    nocontains(T,L,AR,R).

但是，有没有办法实现同样的目标而不削减呢？因此，当我使用notin时，我只会得到一个可能的答案？
(适用于学校，部分任务是不使用任何内置谓词或控制运算符)

编辑:

只是为了更具体地说明分配的局限性:它应由纯事实和规则组成，我们不允许使用任何内置谓词或控制结构(包括但不限于算术，减法或失败否定法) )。分号还可以。我们需要定义自己的任何实用谓词。

感谢所有答案，但是我开始认为，用于在图中找到两个节点之间的路径的方法可能会出现更多问题，因为从答案来看，它似乎并不容易解决这。

Answer 1

使用支持dif/2的Prolog系统。有很多这样的系统，甚至是免费的。
dif/2用于以纯关系方式表示两个术语是不同的。

例如，在您的情况下，描述一个元素不是列表的成员:

not_in(_, []).
not_in(L, [X|Xs]) :-
        dif(L, X),
        not_in(L, Xs).

或更短一点，使用maplist(dif(L), Ls)。

您可以在示例中使用以下代码:

?- Ls1 = [5,1], Ls2 = [4,3,2,1], member(M, Ls1), not_in(M, Ls2).
Ls1 = [5, 1],
Ls2 = [4, 3, 2, 1],
M = 5 ;
false.

请注意，这将产生唯一的解决方案 M = 5 。

无需削减即可表达术语不平等。