Prolog:如何在没有削减的情况下避免回溯？

Question

所以我试图在prolog中编写一个谓词,它可以获取列表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

使用支持的Prolog系统dif/2.有许多这样的系统,甚至是免费的系统.

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.

不需要削减来表达术语不平等.

Answer 2

由于您不能使用内置函数或控制结构或剪切，也许问题的重点是没有答案。（也就是说，也许问题的要点是强调需要某种方式来表达否定，例如将否定视为失败或不平等。）

（顺便说一句，您对 myappendelem 的定义实际上是在元素前面添加的。）