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) 2007-2020, University of Amsterdam 7 VU University Amsterdam 8 SWI-Prolog Solutions b.v. 9 All rights reserved. 10 11 Redistribution and use in source and binary forms, with or without 12 modification, are permitted provided that the following conditions 13 are met: 14 15 1. Redistributions of source code must retain the above copyright 16 notice, this list of conditions and the following disclaimer. 17 18 2. Redistributions in binary form must reproduce the above copyright 19 notice, this list of conditions and the following disclaimer in 20 the documentation and/or other materials provided with the 21 distribution. 22 23 THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 24 "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 25 LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS 26 FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE 27 COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, 28 INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, 29 BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; 30 LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER 31 CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 32 LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN 33 ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE 34 POSSIBILITY OF SUCH DAMAGE. 35*/ 36 37:- module(apply, 38 [ include/3, % :Pred, +List, -Ok 39 exclude/3, % :Pred. +List, -NotOk 40 partition/4, % :Pred, +List, -Included, -Excluded 41 partition/5, % :Pred, +List, ?Less, ?Equal, ?Greater 42 maplist/2, % :Pred, +List 43 maplist/3, % :Pred, ?List, ?List 44 maplist/4, % :Pred, ?List, ?List, ?List 45 maplist/5, % :Pred, ?List, ?List, ?List, ?List 46 convlist/3, % :Pred, +List, -List 47 foldl/4, % :Pred, +List, ?V0, ?V 48 foldl/5, % :Pred, +List1, +List2, ?V0, ?V 49 foldl/6, % :Pred, +List1, +List2, +List3, ?V0, ?V 50 foldl/7, % :Pred, +List1, +List2, +List3, +List4, 51 % ?V0, ?V 52 scanl/4, % :Pred, +List, ?V0, ?Vs 53 scanl/5, % :Pred, +List1, +List2, ?V0, ?Vs 54 scanl/6, % :Pred, +List1, +List2, +List3, ?V0, ?Vs 55 scanl/7 % :Pred, +List1, +List2, +List3, +List4, 56 % ?V0, ?Vs 57 ]). 58:- autoload(library(error),[must_be/2]). 59 60/** <module> Apply predicates on a list 61 62This module defines meta-predicates that apply a predicate on all 63members of a list. 64 65All predicates support partial application in the Goal argument. This 66means that these calls are identical: 67 68``` 69?- maplist(=, [foo, foo], [X, Y]). 70?- maplist(=(foo), [X, Y]). 71``` 72 73@see apply_macros.pl provides compile-time expansion for part of this 74 library. 75@see http://www.cs.otago.ac.nz/staffpriv/ok/pllib.htm 76@see Unit test code in src/Tests/library/test_apply.pl 77@tbd Add include/4, include/5, exclude/4, exclude/5 78*/ 79 80:- meta_predicate 81 include(, , ), 82 exclude(, , ), 83 partition(, , , ), 84 partition(, , , , ), 85 maplist(, ), 86 maplist(, , ), 87 maplist(, , , ), 88 maplist(, , , , ), 89 convlist(, , ), 90 foldl(, , , ), 91 foldl(, , , , ), 92 foldl(, , , , , ), 93 foldl(, , , , , , ), 94 scanl(, , , ), 95 scanl(, , , , ), 96 scanl(, , , , , ), 97 scanl(, , , , , , ). 98 99 100%! include(:Goal, +List1, ?List2) is det. 101% 102% Filter elements for which Goal succeeds. True if List2 contains 103% those elements Xi of List1 for which call(Goal, Xi) succeeds. 104% 105% @see exclude/3, partition/4, convlist/3. 106% @compat Older versions of SWI-Prolog had sublist/3 with the same 107% arguments and semantics. 108 109include(Goal, List, Included) :- 110 include_(List, Goal, Included). 111 112include_([], _, []). 113include_([X1|Xs1], P, Included) :- 114 ( call(P, X1) 115 -> Included = [X1|Included1] 116 ; Included = Included1 117 ), 118 include_(Xs1, P, Included1). 119 120 121%! exclude(:Goal, +List1, ?List2) is det. 122% 123% Filter elements for which Goal fails. True if List2 contains those 124% elements Xi of List1 for which call(Goal, Xi) fails. 125% 126% @see include/3, partition/4 127 128exclude(Goal, List, Included) :- 129 exclude_(List, Goal, Included). 130 131exclude_([], _, []). 132exclude_([X1|Xs1], P, Included) :- 133 ( call(P, X1) 134 -> Included = Included1 135 ; Included = [X1|Included1] 136 ), 137 exclude_(Xs1, P, Included1). 138 139 140%! partition(:Pred, +List, ?Included, ?Excluded) is det. 141% 142% Filter elements of List according to Pred. True if Included 143% contains all elements for which call(Pred, X) succeeds and 144% Excluded contains the remaining elements. 145% 146% @see include/3, exclude/3, partition/5. 147 148partition(Pred, List, Included, Excluded) :- 149 partition_(List, Pred, Included, Excluded). 150 151partition_([], _, [], []). 152partition_([H|T], Pred, Incl, Excl) :- 153 ( call(Pred, H) 154 -> Incl = [H|I], 155 partition_(T, Pred, I, Excl) 156 ; Excl = [H|E], 157 partition_(T, Pred, Incl, E) 158 ). 159 160 161%! partition(:Pred, +List, ?Less, ?Equal, ?Greater) is semidet. 162% 163% Filter List according to Pred in three sets. For each element Xi 164% of List, its destination is determined by call(Pred, Xi, Place), 165% where Place must be unified to one of =|<|=, =|=|= or =|>|=. 166% Pred must be deterministic. 167% 168% @see partition/4 169 170partition(Pred, List, Less, Equal, Greater) :- 171 partition_(List, Pred, Less, Equal, Greater). 172 173partition_([], _, [], [], []). 174partition_([H|T], Pred, L, E, G) :- 175 call(Pred, H, Diff), 176 partition_(Diff, H, Pred, T, L, E, G). 177 178partition_(<, H, Pred, T, L, E, G) :- 179 !, 180 L = [H|Rest], 181 partition_(T, Pred, Rest, E, G). 182partition_(=, H, Pred, T, L, E, G) :- 183 !, 184 E = [H|Rest], 185 partition_(T, Pred, L, Rest, G). 186partition_(>, H, Pred, T, L, E, G) :- 187 !, 188 G = [H|Rest], 189 partition_(T, Pred, L, E, Rest). 190partition_(Diff, _, _, _, _, _, _) :- 191 must_be(oneof([<,=,>]), Diff). 192 193 194 /******************************* 195 * MAPLIST * 196 *******************************/ 197 198%! maplist(:Goal, ?List1). 199%! maplist(:Goal, ?List1, ?List2). 200%! maplist(:Goal, ?List1, ?List2, ?List3). 201%! maplist(:Goal, ?List1, ?List2, ?List3, ?List4). 202% 203% True if Goal is successfully applied on all matching elements of the 204% list. The maplist family of predicates is defined as: 205% 206% ``` 207% maplist(G, [X_11, ..., X_1n], 208% [X_21, ..., X_2n], 209% ..., 210% [X_m1, ..., X_mn]) :- 211% call(G, X_11, ..., X_m1), 212% call(G, X_12, ..., X_m2), 213% ... 214% call(G, X_1n, ..., X_mn). 215% ``` 216% 217% This family of predicates is deterministic iff Goal is deterministic 218% and List1 is a proper list, i.e., a list that ends in `[]`. 219 220maplist(Goal, List) :- 221 maplist_(List, Goal). 222 223maplist_([], _). 224maplist_([Elem|Tail], Goal) :- 225 call(Goal, Elem), 226 maplist_(Tail, Goal). 227 228maplist(Goal, List1, List2) :- 229 maplist_(List1, List2, Goal). 230 231maplist_([], [], _). 232maplist_([Elem1|Tail1], [Elem2|Tail2], Goal) :- 233 call(Goal, Elem1, Elem2), 234 maplist_(Tail1, Tail2, Goal). 235 236maplist(Goal, List1, List2, List3) :- 237 maplist_(List1, List2, List3, Goal). 238 239maplist_([], [], [], _). 240maplist_([Elem1|Tail1], [Elem2|Tail2], [Elem3|Tail3], Goal) :- 241 call(Goal, Elem1, Elem2, Elem3), 242 maplist_(Tail1, Tail2, Tail3, Goal). 243 244maplist(Goal, List1, List2, List3, List4) :- 245 maplist_(List1, List2, List3, List4, Goal). 246 247maplist_([], [], [], [], _). 248maplist_([Elem1|Tail1], [Elem2|Tail2], [Elem3|Tail3], [Elem4|Tail4], Goal) :- 249 call(Goal, Elem1, Elem2, Elem3, Elem4), 250 maplist_(Tail1, Tail2, Tail3, Tail4, Goal). 251 252 253%! convlist(:Goal, +ListIn, -ListOut) is det. 254% 255% Similar to maplist/3, but elements for which call(Goal, ElemIn, _) 256% fails are omitted from ListOut. For example (using library(yall)): 257% 258% ``` 259% ?- convlist([X,Y]>>(integer(X), Y is X^2), 260% [3, 5, foo, 2], L). 261% L = [9, 25, 4]. 262% ``` 263% 264% @compat Also appears in YAP =|library(maplist)|= and SICStus 265% =|library(lists)|=. 266 267convlist(Goal, ListIn, ListOut) :- 268 convlist_(ListIn, ListOut, Goal). 269 270convlist_([], [], _). 271convlist_([H0|T0], ListOut, Goal) :- 272 ( call(Goal, H0, H) 273 -> ListOut = [H|T], 274 convlist_(T0, T, Goal) 275 ; convlist_(T0, ListOut, Goal) 276 ). 277 278 279 /******************************* 280 * FOLDL * 281 *******************************/ 282 283%! foldl(:Goal, +List, +V0, -V). 284%! foldl(:Goal, +List1, +List2, +V0, -V). 285%! foldl(:Goal, +List1, +List2, +List3, +V0, -V). 286%! foldl(:Goal, +List1, +List2, +List3, +List4, +V0, -V). 287% 288% Fold an ensemble of _m_ (0 <= _m_ <= 4) lists of length _n_ 289% head-to-tail ("fold-left"), using columns of _m_ list elements as 290% arguments for Goal. The `foldl` family of predicates is defined as 291% follows, with `V0` an initial value and `V` the final value of the 292% folding operation: 293% 294% ``` 295% foldl(G, [X_11, ..., X_1n], 296% [X_21, ..., X_2n], 297% ..., 298% [X_m1, ..., X_mn], V0, V) :- 299% call(G, X_11, ..., X_m1, V0, V1), 300% call(G, X_12, ..., X_m2, V1, V2), 301% ... 302% call(G, X_1n, ..., X_mn, V<n-1>, V). 303% ``` 304% 305% No implementation for a corresponding `foldr` is given. A `foldr` 306% implementation would consist in first calling reverse/2 on each of 307% the _m_ input lists, then applying the appropriate `foldl`. This is 308% actually more efficient than using a properly programmed-out 309% recursive algorithm that cannot be tail-call optimized. 310 311foldl(Goal, List, V0, V) :- 312 foldl_(List, Goal, V0, V). 313 314foldl_([], _, V, V). 315foldl_([H|T], Goal, V0, V) :- 316 call(Goal, H, V0, V1), 317 foldl_(T, Goal, V1, V). 318 319 320foldl(Goal, List1, List2, V0, V) :- 321 foldl_(List1, List2, Goal, V0, V). 322 323foldl_([], [], _, V, V). 324foldl_([H1|T1], [H2|T2], Goal, V0, V) :- 325 call(Goal, H1, H2, V0, V1), 326 foldl_(T1, T2, Goal, V1, V). 327 328 329foldl(Goal, List1, List2, List3, V0, V) :- 330 foldl_(List1, List2, List3, Goal, V0, V). 331 332foldl_([], [], [], _, V, V). 333foldl_([H1|T1], [H2|T2], [H3|T3], Goal, V0, V) :- 334 call(Goal, H1, H2, H3, V0, V1), 335 foldl_(T1, T2, T3, Goal, V1, V). 336 337 338foldl(Goal, List1, List2, List3, List4, V0, V) :- 339 foldl_(List1, List2, List3, List4, Goal, V0, V). 340 341foldl_([], [], [], [], _, V, V). 342foldl_([H1|T1], [H2|T2], [H3|T3], [H4|T4], Goal, V0, V) :- 343 call(Goal, H1, H2, H3, H4, V0, V1), 344 foldl_(T1, T2, T3, T4, Goal, V1, V). 345 346 347 /******************************* 348 * SCANL * 349 *******************************/ 350 351%! scanl(:Goal, +List, +V0, -Values). 352%! scanl(:Goal, +List1, +List2, +V0, -Values). 353%! scanl(:Goal, +List1, +List2, +List3, +V0, -Values). 354%! scanl(:Goal, +List1, +List2, +List3, +List4, +V0, -Values). 355% 356% Scan an ensemble of _m_ (0 <= _m_ <= 4) lists of length _n_ 357% head-to-tail ("scan-left"), using columns of _m_ list elements as 358% arguments for Goal. The `scanl` family of predicates is defined as 359% follows, with `V0` an initial value and `V` the final value of the 360% scanning operation: 361% 362% ``` 363% scanl(G, [X_11, ..., X_1n], 364% [X_21, ..., X_2n], 365% ..., 366% [X_m1, ..., X_mn], V0, [V0, V1, ..., Vn] ) :- 367% call(G, X_11, ..., X_m1, V0, V1), 368% call(G, X_12, ..., X_m2, V1, V2), 369% ... 370% call(G, X_1n, ..., X_mn, V<n-1>, Vn). 371% ``` 372% 373% `scanl` behaves like a `foldl` that collects the sequence of 374% values taken on by the `Vx` accumulator into a list. 375 376scanl(Goal, List, V0, [V0|Values]) :- 377 scanl_(List, Goal, V0, Values). 378 379scanl_([], _, _, []). 380scanl_([H|T], Goal, V, [VH|VT]) :- 381 call(Goal, H, V, VH), 382 scanl_(T, Goal, VH, VT). 383 384 385scanl(Goal, List1, List2, V0, [V0|Values]) :- 386 scanl_(List1, List2, Goal, V0, Values). 387 388scanl_([], [], _, _, []). 389scanl_([H1|T1], [H2|T2], Goal, V, [VH|VT]) :- 390 call(Goal, H1, H2, V, VH), 391 scanl_(T1, T2, Goal, VH, VT). 392 393 394scanl(Goal, List1, List2, List3, V0, [V0|Values]) :- 395 scanl_(List1, List2, List3, Goal, V0, Values). 396 397scanl_([], [], [], _, _, []). 398scanl_([H1|T1], [H2|T2], [H3|T3], Goal, V, [VH|VT]) :- 399 call(Goal, H1, H2, H3, V, VH), 400 scanl_(T1, T2, T3, Goal, VH, VT). 401 402 403scanl(Goal, List1, List2, List3, List4, V0, [V0|Values]) :- 404 scanl_(List1, List2, List3, List4, Goal, V0, Values). 405 406scanl_([], [], [], [], _, _, []). 407scanl_([H1|T1], [H2|T2], [H3|T3], [H4|T4], Goal, V, [VH|VT]) :- 408 call(Goal, H1, H2, H3, H4, V, VH), 409 scanl_(T1, T2, T3, T4, Goal, VH, VT). 410 411 412 /******************************* 413 * SANDBOX * 414 *******************************/ 415 416:- multifile 417 sandbox:safe_meta_predicate/1. 418 419safe_api(Name/Arity, sandbox:safe_meta_predicate(apply:Name/Arity)). 420 421term_expansion(safe_api, Clauses) :- 422 module_property(apply, exports(API)), 423 maplist(safe_api, API, Clauses). 424 425safe_api