带有列表的 Prolog 基本练习给出堆栈大小错误

Question

我开始学习序言，但我一直被这个问题所困扰，如果有人能告诉我我做错了什么以及为什么会出错，那将非常有帮助，以便我学习。

运动

写一个遵循语法的谓词：

supr_bigger（元素、列表、结果）

其中 Result 是列表 List，但所有元素都大于 Elem 已删除。

代码

supr_bigger(_,[],[]).

supr_bigger(Elem,[X|Y],R) :- X =< Elem,
                                  insert(X,R,R1),
                                  supr_bigger(Elem,Y,R1).

supr_bigger(Elem,[X|Y],R) :- X > Elem, supr_bigger(Elem,Y,R).



insert(Z,L1,L2) :- choose(Z,L2,L1).


choose(X,[X|L],L).
choose(X,[Y|L1],[Y|L2]) :- choose(X,L1,L2).

当我尝试测试上面的代码时，出现了这个错误：
?- supr_bigger(3,[3,2,5,4,1,2,6],R)。

错误：超出堆栈限制 (1,0Gb)
错误：堆栈大小：本地：2Kb，全局：0,9Gb，跟踪：0Kb
错误：堆栈深度：16，最后调用：13%，选择点：11

非常感谢。

Answer 1

您可以使用谓词 trace/1 来找出您的代码有什么问题：

?- trace, supr_bigger(3, [3,2,1,4], R).
   Call: (11) supr_bigger(3, [3, 2, 1, 4], _4526) ? creep
   Call: (12) 3=<3 ? creep
   Exit: (12) 3=<3 ? creep
   Call: (12) insert(3, _4526, _5168) ? creep
   Call: (13) choose(3, _5210, _4526) ? creep
   Exit: (13) choose(3, [3|_4526], _4526) ? creep
   Exit: (12) insert(3, _4526, [3|_4526]) ? creep
   Call: (12) supr_bigger(3, [2, 1, 4], [3|_4526]) ? creep
   Call: (13) 2=<3 ? creep
   Exit: (13) 2=<3 ? creep
   Call: (13) insert(2, [3|_4526], _5482) ? creep
   Call: (14) choose(2, _5524, [3|_4526]) ? creep
   Exit: (14) choose(2, [2, 3|_4526], [3|_4526]) ? creep
   Exit: (13) insert(2, [3|_4526], [2, 3|_4526]) ? creep
   Call: (13) supr_bigger(3, [1, 4], [2, 3|_4526]) ? creep
   Call: (14) 1=<3 ? creep
   Exit: (14) 1=<3 ? creep
   Call: (14) insert(1, [2, 3|_4526], _5796) ? creep
   Call: (15) choose(1, _5838, [2, 3|_4526]) ? creep
   Exit: (15) choose(1, [1, 2, 3|_4526], [2, 3|_4526]) ? creep
   Exit: (14) insert(1, [2, 3|_4526], [1, 2, 3|_4526]) ? creep
   Call: (14) supr_bigger(3, [4], [1, 2, 3|_4526]) ? creep
   Call: (15) 4=<3 ? creep
   Fail: (15) 4=<3 ? creep
   Redo: (14) supr_bigger(3, [4], [1, 2, 3|_4526]) ? creep
   Call: (15) 4>3 ? creep
   Exit: (15) 4>3 ? creep
   Call: (15) supr_bigger(3, [], [1, 2, 3|_4526]) ? creep
   Fail: (15) supr_bigger(3, [], [1, 2, 3|_4526]) ?

如您所见，当输入列表为空（调用15）时，输出列表实际上包含所有本应被选中的元素。但是，supr_bigger/3的递归定义中的基本子句不能应用于这种情况，因为列表[]（子句的第三个参数）和 [1, 2, 3|_4526]（目标的第三个参数）不匹配。

要解决此问题，您可以将代码修改为：

关闭打开列表[1, 2, 3|_4526]，将其转化为[1, 2, 3]。
添加一个新参数来收集最终结果。

但是，由于您的代码还有许多其他问题，最好尝试 更简单的方法:

supr_bigger(_, [], []).
supr_bigger(B, [X|Xs], [X|Ys]) :- X =< B, supr_bigger(B, Xs, Ys).
supr_bigger(B, [X|Xs], Ys) :- X  > B, supr_bigger(B, Xs, Ys).

示例：

?- supr_bigger(3, [3,2,1,4], R).
R = [3, 2, 1] ;
false.

要消除虚假的选择点，可以按如下方式进行

supr_bigger(B, L, R) :-
    best_supr_bigger(L, B, R).

best_supr_bigger([], _, []).
best_supr_bigger([X|Xs], B, R) :-
    (   X =< B
    ->  R = [X|Ys]
    ;   R = Ys ),
    best_supr_bigger(Xs, B, Ys).

示例：

?- supr_bigger(3, [3,2,1,4], R).
R = [3, 2, 1].

带有列表的 Prolog 基本练习给出堆栈大小错误

Prolog basic exercise with lists gives stack size error

list

prolog

swi-prolog

运动

代码