Search code examples
listinsertprologfailure-slice

prolog list insert at any position

New to Prolog, trying to write a predicate to give all the options that an element could be inserted in to a list at any position. Ex:

ins(a, [b,c], R). should give:

R = [a,b,c]
R = [b,a,c]
R = [b,c,a]

which it does, but then gives an error 'Out of Global stack'. Is there a way to make this more deterministic, give the results and be done? When it is run in reverse ie. ins(X, Y, [a,b,c]). It gives the expected results then says false indicating it has completed. Code:

app([],L,L).
app([H|T],L2,[H|L]) :- 
    app(T,L2,L).

ins(E, List, R) :-
    R = R1,
    app(R2, R3, R1),
    app([E], R4, R3),
    app(R2, R4, List).

Here is a link to run the code in an online compiler, SWISH (This also has an example of how I hope to use ins, but ins is the problem right now) Any Help would be appreciated!

Solution

  • Did you notice how this went bad? First, Prolog was very nice and dandy and showed you how smart it is, and only later on it struck you: Buy. More. RAM. Now!

    Wouldn't it be better if Prolog would be up front? Before showing any answer?

    Well, you can force Prolog to do exactly this. Add a false at the end of your query like so:

    ?- ins(a, [b,c], R), false.
   resource_error(_). % ERROR: Out of global stack

    And the same you can do with your remaining program: Simply add false such that the remaining program still loops or runs out of space. I came up with the following minimal 

    app([],L,L) :- false.
app([H|T],L2,[H|L]) :-
    app(T,L2,L), false.

ins(E, List, R) :-
    R = R1,
    app(R2, R3, R1), false,
    app([E], R4, R3),
    app(R2, R4, List).

?- ins(a, [b,c], R), false.

    That means that we have to modify something in the remaining visible part in order to get rid of that looping. In other words: As long as the visible part remains unmodified the error will persist — guaranteed!

    For more on this technique to understand reasons for non-termination see

    The immediate fix would be to put the first app/3-goal last.

    But there is something else: You used all kinds of variables that are difficult to fathom. Maybe stick to a more uniform scheme. Also, there is no need for appending [A] using app/3. You actually need only two app/3 goals.