6

所以我试图在序言中编写一个谓词,它可以采用列表 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 时,我只能得到一个可能的答案?(它是针对学校的,部分任务是不使用任何内置谓词或控制运算符)

编辑:

只是为了更具体地说明赋值的限制:它应该由纯事实和规则组成,我们不允许使用任何内置的谓词或控制结构(包括但不限于算术,削减或否定作为失败)。分号没问题。我们需要定义自己的任何实用谓词。

感谢所有答案,但我开始认为我用于在图中查找两个节点之间的路径的方法可能是一个问题,因为从答案来看,似乎没有简单的方法这个。

4

4 回答 4

7

使用支持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

不需要削减来表达术语不等式。

于 2015-09-29T06:05:50.667 回答
3

由于您不能使用内置函数或控制结构或剪切,因此问题的关键在于没有答案。(也就是说,也许问题的重点是强调需要某种方式来表达否定,例如,作为失败或不平等的否定。)

(顺便说一句,您对 myappendelem 的定义实际上是在元素前面。)

于 2015-09-29T05:06:05.113 回答
1

如果你不能使用dif, or findallor setofor \+or ->or even ;then you can use the following where the control is built around \=. 这仍然是失败的否定(就像有一个内部不可见的切口一样)。不过,在其他答案中使用方法和内置系统谓词是一种更好的方法。

my_member(I,[I|_]).
my_member(I,[_|T]):-
  my_member(I,T).

notin(Test,List,Result):-
  notin_(Test,List,[],[],Result).

notin_([],_,_,Result,Result).
notin_([H|T],List,AcIn,AcOut,Result):-
  my_member(H,List),
  notin_(T,List,[H|AcIn],AcOut,Result).
  notin_([H|T],List,AcIn,AcOut,Result):-
  not_member(H,List),
  notin_(T,List,AcIn,[H|AcOut],Result).

item_is_not_head(Item,[H|_]):-
  H \= Item.

not_member(_,[]).
not_member(Item,List):-
  List=[_|T],
  item_is_not_head(Item,List),
  not_member(Item,T).

查询:

?-notin([5,1],[4,3,2,1],X).
X =[5],
false.

但它会给你重复的答案。(但至少它们是相同的)。

  ?- notin([a,b,q,x,x,y],[a,b,q,d,a,a],R).
  R = [y, x, x] ;
  R = [y, x, x] ;
  R = [y, x, x] ;
  false.
于 2015-09-29T10:42:28.257 回答
1

琐碎的,迂回的方式来做到这一点:

?- setof(M, ( member(M, L1), \+ member(M, L2) ), Ms).

这正是:

做一组所有M这样的人,它M是 的成员,L1但不是 的成员L2

?- L1 = [a,b,c,d,e,f,g],
   L2 = [c,f,x,y],
   setof(M, ( member(M, L1), \+ member(M, L2) ), Ms).
Ms = [a, b, d, e, g].

如果您不想制作有序集,可以使用bagof/3代替setof/3

?- L1 = [c,b,a,c,b,a],
   L2 = [c,y],
   setof(M, ( member(M, L1), \+ member(M, L2) ), Ms).
Ms = [a, b].

?- L1 = [c,b,a,c,b,a],
   L2 = [c,y],
   bagof(M, ( member(M, L1), \+ member(M, L2) ), Ms).
Ms = [b, a, b, a].

但是,@mat 的答案显示了一种比\+ member(M, L2).

还有一些库谓词可以完成这项工作。处理集合的一种更有效library(ordsets)的方法是将它们表示为没有重复的排序列表,如下所示:

?- L1 = [a,b,c,d,e,f,g,a,a,a],
   L2 = [c,f,x,y],
   time(setof(M, ( member(M, L1), \+ member(M, L2) ), Ms)).
% 85 inferences, 0.000 CPU in 0.000 seconds (95% CPU, 1841262 Lips)
Ms = [a, b, d, e, g].

?- L1 = [a,b,c,d,e,f,g,a,a,a],
   L2 = [c,f,x,y],
   time(( sort(L1, S1),
          sort(L2, S2),
          ord_subtract(S1, S2, S) )).
% 28 inferences, 0.000 CPU in 0.000 seconds (90% CPU, 1066545 Lips)
S1 = [a, b, c, d, e, f, g],
S = [a, b, d, e, g].

(一般来说,更少的推理意味着更少的工作来证明查询。然而,这在sort/2涉及时有点误导,因为它总是算作一个推理。在 SWI-Prolog 中,它使用原生 C 实现,很难与纯 Prolog 代码相比。另外,请记住在内部setof/3使用 a sort/2。)

于 2015-09-29T07:18:06.993 回答