list - 将成员谓词实现为单行

Question

面试问题!

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

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

解决方案:

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

演示:

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

工作原理:

我们正在寻找第二个参数X中第一个参数[Y|T]的出现。

第二个参数假定为列表。 Y匹配其头部，T匹配其尾部。

结果，空列表的谓词失败(应该如此)。

如果X = Y(即X可以与Y统一)，则我们在列表中找到X。否则(;)我们测试X是否在尾部。

备注:

感谢humble coffee指出使用=(统一)会比使用==(测试相等性)产生更灵活的代码。

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

?- 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版本5.6.57测试)。