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            convlist/3,                 % :Pred, +List, -List
   46            foldl/4,                    % :Pred, +List, ?V0, ?V
   47            foldl/5,                    % :Pred, +List1, +List2, ?V0, ?V
   48            foldl/6,                    % :Pred, +List1, +List2, +List3, ?V0, ?V
   49            foldl/7,                    % :Pred, +List1, +List2, +List3, +List4,
   50                                        % ?V0, ?V
   51            scanl/4,                    % :Pred, +List, ?V0, ?Vs
   52            scanl/5,                    % :Pred, +List1, +List2, ?V0, ?Vs
   53            scanl/6,                    % :Pred, +List1, +List2, +List3, ?V0, ?Vs
   54            scanl/7                     % :Pred, +List1, +List2, +List3, +List4,
   55                                        % ?V0, ?Vs
   56          ]).   57:- use_module(library(error)).   58
   59/** <module> Apply predicates on a list
   60
   61This module defines meta-predicates  that  apply   a  predicate  on  all
   62members of a list.
   63
   64@see    apply_macros.pl provides compile-time expansion for part of this
   65        library.
   66@see    http://www.cs.otago.ac.nz/staffpriv/ok/pllib.htm
   67@tbd    Add include/4, include/5, exclude/4, exclude/5
   68*/
   69
   70:- meta_predicate
   71    include(1, +, -),
   72    exclude(1, +, -),
   73    partition(1, +, -, -),
   74    partition(2, +, -, -, -),
   75    maplist(1, ?),
   76    maplist(2, ?, ?),
   77    maplist(3, ?, ?, ?),
   78    maplist(4, ?, ?, ?, ?),
   79    convlist(2, +, -),
   80    foldl(3, +, +, -),
   81    foldl(4, +, +, +, -),
   82    foldl(5, +, +, +, +, -),
   83    foldl(6, +, +, +, +, +, -),
   84    scanl(3, +, +, -),
   85    scanl(4, +, +, +, -),
   86    scanl(5, +, +, +, +, -),
   87    scanl(6, +, +, +, +, +, -).   88
   89
   90%!  include(:Goal, +List1, ?List2) is det.
   91%
   92%   Filter elements for which Goal succeeds.  True if List2 contains
   93%   those elements Xi of List1 for which call(Goal, Xi) succeeds.
   94%
   95%   @see    Older versions of SWI-Prolog had sublist/3 with the same
   96%           arguments and semantics.
   97
   98include(Goal, List, Included) :-
   99    include_(List, Goal, Included).
  100
  101include_([], _, []).
  102include_([X1|Xs1], P, Included) :-
  103    (   call(P, X1)
  104    ->  Included = [X1|Included1]
  105    ;   Included = Included1
  106    ),
  107    include_(Xs1, P, Included1).
  108
  109
  110%!  exclude(:Goal, +List1, ?List2) is det.
  111%
  112%   Filter elements for which Goal fails.  True if List2 contains
  113%   those elements Xi of List1 for which call(Goal, Xi) fails.
  114
  115exclude(Goal, List, Included) :-
  116    exclude_(List, Goal, Included).
  117
  118exclude_([], _, []).
  119exclude_([X1|Xs1], P, Included) :-
  120    (   call(P, X1)
  121    ->  Included = Included1
  122    ;   Included = [X1|Included1]
  123    ),
  124    exclude_(Xs1, P, Included1).
  125
  126
  127%!  partition(:Pred, +List, ?Included, ?Excluded) is det.
  128%
  129%   Filter elements of List according  to   Pred.  True  if Included
  130%   contains all elements  for  which   call(Pred,  X)  succeeds and
  131%   Excluded contains the remaining elements.
  132
  133partition(Pred, List, Included, Excluded) :-
  134    partition_(List, Pred, Included, Excluded).
  135
  136partition_([], _, [], []).
  137partition_([H|T], Pred, Incl, Excl) :-
  138    (   call(Pred, H)
  139    ->  Incl = [H|I],
  140        partition_(T, Pred, I, Excl)
  141    ;   Excl = [H|E],
  142        partition_(T, Pred, Incl, E)
  143    ).
  144
  145
  146%!  partition(:Pred, +List, ?Less, ?Equal, ?Greater) is semidet.
  147%
  148%   Filter List according to Pred in three sets. For each element Xi
  149%   of List, its destination is determined by call(Pred, Xi, Place),
  150%   where Place must be unified to  one   of  =|<|=, =|=|= or =|>|=.
  151%   Pred must be deterministic.
  152
  153partition(Pred, List, Less, Equal, Greater) :-
  154    partition_(List, Pred, Less, Equal, Greater).
  155
  156partition_([], _, [], [], []).
  157partition_([H|T], Pred, L, E, G) :-
  158    call(Pred, H, Diff),
  159    partition_(Diff, H, Pred, T, L, E, G).
  160
  161partition_(<, H, Pred, T, L, E, G) :-
  162    !,
  163    L = [H|Rest],
  164    partition_(T, Pred, Rest, E, G).
  165partition_(=, H, Pred, T, L, E, G) :-
  166    !,
  167    E = [H|Rest],
  168    partition_(T, Pred, L, Rest, G).
  169partition_(>, H, Pred, T, L, E, G) :-
  170    !,
  171    G = [H|Rest],
  172    partition_(T, Pred, L, E, Rest).
  173partition_(Diff, _, _, _, _, _, _) :-
  174    must_be(oneof([<,=,>]), Diff).
  175
  176
  177                 /*******************************
  178                 *          MAPLIST/2...        *
  179                 *******************************/
  180
  181%!  maplist(:Goal, ?List)
  182%
  183%   True if Goal can successfully  be   applied  on  all elements of
  184%   List. Arguments are reordered to gain  performance as well as to
  185%   make the predicate deterministic under normal circumstances.
  186
  187maplist(Goal, List) :-
  188    maplist_(List, Goal).
  189
  190maplist_([], _).
  191maplist_([Elem|Tail], Goal) :-
  192    call(Goal, Elem),
  193    maplist_(Tail, Goal).
  194
  195%!  maplist(:Goal, ?List1, ?List2)
  196%
  197%   As maplist/2, operating on pairs of elements from two lists.
  198
  199maplist(Goal, List1, List2) :-
  200    maplist_(List1, List2, Goal).
  201
  202maplist_([], [], _).
  203maplist_([Elem1|Tail1], [Elem2|Tail2], Goal) :-
  204    call(Goal, Elem1, Elem2),
  205    maplist_(Tail1, Tail2, Goal).
  206
  207%!  maplist(:Goal, ?List1, ?List2, ?List3)
  208%
  209%   As maplist/2, operating on triples of elements from three lists.
  210
  211maplist(Goal, List1, List2, List3) :-
  212    maplist_(List1, List2, List3, Goal).
  213
  214maplist_([], [], [], _).
  215maplist_([Elem1|Tail1], [Elem2|Tail2], [Elem3|Tail3], Goal) :-
  216    call(Goal, Elem1, Elem2, Elem3),
  217    maplist_(Tail1, Tail2, Tail3, Goal).
  218
  219
  220%!  maplist(:Goal, ?List1, ?List2, ?List3, ?List4)
  221%
  222%   As maplist/2, operating on  quadruples   of  elements  from four
  223%   lists.
  224
  225maplist(Goal, List1, List2, List3, List4) :-
  226    maplist_(List1, List2, List3, List4, Goal).
  227
  228maplist_([], [], [], [], _).
  229maplist_([Elem1|Tail1], [Elem2|Tail2], [Elem3|Tail3], [Elem4|Tail4], Goal) :-
  230    call(Goal, Elem1, Elem2, Elem3, Elem4),
  231    maplist_(Tail1, Tail2, Tail3, Tail4, Goal).
  232
  233
  234%!  convlist(:Goal, +ListIn, -ListOut) is det.
  235%
  236%   Similar to maplist/3, but elements for   which call(Goal, ElemIn, _)
  237%   fails are omitted from ListOut.  For example (using library(yall)):
  238%
  239%   ```
  240%   ?- convlist([X,Y]>>(integer(X), Y is X^2),
  241%               [3, 5, 4.4, 2], L).
  242%   L = [9, 25, 4].
  243%   ```
  244%
  245%   @compat  Also  appears  in  YAP   =|library(maplist)|=  and  SICStus
  246%   =|library(lists)|=.
  247
  248convlist(Goal, ListIn, ListOut) :-
  249    convlist_(ListIn, ListOut, Goal).
  250
  251convlist_([], [], _).
  252convlist_([H0|T0], ListOut, Goal) :-
  253    (   call(Goal, H0, H)
  254    ->  ListOut = [H|T],
  255        convlist_(T0, T, Goal)
  256    ;   convlist_(T0, ListOut, Goal)
  257    ).
  258
  259
  260                 /*******************************
  261                 *            FOLDL             *
  262                 *******************************/
  263
  264%!  foldl(:Goal, +List, +V0, -V).
  265%!  foldl(:Goal, +List1, +List2, +V0, -V).
  266%!  foldl(:Goal, +List1, +List2, +List3, +V0, -V).
  267%!  foldl(:Goal, +List1, +List2, +List3, +List4, +V0, -V).
  268%
  269%   Fold a list, using arguments of the   list as left argument. The
  270%   foldl family of predicates is defined by:
  271%
  272%     ==
  273%     foldl(P, [X11,...,X1n], ..., [Xm1,...,Xmn], V0, Vn) :-
  274%           P(X11, ..., Xm1, V0, V1),
  275%           ...
  276%           P(X1n, ..., Xmn, V', Vn).
  277%     ==
  278
  279foldl(Goal, List, V0, V) :-
  280    foldl_(List, Goal, V0, V).
  281
  282foldl_([], _, V, V).
  283foldl_([H|T], Goal, V0, V) :-
  284    call(Goal, H, V0, V1),
  285    foldl_(T, Goal, V1, V).
  286
  287
  288foldl(Goal, List1, List2, V0, V) :-
  289    foldl_(List1, List2, Goal, V0, V).
  290
  291foldl_([], [], _, V, V).
  292foldl_([H1|T1], [H2|T2], Goal, V0, V) :-
  293    call(Goal, H1, H2, V0, V1),
  294    foldl_(T1, T2, Goal, V1, V).
  295
  296
  297foldl(Goal, List1, List2, List3, V0, V) :-
  298    foldl_(List1, List2, List3, Goal, V0, V).
  299
  300foldl_([], [], [], _, V, V).
  301foldl_([H1|T1], [H2|T2], [H3|T3], Goal, V0, V) :-
  302    call(Goal, H1, H2, H3, V0, V1),
  303    foldl_(T1, T2, T3, Goal, V1, V).
  304
  305
  306foldl(Goal, List1, List2, List3, List4, V0, V) :-
  307    foldl_(List1, List2, List3, List4, Goal, V0, V).
  308
  309foldl_([], [], [], [], _, V, V).
  310foldl_([H1|T1], [H2|T2], [H3|T3], [H4|T4], Goal, V0, V) :-
  311    call(Goal, H1, H2, H3, H4, V0, V1),
  312    foldl_(T1, T2, T3, T4, Goal, V1, V).
  313
  314
  315                 /*******************************
  316                 *             SCANL            *
  317                 *******************************/
  318
  319%!  scanl(:Goal, +List, +V0, -Values).
  320%!  scanl(:Goal, +List1, +List2, +V0, -Values).
  321%!  scanl(:Goal, +List1, +List2, +List3, +V0, -Values).
  322%!  scanl(:Goal, +List1, +List2, +List3, +List4, +V0, -Values).
  323%
  324%   Left scan of  list.  The  scanl   family  of  higher  order list
  325%   operations is defined by:
  326%
  327%     ==
  328%     scanl(P, [X11,...,X1n], ..., [Xm1,...,Xmn], V0,
  329%           [V0,V1,...,Vn]) :-
  330%           P(X11, ..., Xm1, V0, V1),
  331%           ...
  332%           P(X1n, ..., Xmn, V', Vn).
  333%     ==
  334
  335scanl(Goal, List, V0, [V0|Values]) :-
  336    scanl_(List, Goal, V0, Values).
  337
  338scanl_([], _, _, []).
  339scanl_([H|T], Goal, V, [VH|VT]) :-
  340    call(Goal, H, V, VH),
  341    scanl_(T, Goal, VH, VT).
  342
  343
  344scanl(Goal, List1, List2, V0, [V0|Values]) :-
  345    scanl_(List1, List2, Goal, V0, Values).
  346
  347scanl_([], [], _, _, []).
  348scanl_([H1|T1], [H2|T2], Goal, V, [VH|VT]) :-
  349    call(Goal, H1, H2, V, VH),
  350    scanl_(T1, T2, Goal, VH, VT).
  351
  352
  353scanl(Goal, List1, List2, List3, V0, [V0|Values]) :-
  354    scanl_(List1, List2, List3, Goal, V0, Values).
  355
  356scanl_([], [], [], _, _, []).
  357scanl_([H1|T1], [H2|T2], [H3|T3], Goal, V, [VH|VT]) :-
  358    call(Goal, H1, H2, H3, V, VH),
  359    scanl_(T1, T2, T3, Goal, VH, VT).
  360
  361
  362scanl(Goal, List1, List2, List3, List4, V0, [V0|Values]) :-
  363    scanl_(List1, List2, List3, List4, Goal, V0, Values).
  364
  365scanl_([], [], [], [], _, _, []).
  366scanl_([H1|T1], [H2|T2], [H3|T3], [H4|T4], Goal, V, [VH|VT]) :-
  367    call(Goal, H1, H2, H3, H4, V, VH),
  368    scanl_(T1, T2, T3, T4, Goal, VH, VT).
  369
  370
  371                 /*******************************
  372                 *            SANDBOX           *
  373                 *******************************/
  374
  375:- multifile
  376    sandbox:safe_meta_predicate/1.  377
  378safe_api(Name/Arity, sandbox:safe_meta_predicate(apply:Name/Arity)).
  379
  380term_expansion(safe_api, Clauses) :-
  381    module_property(apply, exports(API)),
  382    maplist(safe_api, API, Clauses).
  383
  384safe_api