Search code examples
prologbacktracking

Generating integers < limit

I am trying to generate all integers (natural numbers) smaller than a limit, let's say 10. I have a predicate nat(X) which produces all numbers from 0 to infinity.

Now my problem is, if I do:

nat10(X) :- nat(X), X =< 10.

This will never terminate, as it tries to find other solutions with nat(X) until infinity.

I need a construct that let's me fail the whole predicate if one subgoal fails. How would I go about doing that?

Solution

  • Depending upon the problem being solved, you might want to consider constraint logic programming over finite domains (CLPFD).

    But in this context, you need just prevent Prolog from backtracking if X > 10. The current predicate nat10/1 has no such constraint, so we'll add it:

    nat10(X) :- nat(X), ( X > 10 -> !, fail ; true ).

    So if X > 10, we do a cut (!) to prevent backtracking to nat(X) (thus avoiding generating natural numbers above 10 infinitely) and then simply fail. Otherwise, we succeed (true).

    | ?- nat10(X).

X = 1 ? ;

X = 2 ? ;

...

X = 9 ? ;

X = 10 ? ;

(3 ms) no
| ?-