CODEWITHSUNDEEP
recursionprolog
Peter
Peter

Reputation: 1759

Stop recursion when variable is reached

I have a prolog program with searches for something and every time it hasn't found it, it increments a variable by 1. If it never finds what the user is searching for, it will search forever. Can I stop prolog from doing that, if a special variable is reached? This is the predicate which searches for something:

% ---------------------------------------------------------------------
% find(X,Y,N) :- ...search for it
% find(X,Y,N) :- ...if not found, increment N by 1 and repeat recursion
% ---------------------------------------------------------------------
find(Y,I,G) :- member(Y,I), G is 0.
find(Y,I,G) :- not(member(Y,I)), expand(I,O), find(Y,O,G1), G is G1+1.
find(Y,I,50) :- fail.

So I want to write something like

find(X,Y,50) :- return false

So that the program returns false, if it hasn't found it after 50 recursions. How do I realize that?

EDIT: This is my code: http://pastebin.com/4X7BSFQ2

vwg(X,Y,G) is searching if the two persons X and Y are related with grade G for example:

vwg(vanessaMueller, selinaMueller, 1)

is true, cause vanessaMueller is her mother

Upvotes: 1

Views: 4716

Answers (3)

Nicholas Carey
Nicholas Carey

Reputation: 74227

If you always have the third argument (the iteration count) bound, you can simply count down. Once you hit zero, you've failed:

find( Y , I , G ) :-  %
  integer(G) ,        % enforce the contract that G must be bound
  G > 0 ,             % if we've not yet hit zero,
  member(Y,I) ,       % see if we can find Y in I
  ! .                 % and eliminate any alternatives.
find( Y , I , G ) :-  %
  integer(G) ,        % enforce the contract that G must be bound
  G > 0 ,             % if we've not yet hit zero
  G1 is G-1 ,         % decrement G
  expand(I,I1) ,      % expand I
  find(Y,I1,G1)       % and recurse down
  .                   %

Note that the above requires the initial call to to find/3 to have its third argument bound to an integer.

If, instead, you want your third argument to return the count, rather than defining a limit (and using a hard-coded limit instead), you can use a helper with an accumulator:

find( Y , I, G ) :-
  find(Y,I,1,G)
  .

find( Y , I , G , G ) :-
  G =< 50 ,              % if we've not yet exceeded the limit
  member(Y,I) ,          % see if we can find Y in I
  ! .                    % and eliminate alternatives
find( Y , I , T , G ) :- %
  T < 50 ,               % if we're below the limit
  T1 is T+1 ,            % increment the accumulator
  expand(I,I1) ,         % expand I
  find(Y,I1,T1,G)        % and recurse down.
  .                      % easy!

Or you can pass in the limit another argument and get the recursion count on success:

find( Y , I, N , G ) :-
  find(Y,I,N,1,G)
  .

find( Y , I , N , G , G ) :-
  G =< N ,
  member(Y,I) ,
  ! .
find( Y , I , N , T , G ) :-
  T < N ,
  T1 is T+1 ,
  expand(I,I1) ,
  find(Y,I1,N,T1,G)
  .

There's more than one way to do it.

Upvotes: 1

CapelliC
CapelliC

Reputation: 60014

from your pastebin, I get

find(Y,I,G) :- member(Y,I), G is 0.
find(Y,I,G) :- not(member(Y,I)), expand(I,O), find(Y,O,G1), G is G1+1.
find(Y,I,50) :- fail.

I would try

find(Y,I,0) :- member(Y,I).
find(Y,I,G) :- G < 50, not(member(Y,I)), expand(I,O), G1 is G+1, find(Y,O,G1).

Upvotes: 1

Arian Kiehr
Arian Kiehr

Reputation: 451

Depending on your interpreter you can use

find(X,Y,50) :- fail

Upvotes: 0

Related Questions