prolog - Prolog 中的成员谓词

Question

我想定义一个成员谓词。

members(A, B) 表示列表 A 的所有成员都是列表 B 的成员。top(N) 定义 A 的长度。

这是我的尝试:

top(5).

members([X], L):-
   member(X, L).
members([X| Xs], L):-
   member(X, L),
   members(Xs, L),
   length(Xs, M),
   top(N),
   M < N.

我想按如下方式使用它:

members(L, [1,2,3]).

我的实现的问题是，如果我；为了获得新的答案，我将以错误结束:超出本地堆栈

?- members(I, [1,2,3]).
I = [1] ;
I = [2] ;
I = [3] ;
I = [1, 1] ;
I = [1, 2] ;
I = [1, 3] ;
I = [1, 1, 1] ;
I = [1, 1, 2] ;
I = [1, 1, 3] ;
I = [1, 1, 1, 1] ;
I = [1, 1, 1, 2] ;
I = [1, 1, 1, 3] ;
I = [1, 1, 1, 1, 1] ;
I = [1, 1, 1, 1, 2] ;
I = [1, 1, 1, 1, 3] ;
;ERROR: Out of local stack

如何更改代码以防止内存不足？

Answer 1

正如已经提到的，您的问题是您在递归调用之后进行长度检查，这意味着递归是无界的。不幸的是，只是将长度检查移到递归调用之上，如下所示......

members([X], L):-
   member(X, L).
members([X|Xs], L):-
    length(Xs, M),
    top(N), M < N,
    member(X, L),
    members(Xs, L).

...不太好，因为我们得到这个:

L = [3, 1, 2, 3, 3] ;
L = [3, 2, 2, 3, 3] ;
L = [3, 3, 2, 3, 3] ;
L = [3, 1, 3, 3, 3] ;
L = [3, 2, 3, 3, 3] ;
L = [3, 3, 3, 3, 3] ;
ERROR: Out of global stack

虽然这给了我们答案，但它并没有那么有用，因为它不能放入更大的谓词中，因为它会损坏。它之所以破裂，是因为我们只是把问题推得更远。原因如下:

问题在于您正在以自上而下的方式构建列表。换句话说，我们这样定义列表:List = [Head|Tail]，其中我们对 Head 规定了一些约束，并声明 Tail 由由相同约束定义的元素列表组成，并且受基本情况限制。这意味着，当我们处于递归调用过程中时，我们实际上只能访问 Head - 我们无法访问 Tail 的内容，因为它只有在解释器一路向下时才被构造。并到达基本情况(即 members([X], L) :-)，然后连续将每个 Tail 添加到其 Head 直到构建最终的 List。

看起来我们可以访问长度，因为 length/2 调用位于递归谓词的中间，但是由于变量被传递到 length/2 因为列表在这个阶段没有绑定(bind)到任何东西，Prolog 会等到完成该点以下的递归调用后再计算长度。当然，问题在于长度检查限制了递归，因此它将继续下去，直到内存耗尽。

虽然自上而下的递归往往是构造 Prolog 谓词的默认方式，如本例所示，但有时我们需要访问我们正在创建的数据结构。解决方案是使用自下而上的递归。这是在 Prolog 中通过累加器谓词实现的，累加器谓词从一个空列表开始，然后通过将累加器列表(这是一个完全基础的列表)传递给 up 来逐一构建列表递归谓词。以下是我为这个问题编写累加器谓词的方法:

members(I,L) :-
    members_accumulator([],I,L).

members_accumulator(Tail,I,L) :-
    length(Tail, M),
    top(N),
    M < N,
    member(X, L),
    members_accumulator([X|Tail],I,L).
members_accumulator(I,I,_).

我们需要两个谓词，因为第一个是累加器的包装器，它将空列表传递给累加器谓词。基本情况不再与空列表有任何关系 - 它所要做的就是声明最终的累加器列表实际上是我们所追求的最终列表(仅出于此目的，它已经通过累加器谓词进行了线程化) 。另外，在这种情况下，累加器谓词需要按此顺序排列，否则最后会有一个评估为 false 的选择点。

在 Prolog 中深入了解递归，以及当您需要使用自下而上递归而不是自上而下递归时，这是一项不小的壮举。在我仔细阅读The Art of Prolog之前，我根本没有真正掌握它。 。网上还应该有大量有关累加器的信息。