Prolog basic exercise with lists gives stack size error

Question

I'm starting to learn prolog, and I'm stuck with this problem, it would be really helpful if someone could tell me what I'm doing wrong and why is it wrong so I can learn.

Exercise

Write a predicate that follows the syntax:

supr_bigger(Elem,List,Result)

where Result is the list List, but with all of the elements bigger than Elem deleted.

Code

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

When I try to test the code above, this error shows up:
?- supr_bigger(3,[3,2,5,4,1,2,6],R).

ERROR: Stack limit (1,0Gb) exceeded
ERROR: Stack sizes: local: 2Kb, global: 0,9Gb, trail: 0Kb
ERROR: Stack depth: 16, last-call:13%, Choice points: 11

A lot of thanks in advance.

To start with, please replace supr-bigger by supr_bigger — false

slago slago · Accepted Answer · 2021-07-09T20:00:39

You can use predicate trace/1 to find out what is wrong with your code:

?- 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]) ?

As you can observe, when the input list is empty (call 15), the output list actually contains all the elements that should have been selected. However, the base clause in the recusive definition of supr_bigger/3 cannot be applied in this case, since lists [] (clause's third argument) and [1, 2, 3|_4526] (goal's third argument) do not match.

To solve the problem, you could modify your code to:

Close the open list [1, 2, 3|_4526], transforming it into [1, 2, 3].
Add a new argument to collect the final result.

But, since your code has many other problems, it's better to try a simpler approach:

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

Example:

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

To eliminate spurious choice points, you can do as follows

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

Example:

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

Prolog basic exercise with lists gives stack size error

Exercise

Code

1 Answers