Search code examples
prologbacktracking

How to use backtrack to increment a variable infinitely in Prolog


I am currently reading a Prolog book and I am stuck on one of the challenge exercises. I am meant to create a predicate with one argument. When this argument is a variable, it will return the following with backtracking, and X will continue to increment with no limit.

X = 0, X = 1, X = 2, X = 3, X = ...

I made the simple predicate below which backtracks through 0-2 but I can't figure out a way to make it continue infinitely.

backtracking_exercise(X) :-
    X = 0;
    X = 1;
    X = 2.

I was considering using the between/3 predicate but this would be only give a finite amount of numbers. I also experimented with the plus/3 predicate and recursion but no luck. This is what I have come up with, but as you can tell it is currently useless.

backtracking_excercise2(X) :-
    X = 0,
    plus(X,1,Y),
    backtracking_excercise2(Y).

Any tips on how to proceed would be greatly appreciated.

Thank you in advance.


Solution

  • A tail-recursive variant of Jim's solution:

    plus(N) :-
        next_integer(1, N).
    
    next_integer(I, I).
    next_integer(I, K) :-
        J is I + 1,
        next_integer(J, K).
    

    To prevent going into an infinite loop when the plus/1 predicate is called with an instantiated argument, i.e. to make the predicate be only a generator, the first clause can be modified to:

    plus(N) :-
        var(N),
        next_integer(1, N).