list - 带有列表的 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

非常感谢提前。

标签： listprologswi-prolog

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].