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-2015, University of Amsterdam
   7                              VU University Amsterdam
   8    All rights reserved.
   9
  10    Redistribution and use in source and binary forms, with or without
  11    modification, are permitted provided that the following conditions
  12    are met:
  13
  14    1. Redistributions of source code must retain the above copyright
  15       notice, this list of conditions and the following disclaimer.
  16
  17    2. Redistributions in binary form must reproduce the above copyright
  18       notice, this list of conditions and the following disclaimer in
  19       the documentation and/or other materials provided with the
  20       distribution.
  21
  22    THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
  23    "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
  24    LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS
  25    FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE
  26    COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT,
  27    INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING,
  28    BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
  29    LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
  30    CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
  31    LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN
  32    ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
  33    POSSIBILITY OF SUCH DAMAGE.
  34*/
  35
  36:- module(apply,
  37          [ include/3,                  % :Pred, +List, -Ok
  38            exclude/3,                  % :Pred. +List, -NotOk
  39            partition/4,                % :Pred, +List, -Included, -Excluded
  40            partition/5,                % :Pred, +List, ?Less, ?Equal, ?Greater
  41            maplist/2,                  % :Pred, +List
  42            maplist/3,                  % :Pred, ?List, ?List
  43            maplist/4,                  % :Pred, ?List, ?List, ?List
  44            maplist/5,                  % :Pred, ?List, ?List, ?List, ?List
  45            foldl/4,                    % :Pred, +List, ?V0, ?V
  46            foldl/5,                    % :Pred, +List1, +List2, ?V0, ?V
  47            foldl/6,                    % :Pred, +List1, +List2, +List3, ?V0, ?V
  48            foldl/7,                    % :Pred, +List1, +List2, +List3, +List4,
  49                                        % ?V0, ?V
  50            scanl/4,                    % :Pred, +List, ?V0, ?Vs
  51            scanl/5,                    % :Pred, +List1, +List2, ?V0, ?Vs
  52            scanl/6,                    % :Pred, +List1, +List2, +List3, ?V0, ?Vs
  53            scanl/7                     % :Pred, +List1, +List2, +List3, +List4,
  54                                        % ?V0, ?Vs
  55          ]).
  56:- use_module(library(error)).
  57
  58/** <module> Apply predicates on a list
  59
  60This module defines meta-predicates  that  apply   a  predicate  on  all
  61members of a list.
  62
  63@see    apply_macros.pl provides compile-time expansion for part of this
  64        library.
  65@see    http://www.cs.otago.ac.nz/staffpriv/ok/pllib.htm
  66@tbd    Add include/4, include/5, exclude/4, exclude/5
  67*/
  68
  69:- meta_predicate
  70    include(1, +, -),
  71    exclude(1, +, -),
  72    partition(1, +, -, -),
  73    partition(2, +, -, -, -),
  74    maplist(1, ?),
  75    maplist(2, ?, ?),
  76    maplist(3, ?, ?, ?),
  77    maplist(4, ?, ?, ?, ?),
  78    foldl(3, +, +, -),
  79    foldl(4, +, +, +, -),
  80    foldl(5, +, +, +, +, -),
  81    foldl(6, +, +, +, +, +, -),
  82    scanl(3, +, +, -),
  83    scanl(4, +, +, +, -),
  84    scanl(5, +, +, +, +, -),
  85    scanl(6, +, +, +, +, +, -).
  86
  87
  88%!  include(:Goal, +List1, ?List2) is det.
  89%
  90%   Filter elements for which Goal succeeds.  True if List2 contains
  91%   those elements Xi of List1 for which call(Goal, Xi) succeeds.
  92%
  93%   @see    Older versions of SWI-Prolog had sublist/3 with the same
  94%           arguments and semantics.
  95
  96include(Goal, List, Included) :-
  97    include_(List, Goal, Included).
  98
  99include_([], _, []).
 100include_([X1|Xs1], P, Included) :-
 101    (   call(P, X1)
 102    ->  Included = [X1|Included1]
 103    ;   Included = Included1
 104    ),
 105    include_(Xs1, P, Included1).
 106
 107
 108%!  exclude(:Goal, +List1, ?List2) is det.
 109%
 110%   Filter elements for which Goal fails.  True if List2 contains
 111%   those elements Xi of List1 for which call(Goal, Xi) fails.
 112
 113exclude(Goal, List, Included) :-
 114    exclude_(List, Goal, Included).
 115
 116exclude_([], _, []).
 117exclude_([X1|Xs1], P, Included) :-
 118    (   call(P, X1)
 119    ->  Included = Included1
 120    ;   Included = [X1|Included1]
 121    ),
 122    exclude_(Xs1, P, Included1).
 123
 124
 125%!  partition(:Pred, +List, ?Included, ?Excluded) is det.
 126%
 127%   Filter elements of List according  to   Pred.  True  if Included
 128%   contains all elements  for  which   call(Pred,  X)  succeeds and
 129%   Excluded contains the remaining elements.
 130
 131partition(Pred, List, Included, Excluded) :-
 132    partition_(List, Pred, Included, Excluded).
 133
 134partition_([], _, [], []).
 135partition_([H|T], Pred, Incl, Excl) :-
 136    (   call(Pred, H)
 137    ->  Incl = [H|I],
 138        partition_(T, Pred, I, Excl)
 139    ;   Excl = [H|E],
 140        partition_(T, Pred, Incl, E)
 141    ).
 142
 143
 144%!  partition(:Pred, +List, ?Less, ?Equal, ?Greater) is semidet.
 145%
 146%   Filter List according to Pred in three sets. For each element Xi
 147%   of List, its destination is determined by call(Pred, Xi, Place),
 148%   where Place must be unified to  one   of  =|<|=, =|=|= or =|>|=.
 149%   Pred must be deterministic.
 150
 151partition(Pred, List, Less, Equal, Greater) :-
 152    partition_(List, Pred, Less, Equal, Greater).
 153
 154partition_([], _, [], [], []).
 155partition_([H|T], Pred, L, E, G) :-
 156    call(Pred, H, Diff),
 157    partition_(Diff, H, Pred, T, L, E, G).
 158
 159partition_(<, H, Pred, T, [H|L], E, G) :-
 160    !,
 161    partition_(T, Pred, L, E, G).
 162partition_(=, H, Pred, T, L, [H|E], G) :-
 163    !,
 164    partition_(T, Pred, L, E, G).
 165partition_(>, H, Pred, T, L, E, [H|G]) :-
 166    !,
 167    partition_(T, Pred, L, E, G).
 168partition_(Diff, _, _, _, _, _, _) :-
 169    must_be(oneof([<.=,>]), Diff).
 170
 171
 172                 /*******************************
 173                 *          MAPLIST/2...        *
 174                 *******************************/
 175
 176%!  maplist(:Goal, ?List)
 177%
 178%   True if Goal can successfully  be   applied  on  all elements of
 179%   List. Arguments are reordered to gain  performance as well as to
 180%   make the predicate deterministic under normal circumstances.
 181
 182maplist(Goal, List) :-
 183    maplist_(List, Goal).
 184
 185maplist_([], _).
 186maplist_([Elem|Tail], Goal) :-
 187    call(Goal, Elem),
 188    maplist_(Tail, Goal).
 189
 190%!  maplist(:Goal, ?List1, ?List2)
 191%
 192%   As maplist/2, operating on pairs of elements from two lists.
 193
 194maplist(Goal, List1, List2) :-
 195    maplist_(List1, List2, Goal).
 196
 197maplist_([], [], _).
 198maplist_([Elem1|Tail1], [Elem2|Tail2], Goal) :-
 199    call(Goal, Elem1, Elem2),
 200    maplist_(Tail1, Tail2, Goal).
 201
 202%!  maplist(:Goal, ?List1, ?List2, ?List3)
 203%
 204%   As maplist/2, operating on triples of elements from three lists.
 205
 206maplist(Goal, List1, List2, List3) :-
 207    maplist_(List1, List2, List3, Goal).
 208
 209maplist_([], [], [], _).
 210maplist_([Elem1|Tail1], [Elem2|Tail2], [Elem3|Tail3], Goal) :-
 211    call(Goal, Elem1, Elem2, Elem3),
 212    maplist_(Tail1, Tail2, Tail3, Goal).
 213
 214
 215%!  maplist(:Goal, ?List1, ?List2, ?List3, ?List4)
 216%
 217%   As maplist/2, operating on  quadruples   of  elements  from four
 218%   lists.
 219
 220maplist(Goal, List1, List2, List3, List4) :-
 221    maplist_(List1, List2, List3, List4, Goal).
 222
 223maplist_([], [], [], [], _).
 224maplist_([Elem1|Tail1], [Elem2|Tail2], [Elem3|Tail3], [Elem4|Tail4], Goal) :-
 225    call(Goal, Elem1, Elem2, Elem3, Elem4),
 226    maplist_(Tail1, Tail2, Tail3, Tail4, Goal).
 227
 228
 229                 /*******************************
 230                 *            FOLDL             *
 231                 *******************************/
 232
 233%!  foldl(:Goal, +List, +V0, -V).
 234%!  foldl(:Goal, +List1, +List2, +V0, -V).
 235%!  foldl(:Goal, +List1, +List2, +List3, +V0, -V).
 236%!  foldl(:Goal, +List1, +List2, +List3, +List4, +V0, -V).
 237%
 238%   Fold a list, using arguments of the   list as left argument. The
 239%   foldl family of predicates is defined by:
 240%
 241%     ==
 242%     foldl(P, [X11,...,X1n], ..., [Xm1,...,Xmn], V0, Vn) :-
 243%           P(X11, ..., Xm1, V0, V1),
 244%           ...
 245%           P(X1n, ..., Xmn, V', Vn).
 246%     ==
 247
 248foldl(Goal, List, V0, V) :-
 249    foldl_(List, Goal, V0, V).
 250
 251foldl_([], _, V, V).
 252foldl_([H|T], Goal, V0, V) :-
 253    call(Goal, H, V0, V1),
 254    foldl_(T, Goal, V1, V).
 255
 256
 257foldl(Goal, List1, List2, V0, V) :-
 258    foldl_(List1, List2, Goal, V0, V).
 259
 260foldl_([], [], _, V, V).
 261foldl_([H1|T1], [H2|T2], Goal, V0, V) :-
 262    call(Goal, H1, H2, V0, V1),
 263    foldl_(T1, T2, Goal, V1, V).
 264
 265
 266foldl(Goal, List1, List2, List3, V0, V) :-
 267    foldl_(List1, List2, List3, Goal, V0, V).
 268
 269foldl_([], [], [], _, V, V).
 270foldl_([H1|T1], [H2|T2], [H3|T3], Goal, V0, V) :-
 271    call(Goal, H1, H2, H3, V0, V1),
 272    foldl_(T1, T2, T3, Goal, V1, V).
 273
 274
 275foldl(Goal, List1, List2, List3, List4, V0, V) :-
 276    foldl_(List1, List2, List3, List4, Goal, V0, V).
 277
 278foldl_([], [], [], [], _, V, V).
 279foldl_([H1|T1], [H2|T2], [H3|T3], [H4|T4], Goal, V0, V) :-
 280    call(Goal, H1, H2, H3, H4, V0, V1),
 281    foldl_(T1, T2, T3, T4, Goal, V1, V).
 282
 283
 284                 /*******************************
 285                 *             SCANL            *
 286                 *******************************/
 287
 288%!  scanl(:Goal, +List, +V0, -Values).
 289%!  scanl(:Goal, +List1, +List2, +V0, -Values).
 290%!  scanl(:Goal, +List1, +List2, +List3, +V0, -Values).
 291%!  scanl(:Goal, +List1, +List2, +List3, +List4, +V0, -Values).
 292%
 293%   Left scan of  list.  The  scanl   family  of  higher  order list
 294%   operations is defined by:
 295%
 296%     ==
 297%     scanl(P, [X11,...,X1n], ..., [Xm1,...,Xmn], V0,
 298%           [V0,V1,...,Vn]) :-
 299%           P(X11, ..., Xm1, V0, V1),
 300%           ...
 301%           P(X1n, ..., Xmn, V', Vn).
 302%     ==
 303
 304scanl(Goal, List, V0, [V0|Values]) :-
 305    scanl_(List, Goal, V0, Values).
 306
 307scanl_([], _, _, []).
 308scanl_([H|T], Goal, V, [VH|VT]) :-
 309    call(Goal, H, V, VH),
 310    scanl_(T, Goal, VH, VT).
 311
 312
 313scanl(Goal, List1, List2, V0, [V0|Values]) :-
 314    scanl_(List1, List2, Goal, V0, Values).
 315
 316scanl_([], [], _, _, []).
 317scanl_([H1|T1], [H2|T2], Goal, V, [VH|VT]) :-
 318    call(Goal, H1, H2, V, VH),
 319    scanl_(T1, T2, Goal, VH, VT).
 320
 321
 322scanl(Goal, List1, List2, List3, V0, [V0|Values]) :-
 323    scanl_(List1, List2, List3, Goal, V0, Values).
 324
 325scanl_([], [], [], _, _, []).
 326scanl_([H1|T1], [H2|T2], [H3|T3], Goal, V, [VH|VT]) :-
 327    call(Goal, H1, H2, H3, V, VH),
 328    scanl_(T1, T2, T3, Goal, VH, VT).
 329
 330
 331scanl(Goal, List1, List2, List3, List4, V0, [V0|Values]) :-
 332    scanl_(List1, List2, List3, List4, Goal, V0, Values).
 333
 334scanl_([], [], [], [], _, _, []).
 335scanl_([H1|T1], [H2|T2], [H3|T3], [H4|T4], Goal, V, [VH|VT]) :-
 336    call(Goal, H1, H2, H3, H4, V, VH),
 337    scanl_(T1, T2, T3, T4, Goal, VH, VT).
 338
 339
 340                 /*******************************
 341                 *            SANDBOX           *
 342                 *******************************/
 343
 344:- multifile
 345    sandbox:safe_meta_predicate/1.
 346
 347safe_api(Name/Arity, sandbox:safe_meta_predicate(apply:Name/Arity)).
 348
 349term_expansion(safe_api, Clauses) :-
 350    module_property(apply, exports(API)),
 351    maplist(safe_api, API, Clauses).
 352
 353safe_api.