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