1

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.

false
  • 10,264
  • 13
  • 101
  • 209
dodge
  • 13
  • 3
  • 5
    `length(_,X)` is a fast way – false Mar 01 '17 at 14:55
  • 2
    @false Using `length/1` is also a terrible way given that it generates lists that will eventually need to be garbage collected. – Paulo Moura Mar 01 '17 at 15:42
  • @PauloMoura: Have you **measured** the actual "overhead"? It's completely neglectable. And it is much faster than the accepted answer... – false Mar 01 '17 at 18:28
  • @false This is a terrible way because it will crash when the integer is too big (`100,000,000` is small enough), even though the task solved is seemingly trivial. – Fatalize Mar 02 '17 at 08:42
  • @Fatalize: Could you please first measure the accepted solution for, say, 1000000? And, a system that crashes is broken by definition. – false Mar 02 '17 at 10:41
  • 1
    @false I'm not saying the accepted solution is good, I'm saying using `length` is not good either. – Fatalize Mar 02 '17 at 11:24
  • @Fatalize: There is not a single case where the accepted solution is better. That is a difference worth noting. – false Mar 02 '17 at 11:43
  • For reference outside of exercise limitations, [here is a good implementation of that predicate](http://stackoverflow.com/a/39259871/2554145). – Fatalize Mar 02 '17 at 11:48
  • @Fatalize: That still needs some extra work: In SWI it is 84 times slower, and in SICStus a factor of 11 for: `time( (positive_integer(N),N=100000) )`. – false Mar 05 '17 at 01:51

2 Answers2

1

You had tagged your question with 'recursion' (since removed) and yet have implemented no recursion. I assume that this challenge is from a chapter on recursion, so I present the following hints (followed by a solution):

Hint 1:

What is the base case? If you want a recursive call to terminate it should have a base case.

Your base case is X = 0.

Hint 2:

What is the recursive step? What do you need to do to the previous iteration in order to generate the next step in the sequence?

Your step is X is OldX + 1.

A Solution:

plus(0).
plus(X) :- plus(N), X is N + 1.

Additional info:

This solution will go infinite for plus(-1). (and, indeed, all negative X).
To avoid this, you'll need more advanced tools (such as DCG or CLP(FD)).

Jim Ashworth
  • 765
  • 6
  • 17
1

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).
Paulo Moura
  • 18,373
  • 3
  • 23
  • 33