将成员谓词实现为单行

Question

面试问题!

这是您通常member在Prolog中定义关系的方式:

member(X, [X|_]).        % member(X, [Head|Tail]) is true if X = Head 
                         % that is, if X is the head of the list
member(X, [_|Tail]) :-   % or if X is a member of Tail,
  member(X, Tail).       % ie. if member(X, Tail) is true.

仅使用一个规则定义它.

Answer 1

1. 解:

   member(X, [Y|T]) :- X = Y; member(X, T).
   

2. 示范:

   ?- member(a, []).
   fail.
   ?- member(a, [a]).
   true ;
   fail.
   ?- member(a, [b]).
   fail.
   ?- member(a, [1, 2, 3, a, 5, 6, a]).
   true ;
   true ;
   fail.
   

3. 这个怎么运作:

   • 我们正在寻找第一个参数的出现X,在第二个参数中[Y|T].
   • 假设第二个参数是一个列表.Y匹配它的头部,T匹配尾巴.
   • 结果,谓词对于空列表失败(应该如此).
   • 如果X = Y(即X可以统一Y)那么我们X在列表中找到.否则(;)我们测试是否X在尾部.

4. 备注:

   • 感谢卑微的咖啡,指出使用=(统一)产生比使用==(测试相等)更灵活的代码.

   • 此代码还可用于枚举给定列表的元素:

     ?- member(X, [a, b]).
     X = a ;
     X = b ;
     fail.
     

   • 它可以用于"枚举"包含给定元素的所有列表:

     ?- member(a, X).
     X = [a|_G246] ;
     X = [_G245, a|_G249] ;
     X = [_G245, _G248, a|_G252] ;
     ...
     

   • 替换=通过==在上面的代码使得它少了很多灵活:它会立即失败上member(X, [a])并导致上堆栈溢出member(a, X)(与SWI-Prolog的版本57年5月6日测试).

Answer 2

既然你没有指定我们允许使用的其他谓词,我会尝试作弊. :P

member(X, L) :- append(_, [X|_], L).

Answer 3

newmember(X, Xs) :-
   phrase(( ..., [X] ),Xs, _).

同

... --> [] | [_], ... .

实际上,以下定义也确保了这Xs是一个列表:

member_oflist(X, Xs) :-
   phrase(( ..., [X], ... ), Xs).

致谢

上面定义的第一次出现...是在p.205,注1

David B. Searls,用明确的条款语法研究DNA的语言学.NACLP 1989,第1卷.