list 将成员谓词实现为单行

Implement the member predicate as a one-liner

提问by Claudiu

Interview question!

面试题！

This is how you normally define the memberrelation in Prolog:

这是您通常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.

Define it using only one rule.

仅使用一个规则来定义它。

回答by Stephan202

1. Solution:

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

2. Demonstration:

   ?- 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. How it works:

   • We are looking for an occurrence of the first argument, X, in the the second argument, [Y|T].
   • The second argument is assumed to be a list. Ymatches its head, Tmatches the tail.
   • As a result the predicate fails for the empty list (as it should).
   • If X = Y(i.e. Xcan be unified with Y) then we found Xin the list. Otherwise (;) we test whether Xis in the tail.

4. Remarks:

   • Thanks to humble coffeefor pointing out that using =(unification) yields more flexible code than using ==(testing for equality).

   • This code can also be used to enumerate the elements of a given list:

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

   • And it can be used to "enumerate" all lists which contain a given element:

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

   • Replacing =by ==in the above code makes it a lot less flexible: it would immediately fail on member(X, [a])and cause a stack overflow on member(a, X)(tested with SWI-Prolog version 5.6.57).

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] ;
     ...
     

   • 替换上面代码中的=by==使其不那么灵活：它会立即失败member(X, [a])并导致堆栈溢出member(a, X)（使用 SWI-Prolog 版本 5.6.57 测试）。

回答by bcat

Since you didn't specify what other predicates we're allowed to use, I'm going to try and cheat a bit. :P

由于您没有指定我们允许使用哪些其他谓词，我将尝试作弊。 :P

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

回答by false

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

With

和

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

Actually, the following definition also ensures that Xsis a list:

实际上，以下定义也确保它Xs是一个列表：

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

Acknowledgements

致谢

The first appearance of above definition of ...is on p. 205, Note 1 of

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

David B. Searls, Investigating the Linguistics of DNA with Definite Clause Grammars. NACLP 1989, Volume 1.

David B. Searls，用定语从句语法研究 DNA 的语言学。NACLP 1989，第 1 卷。

回答by Adam Meissner

You can also try this:

你也可以试试这个：

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