Prolog: "findall" for limited number of solutions
A portable solution in ISO Prolog:
:- dynamic(find_n_solution/1).
:- dynamic(find_n_counter/1).
find_n(N, Term, Goal, Solutions) :-
( set_find_n_counter(N),
retractall(find_n_solution(_)),
once((
call(Goal),
assertz(find_n_solution(Term)),
dec_find_n_counter(M),
M =:= 0
)),
fail
; findall(Solution, retract(find_n_solution(Solution)), Solutions)
).
set_find_n_counter(N) :-
retractall(find_n_counter(_)),
assertz(find_n_counter(N)).
dec_find_n_counter(M) :-
retract(find_n_counter(N)),
M is N - 1,
assertz(find_n_counter(M)).
Using the sample predicate find/1
@ChristianF answer:
| ?- find_n(10, X, find(X), L).
L = [0,1,2,3,4,5,6,7,8,9]
yes
Note that this solution will still return a list of solutions even if there are less than the required number of solutions. Some Prolog compilers, including B-Prolog and ECLiPSe provide non-logical global variables that can be used to implement the counter but that would make the solution non-portable.
There are many similar uses, so maybe consider to define some abstractions in between. E.g. call_firstn(Goal_0,N)
which succeeds for at most the firstN
many answers of Goal_0
. This in turn can be implemented using call_nth(Goal_0, Nth)
.
findfirstn(N, Template, Goal_0, Instances) :-
findall(Template, call_firstn(Goal_0, N), Instances).
call_firstn(Goal_0, N) :-
N + N mod 1 >= 0, % ensures that N >=0 and N is an integer
call_nth(Goal_0, Nth),
( Nth == N -> ! ; true ).
A full implementation of call_nth/2
that does not leak and still is reentrant cannot be defined in ISO Prolog directly. You need to resort to all kinds of low-level operations with often incomplete semantics that are better hidden from the regular programmer.
This is how you would do it in ECLiPSe:
find_n(N, Term, Goal, Solutions) :-
( N < 1 ->
Solutions = []
;
record_create(Bag),
shelf_create(count(N), Counter),
(
once((
call(Goal),
recordz(Bag, Term),
\+shelf_dec(Counter, 1) % succeed if enough
)),
fail
;
recorded_list(Bag, Solutions)
)
).
This is reentrant and does not leak memory (both are problems with global variable or dynamic predicate based solutions). Small additions are needed if you want it to deal correctly with modules.
You could of course use the same code structure with the assert/retract primitives that Paulo used.