Say I want to find sum of all solutions to a predicate, I just can use
findall(L, find(L), Sols),
and just sum members of Sols.
But what if find(L) has a huge number (infinitely, maybe) of solutions, and I just want to get only first 10 of them?
I'd want this to be usable in B-Prolog and ECLiPSe CLP.
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.
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.
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.
SWI-Prolog offers the built-in predicates findnsols/4 and findnsols/5
?- findnsols(5, I, between(1, 12, I), L).
L = [1, 2, 3, 4, 5] ;
L = [6, 7, 8, 9, 10] ;
L = [11, 12].
You may want to wrap the whole call in once/1 to prevent backtracking for further solution groups (e.g. if in the example above you want the 1-5 list to be your ONLY solution).
?- once( findnsols(5, I, between(1, 12, I), L) ).
L = [1, 2, 3, 4, 5].
I've just realized that in B-Prolog it's trivial to do via tabling:
%% an example predicate with infinite solutions
%% from ChristianF answer.
find(0).
find(X) :- find(X1), X is X1+1.
:- table find(-).
?- table_cardinality_limit(find/1, 10), findall(X, find(X), L).
L = [0,1,2,3,4,5,6,7,8,9]
yes
The Logtalk threaded engines API or the SWI-Prolog coroutining engines API, both added recently, provide an alternative solution. For example, using Logtalk threaded engines:
find_at_most(N, Template, Goal, List) :-
threaded_engine_create(Template, Goal, Engine),
collect_at_most(N, Engine, List0),
threaded_engine_destroy(Engine),
List = List0.
collect_at_most(N, Engine, [X| Xs]) :-
N > 0,
threaded_engine_next(Engine, X),
!,
M is N - 1,
collect_at_most(M, Engine, Xs).
collect_at_most(_, _, []).
The threaded_engine_create/3 predicate computes the first solution and then suspends waiting for it to be retrieved by the threaded_engine_next/2 predicate. When a solution is retrieved, the engine starts computing the next solution, again suspending until it's consumed (when a call to the threaded_engine_next/2 predicate happens before a solution is ready, this predicate simply blocks waiting for it). Thus, at most N solutions are computed.
The solution using SWI-Prolog coroutining engines is almost identical but without the blocking semantics (in the threaded engines version) and expected to be more efficient unless the implicit overhead of threads is offset by exploiting concurrency (elsewhere) in the application:
find_at_most(N, Template, Goal, List) :-
engine_create(Template, Goal, Engine),
collect_at_most(N, Engine, List0),
engine_destroy(Engine),
List = List0.
collect_at_most(N, Engine, [X| Xs]) :-
N > 0,
engine_next(Engine, X),
!,
M is N - 1,
collect_at_most(M, Engine, Xs).
collect_at_most(_, _, []).
Both APIs also support reified versions of the _next/2 predicates, and thus alternative implementations of the find_at_most/4 predicate, if you want to get rid of the cut in the auxiliary predicate.
Last, but not the least, the solution presented here originated from Paul Tarau work and papers on engines.
I think you will need to manually implement the uniqueness condition that is implied in findall, i.e., you will need to aggregate solutions and for each new one check that it hasn't yet been picked before.
Here is an example of how this can work:
%% an example predicate with infinite solutions
find(0).
find(X) :- find(X1), X is X1+1.
%% myfindall(+Num) holds when there are at least Num different solutions for find
myfindall(Num) :-
length(L, Num),
mfa_aux(L, [], All),
%% now do something with All, e.g., sum it.
writeln(All).
mfa_aux([], All, All).
mfa_aux([H|T], All, Rtv) :-
find(H),
not(member(H, All)), !,
mfa_aux(T, [H|All], Rtv).
%% Test
%% ?- myfindall(10).
Needing to make a thread-safe solution in SWI Prolog, I came with this:
find_n( N, Solution, Goal, Solutions ) :-
thread_self( Thread_id ),
atomic_list_concat( [counter, Thread_id], Counter_flag_key ),
flag( Counter_flag_key, _, 0 ),
findall( Solution, (
call( Goal ),
flag( Counter_flag_key, X, X ),
X1 is X + 1,
flag( Counter_flag_key, _, X1 ),
( X1 >= N -> !; true )
), Solutions ).
You can combine findall/3 with limit/2 from the library solution
sequence, inspired from SQL:
limit(+Count, :Goal)
Limit the number of solutions
https://www.swi-prolog.org/pldoc/man?predicate=limit/2
Here is an example run:
?- findall(X, limit(3, (repeat, X = 1)), L).
L = [1, 1, 1].
A couple of Prolog systems have predicates like limit/2
in their repertoire.