Prolog中的成员谓词

Question

我想定义一个成员谓词。成员（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和State的一些约束条件，Tail由相同约束定义的元素列表组成，并且由基本情形限定。这意味着，当我们处于递归调用的中间时，我们实际上只能访问头部 - 我们无法访问尾部的内容，因为只有在解释器已经完成了向下并且到达基本案例（即members([X], L) :-），然后连续添加每个尾部到其头部，直到构建最终列表。

它可能看起来像我们可以访问的长度，因为length/2调用坐在递归谓词的中间，但是因为列表中传递给length/2的变量在此阶段不受任何约束，在计算长度之前，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,_). 

我们需要两个谓词，作为第一个是围绕通空单累加器谓词蓄能器的包装。基本情况不再与空列表有关 - 它只需要声明最终的累加器列表实际上就是我们之后的最后一个列表（为了这个目的，它已经通过了累加器谓词） 。此外，在这种情况下，累加器谓词需要按照此顺序，否则会有一个选择点在最后评估为错误的权利。

在Prolog中获取头部递归，并且当您需要使用自下而上递归而不是自上而下时，这是一项不平凡的专长。直到我对The Art of Prolog进行了很好的阅读之后，我才真正掌握了它。还应该有大量有关累积在线的信息。

Answer 2

您在递归之后检查深度。所以递归的深度不受限制，只有结果列表被丢弃的时间太长。

Answer 3

这是一个不需要计算列表长度的替代实现。这里的N是列表A的长度。这个解决方案给出了所有的答案，而不会退出堆栈。

members([X],L,1) :- member(X,L). 
members([H|T],L,N) :- N>1 , member(H,L) , N1 is N-1, members(T,L,N1). 

实例执行：

?- members(L,[1,2,3],5). 
L = [1, 1, 1, 1, 1] ; 
L = [1, 1, 1, 1, 2] ; 
L = [1, 1, 1, 1, 3] ; 
L = [1, 1, 1, 2, 1] ; 
... 
L = [3, 3, 3, 1, 2] ; 
L = [3, 3, 3, 3, 1] ; 
L = [3, 3, 3, 3, 2] ; 
L = [3, 3, 3, 3, 3] ; 
No 

Answer 4

使用meta-predicatemaplist/2， lambdas，和会员谓语memberd/2和简单的写：

:- use_module(library(lambda)). 

members(As,Bs,N) :- 
    length(Xs,N), 
    append(As,_,Xs), 
    maplist(Bs+\A^memberd(A,Bs), As). 

样品查询与缩写答案序列：

?- members(As,[1,2,3],5). 
As = [   ] ; 
As = [  1] ; As = [  2] ;   As = [  3] ; 
As = [  1,1] ; As = [  1,2] ; /* ... */ As = [  3,3] ; 
As = [ 1,1,1] ; As = [ 1,1,2] ; /* ... */ As = [ 3,3,3] ; 
As = [ 1,1,1,1] ; As = [ 1,1,1,2] ; /* ... */ As = [ 3,3,3,3] ; 
As = [1,1,1,1,1] ; As = [1,1,1,1,2] ; /* ... */ As = [3,3,3,3,3] ; 
false. 

上面的查询全局终止。 我们来看看解决方案集的大小：

 
?- setof(As,members(As,[1,2,3],5),Ass), length(Ass,N_Solutions). 
Ass   = [[],[1],[1,1],[1,1,1],[1,1,1|...],[1,1|...],[1|...],[...|...]|...], 
N_Solutions = 364. 

?- 364 =:= 1 + 3 + 3^2 + 3^3 + 3^4 + 3^5. 
true.