1/* Part of SWI-Prolog 2 3 Author: Jan Wielemaker 4 E-mail: J.Wielemaker@vu.nl 5 WWW: http://www.swi-prolog.org 6 Copyright (c) 2015-2017, VU University Amsterdam 7 All rights reserved. 8 9 Redistribution and use in source and binary forms, with or without 10 modification, are permitted provided that the following conditions 11 are met: 12 13 1. Redistributions of source code must retain the above copyright 14 notice, this list of conditions and the following disclaimer. 15 16 2. Redistributions in binary form must reproduce the above copyright 17 notice, this list of conditions and the following disclaimer in 18 the documentation and/or other materials provided with the 19 distribution. 20 21 THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 22 "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 23 LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS 24 FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE 25 COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, 26 INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, 27 BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; 28 LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER 29 CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 30 LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN 31 ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE 32 POSSIBILITY OF SUCH DAMAGE. 33*/ 34 35:- module(solution_sequences, 36 [ distinct/1, % :Goal 37 distinct/2, % ?Witness, :Goal 38 reduced/1, % :Goal 39 reduced/3, % ?Witness, :Goal, +Options 40 limit/2, % +Limit, :Goal 41 offset/2, % +Offset, :Goal 42 call_nth/2, % :Goal, ?Nth 43 order_by/2, % +Spec, :Goal 44 group_by/4 % +By, +Template, :Goal, -Bag 45 ]). 46:- autoload(library(apply),[maplist/3]). 47:- autoload(library(error), 48 [domain_error/2,must_be/2,instantiation_error/1]). 49:- autoload(library(lists),[reverse/2,member/2]). 50:- autoload(library(nb_set), 51 [empty_nb_set/1,add_nb_set/3,size_nb_set/2]). 52:- autoload(library(option),[option/3]). 53:- autoload(library(ordsets),[ord_subtract/3]).
107:- meta_predicate 108 distinct( ), 109 distinct( , ), 110 reduced( ), 111 reduced( , , ), 112 limit( , ), 113 offset( , ), 114 call_nth( , ), 115 order_by( , ), 116 group_by( , , , ). 117 118:- noprofile(( 119 distinct/1, 120 distinct/2, 121 reduced/1, 122 reduced/2, 123 limit/2, 124 offset/2, 125 call_nth/2, 126 order_by/2, 127 group_by/3)).
distinct(Goal,Goal)
.
If the answers are ground terms, the predicate behaves as the code below, but answers are returned as soon as they become available rather than first computing the complete answer set.
distinct(Goal) :- findall(Goal, Goal, List), list_to_set(List, Set), member(Goal, Set).
149distinct(Goal) :- 150 distinct(Goal, Goal). 151distinct(Witness, Goal) :- 152 term_variables(Witness, Vars), 153 Witness1 =.. [v|Vars], 154 empty_nb_set(Set), 155 call(Goal), 156 add_nb_set(Witness1, Set, true).
173reduced(Goal) :- 174 reduced(Goal, Goal, []). 175reduced(Witness, Goal, Options) :- 176 option(size_limit(SizeLimit), Options, 10_000), 177 term_variables(Witness, Vars), 178 Witness1 =.. [v|Vars], 179 empty_nb_set(Set), 180 State = state(Set), 181 call(Goal), 182 reduced_(State, Witness1, SizeLimit). 183 184reduced_(State, Witness1, SizeLimit) :- 185 arg(1, State, Set), 186 add_nb_set(Witness1, Set, true), 187 size_nb_set(Set, Size), 188 ( Size > SizeLimit 189 -> empty_nb_set(New), 190 nb_setarg(1, State, New) 191 ; true 192 ).
205limit(Count, Goal) :- 206 Count == infinite, 207 !, 208 call(Goal). 209limit(Count, Goal) :- 210 Count > 0, 211 State = count(0), 212 call(Goal), 213 arg(1, State, N0), 214 N is N0+1, 215 ( N =:= Count 216 -> ! 217 ; nb_setarg(1, State, N) 218 ).
226offset(Count, Goal) :- 227 Count > 0, 228 !, 229 State = count(0), 230 call(Goal), 231 arg(1, State, N0), 232 ( N0 >= Count 233 -> true 234 ; N is N0+1, 235 nb_setarg(1, State, N), 236 fail 237 ). 238offset(Count, Goal) :- 239 Count =:= 0, 240 !, 241 call(Goal). 242offset(Count, _) :- 243 domain_error(not_less_than_zero, Count).
251call_nth(Goal, Nth) :- 252 integer(Nth), 253 !, 254 ( Nth > 0 255 -> ( call_nth(Goal, Sofar), 256 Sofar =:= Nth 257 -> true 258 ) 259 ; domain_error(not_less_than_one, Nth) 260 ). 261call_nth(Goal, Nth) :- 262 var(Nth), 263 !, 264 State = count(0), 265 call(Goal), 266 arg(1, State, N0), 267 Nth is N0+1, 268 nb_setarg(1, State, Nth). 269call_nth(_Goal, Bad) :- 270 must_be(integer, Bad).
284order_by(Spec, Goal) :- 285 must_be(list, Spec), 286 non_empty_list(Spec), 287 maplist(order_witness, Spec, Witnesses0), 288 join_orders(Witnesses0, Witnesses), 289 non_witness_template(Goal, Witnesses, Others), 290 reverse(Witnesses, RevWitnesses), 291 maplist(x_vars, RevWitnesses, WitnessVars), 292 Template =.. [v,Others|WitnessVars], 293 findall(Template, Goal, Results), 294 order(RevWitnesses, 2, Results, OrderedResults), 295 member(Template, OrderedResults). 296 297order([], _, Results, Results). 298order([H|T], N, Results0, Results) :- 299 order1(H, N, Results0, Results1), 300 N2 is N + 1, 301 order(T, N2, Results1, Results). 302 303order1(asc(_), N, Results0, Results) :- 304 sort(N, @=<, Results0, Results). 305order1(desc(_), N, Results0, Results) :- 306 sort(N, @>=, Results0, Results). 307 308non_empty_list([]) :- 309 !, 310 domain_error(non_empty_list, []). 311non_empty_list(_). 312 313order_witness(Var, _) :- 314 var(Var), 315 !, 316 instantiation_error(Var). 317order_witness(asc(Term), asc(Witness)) :- 318 !, 319 witness(Term, Witness). 320order_witness(desc(Term), desc(Witness)) :- 321 !, 322 witness(Term, Witness). 323order_witness(Term, _) :- 324 domain_error(order_specifier, Term). 325 326x_vars(asc(Vars), Vars). 327x_vars(desc(Vars), Vars). 328 329witness(Term, Witness) :- 330 term_variables(Term, Vars), 331 Witness =.. [v|Vars].
asc(v(A))
, asc(v(B))
] becomes [asc(v(A,B))
].338join_orders([], []). 339join_orders([asc(O1)|T0], [asc(O)|T]) :- 340 !, 341 ascs(T0, OL, T1), 342 join_witnesses(O1, OL, O), 343 join_orders(T1, T). 344join_orders([desc(O1)|T0], [desc(O)|T]) :- 345 !, 346 descs(T0, OL, T1), 347 join_witnesses(O1, OL, O), 348 join_orders(T1, T). 349 350ascs([asc(A)|T0], [A|AL], T) :- 351 !, 352 ascs(T0, AL, T). 353ascs(L, [], L). 354 355descs([desc(A)|T0], [A|AL], T) :- 356 !, 357 descs(T0, AL, T). 358descs(L, [], L). 359 360join_witnesses(O, [], O) :- !. 361join_witnesses(O, OL, R) :- 362 term_variables([O|OL], VL), 363 R =.. [v|VL].
370non_witness_template(Goal, Witness, Template) :- 371 ordered_term_variables(Goal, AllVars), 372 ordered_term_variables(Witness, WitnessVars), 373 ord_subtract(AllVars, WitnessVars, TemplateVars), 374 Template =.. [t|TemplateVars]. 375 376ordered_term_variables(Term, Vars) :- 377 term_variables(Term, Vars0), 378 sort(Vars0, Vars).
388group_by(By, Template, Goal, Bag) :-
389 ordered_term_variables(Goal, GVars),
390 ordered_term_variables(By+Template, UVars),
391 ord_subtract(GVars, UVars, ExVars),
392 bagof(Template, ExVars^, Bag)
Modify solution sequences
The meta predicates of this library modify the sequence of solutions of a goal. The modifications and the predicate names are based on the classical database operations DISTINCT, LIMIT, OFFSET, ORDER BY and GROUP BY.
These predicates were introduced in the context of the SWISH Prolog browser-based shell, which can represent the solutions to a predicate as a table. Notably wrapping a goal in distinct/1 avoids duplicates in the result table and using order_by/2 produces a nicely ordered table.
However, the predicates from this library can also be used to stay longer within the clean paradigm where non-deterministic predicates are composed from simpler non-deterministic predicates by means of conjunction and disjunction. While evaluating a conjunction, we might want to eliminate duplicates of the first part of the conjunction. Below we give both the classical solution for solving variations of (
a(X)
,b(X)
) and the ones using this library side-by-side.Note that the distinct/1 based solution returns the first result of
distinct(a(X))
immediately after a/1 produces a result, while the setof/3 based solution will first compute all results of a/1.b(X)
only for the top-10a(X)
Here we see power of composing primitives from this library and staying within the paradigm of pure non-deterministic relational predicates.
library(aggregate)
*/