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

看起来我们可以访问长度,因为length/2调用位于递归谓词的中间,但是因为传递length/2给列表的变量在此阶段没有绑定任何内容,所以Prolog会等到它完成在计算长度之前,在此点之下进行递归调用.问题当然是长度检查是递归的边界,所以它会一直持续到内存不足为止.

虽然自上而下的递归往往是构造Prolog谓词的默认方式,但正如此示例所示,有时我们需要访问我们正在创建的数据结构.解决方案是使用自下而上的递归.这在Prolog中由累加器谓词,其与一个空列表开始,并进行到生成列表的方式实现了通过一个一个,通过将累加器列表(这是一个完全地列表)通过递归谓词.这是我为这个问题写一个累加器谓词的方法:

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中进行递归,当你需要使用自下而上的递归而不是自上而下是一个非平凡的壮举.在我通过Prolog的艺术阅读之前,我根本没有真正掌握它.还应该有很多关于累积器在线的信息.