1

无法理解 Prolog 的工作原理。我正在尝试编写一个规则,该规则将三个整数列表作为输入(表示集合)并将属于第一个和第二个列表的整数放在第三个列表中。

例子:

?-inter([10,20,30,40],[10,50,40,60], List3 )
List3 = [10, 40]

到目前为止,我有这个,它可以识别列表是否包含某个字母:

mymember(X,[X|T]).
mymember(X,[H|T]) :- mymember(X,T).
4

3 回答 3

1

实际上有一个内置库可以为您整理所有内容,称为 ordsets。

inter(X, Y, Z) :-
    list_to_ord_set(X, L1),
    list_to_ord_set(Y, L2),
    ord_intersection(L1, L2, Z).

使用您的示例输入,您将获得以下信息

| ?- inter([10,20,30,40],[10,50,40,60],X).
X = [10,40] ? ;
no
于 2012-09-09T03:06:38.303 回答
1

inter(Xs, Ys, Zs)当 Zs 中的每个元素也在 XsYs 中时,将是真的。

但是 Z 是未知的,因此需要一种更具建设性的方法。这里是:iterate on Xs and store in Zs each element that is in Ys

迭代的一个例子是 mymember/2,你可以看到它需要一个递归谓词。上述语句的另一个惯用部分是store in Zs,Prolog 有一种特殊的方式来做这些事情,使用模式匹配。

inter([X|Xs], Ys, [X|Zs]) :-
   mymember(X, Ys), inter(Xs, Ys, Zs).

您将需要用其他 2 个子句完成 inter/3:基本递归,即当所有 Xs 元素都已处理时,以及 X不是Ys 成员的情况。

于 2012-09-09T06:03:53.223 回答
0

尝试这样的事情,使用内置member/2setof\3

set_intersection( As , Bs , Xs ) :-
  set_of( X , ( member(X,As) , member(X,Bs) ) , Xs )
  .

应该注意的是,如果列表没有共同的元素,这将As失败Bs。另一种方法是使用findall/3而不是set_of/3. findall/3如果目标不满足,将退回并清空列表而不是失败:

set_intersection( As , Bs , Xs ) :-
  findall( X , ( member(X,As) , member(X,Bs) ) , Xs )
  .

然而findall/3返回一个(允许重复)而不是一个集合(不允许重复),所以如果你的两个源列表不是集合,你就不会得到一个集合。

member/2是一个内置谓词,它将它的第一个参数与列表的一个元素统一起来——相当于

member(X,[X|_).
member(X,[_|Xs) :- member(X,Xs) .

最后,正如@chac 在他的回答中指出的那样,您可以递归地遍历列表。

set_intersection( [] , _ , [] ) .            % the intersection of the empty set with anything is the empty set.
set_intersection( [A|As] , Bs , [A|Xs] ) :-  % if the list is non-empty,
  member(A,Bs) ,                             % - and A is a member of the 2nd set
  ! ,                                        % - we cut off alternatives at this point (deterministic)
  set_intersection( As , Bs , Xs )           % - and recurse down on the tail of the list.
  .
set_intersection( [_|As] , Bs , Xs ) :-      % if the list is non-empty, and A is NOT a embmer of the 2nd set
  set_intersection( As , Bs , Xs )           % we just recurse down on the tail of the list.
  .

@chac 的技术会在他进行时构建结果列表,例如:

[a|X]
[a,b|X]
[a,b,c|X]

最终统一,空列表的特殊情况将列表的未绑定尾部与[]使列表完整统一,因此最终[a,b,c|X]变为

[a,b,c]

一点序幕魔法。一种可能更容易理解的替代方法是使用带有累加器的工作者谓词:

%
% set_intersection/3: the public interface predicate
%
set_intersection( As , Bs , Xs ) :-
   set_intersection( As , Bc , [] , T ) % we seed our accumulator with the empty list here
   .


%
% set_intersection/4: the private worker bee predicate
%    
set_intersection( []     , _  , T , Xs ) :-   % since our accumulator is essentially a stack
  reverse(T,Xs)                               % we need to reverse the accumulator to 
  .                                           % put things in the expected sequence
 set_intersection( [A|As] , Bs , T  , Xs ) :-
  member( A, Bs ) ,
  ! ,
  T1 = [A|T] ,
  set_intersection( As , Bs , T1 , Xs )
  .
set_intersection( [_|As] , Bs , T , Xs ) :-
  set_intersection( As , Bs , T , Xs )
  .
于 2012-09-10T17:40:12.947 回答