View source with formatted comments or as raw
    1/*  Part of SWI-Prolog
    2
    3    Author:        Jan Wielemaker and Richard O'Keefe
    4    E-mail:        J.Wielemaker@cs.vu.nl
    5    WWW:           http://www.swi-prolog.org
    6    Copyright (c)  2002-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(lists,
   38        [ member/2,                     % ?X, ?List
   39          memberchk/2,                  % ?X, ?List
   40          append/2,                     % +ListOfLists, -List
   41          append/3,                     % ?A, ?B, ?AB
   42          prefix/2,                     % ?Part, ?Whole
   43          select/3,                     % ?X, ?List, ?Rest
   44          selectchk/3,                  % ?X, ?List, ?Rest
   45          select/4,                     % ?X, ?XList, ?Y, ?YList
   46          selectchk/4,                  % ?X, ?XList, ?Y, ?YList
   47          nextto/3,                     % ?X, ?Y, ?List
   48          delete/3,                     % ?List, ?X, ?Rest
   49          nth0/3,                       % ?N, ?List, ?Elem
   50          nth1/3,                       % ?N, ?List, ?Elem
   51          nth0/4,                       % ?N, ?List, ?Elem, ?Rest
   52          nth1/4,                       % ?N, ?List, ?Elem, ?Rest
   53          last/2,                       % +List, -Element
   54          proper_length/2,              % @List, -Length
   55          same_length/2,                % ?List1, ?List2
   56          reverse/2,                    % +List, -Reversed
   57          permutation/2,                % ?List, ?Permutation
   58          flatten/2,                    % +Nested, -Flat
   59          clumped/2,                    % +Items,-Pairs
   60          subseq/3,                     % ?List, ?SubList, ?Complement
   61
   62                                        % Ordered operations
   63          max_member/2,                 % -Max, +List
   64          min_member/2,                 % -Min, +List
   65          max_member/3,                 % :Pred, -Max, +List
   66          min_member/3,                 % :Pred, -Min, +List
   67
   68                                        % Lists of numbers
   69          sum_list/2,                   % +List, -Sum
   70          max_list/2,                   % +List, -Max
   71          min_list/2,                   % +List, -Min
   72          numlist/3,                    % +Low, +High, -List
   73
   74                                        % set manipulation
   75          is_set/1,                     % +List
   76          list_to_set/2,                % +List, -Set
   77          intersection/3,               % +List1, +List2, -Intersection
   78          union/3,                      % +List1, +List2, -Union
   79          subset/2,                     % +SubSet, +Set
   80          subtract/3                    % +Set, +Delete, -Remaining
   81        ]).   82:- autoload(library(error), [must_be/2, instantiation_error/1]).   83:- autoload(library(pairs), [pairs_keys/2]).   84
   85:- meta_predicate
   86    max_member(2, -, +),
   87    min_member(2, -, +).   88
   89:- set_prolog_flag(generate_debug_info, false).   90
   91/** <module> List Manipulation
   92
   93This library provides  commonly  accepted   basic  predicates  for  list
   94manipulation in the Prolog community. Some additional list manipulations
   95are built-in. See e.g., memberchk/2, length/2.
   96
   97The implementation of this library  is   copied  from many places. These
   98include: "The Craft of Prolog", the   DEC-10  Prolog library (LISTRO.PL)
   99and the YAP lists library. Some   predicates  are reimplemented based on
  100their specification by Quintus and SICStus.
  101
  102@compat Virtually every Prolog system has library(lists), but the set
  103        of provided predicates is diverse.  There is a fair agreement
  104        on the semantics of most of these predicates, although error
  105        handling may vary.
  106*/
  107
  108%!  member(?Elem, ?List)
  109%
  110%   True if Elem is a  member   of  List.  The SWI-Prolog definition
  111%   differs from the classical one.  Our definition avoids unpacking
  112%   each list element twice and  provides   determinism  on the last
  113%   element.  E.g. this is deterministic:
  114%
  115%       ==
  116%           member(X, [One]).
  117%       ==
  118%
  119%   @author Gertjan van Noord
  120
  121member(El, [H|T]) :-
  122    member_(T, El, H).
  123
  124member_(_, El, El).
  125member_([H|T], El, _) :-
  126    member_(T, El, H).
  127
  128%!  append(?List1, ?List2, ?List1AndList2)
  129%
  130%   List1AndList2 is the concatenation of List1 and List2
  131
  132append([], L, L).
  133append([H|T], L, [H|R]) :-
  134    append(T, L, R).
  135
  136%!  append(+ListOfLists, ?List)
  137%
  138%   Concatenate a list of lists.  Is  true   if  ListOfLists  is a list of
  139%   lists, and List is the concatenation of these lists.
  140%
  141%   @param  ListOfLists must be a list of _possibly_ partial lists
  142
  143append(ListOfLists, List) :-
  144    must_be(list, ListOfLists),
  145    append_(ListOfLists, List).
  146
  147append_([], []).
  148append_([L|Ls], As) :-
  149    append(L, Ws, As),
  150    append_(Ls, Ws).
  151
  152
  153%!  prefix(?Part, ?Whole)
  154%
  155%   True iff Part is a leading substring of Whole.  This is the same
  156%   as append(Part, _, Whole).
  157
  158prefix([], _).
  159prefix([E|T0], [E|T]) :-
  160    prefix(T0, T).
  161
  162
  163%!  select(?Elem, ?List1, ?List2)
  164%
  165%   Is true when List1,  with  Elem   removed,  results  in  List2. This
  166%   implementation is determinsitic if the  last   element  of List1 has
  167%   been selected.
  168
  169select(X, [Head|Tail], Rest) :-
  170    select3_(Tail, Head, X, Rest).
  171
  172select3_(Tail, Head, Head, Tail).
  173select3_([Head2|Tail], Head, X, [Head|Rest]) :-
  174    select3_(Tail, Head2, X, Rest).
  175
  176
  177%!  selectchk(+Elem, +List, -Rest) is semidet.
  178%
  179%   Semi-deterministic removal of first element in List that unifies
  180%   with Elem.
  181
  182selectchk(Elem, List, Rest) :-
  183    select(Elem, List, Rest0),
  184    !,
  185    Rest = Rest0.
  186
  187
  188%!  select(?X, ?XList, ?Y, ?YList) is nondet.
  189%
  190%   Select from two lists  at  the  same   position.  True  if  XList is
  191%   unifiable with YList apart a  single   element  at the same position
  192%   that is unified with X in XList and   with Y in YList. A typical use
  193%   for this predicate is to  _replace_  an   element,  as  shown in the
  194%   example  below.  All  possible  substitutions    are   performed  on
  195%   backtracking.
  196%
  197%     ==
  198%     ?- select(b, [a,b,c,b], 2, X).
  199%     X = [a, 2, c, b] ;
  200%     X = [a, b, c, 2] ;
  201%     false.
  202%     ==
  203%
  204%   @see selectchk/4 provides a semidet version.
  205
  206select(X, XList, Y, YList) :-
  207    select4_(XList, X, Y, YList).
  208
  209select4_([X|List], X, Y, [Y|List]).
  210select4_([X0|XList], X, Y, [X0|YList]) :-
  211    select4_(XList, X, Y, YList).
  212
  213%!  selectchk(?X, ?XList, ?Y, ?YList) is semidet.
  214%
  215%   Semi-deterministic version of select/4.
  216
  217selectchk(X, XList, Y, YList) :-
  218    select(X, XList, Y, YList),
  219    !.
  220
  221%!  nextto(?X, ?Y, ?List)
  222%
  223%   True if Y directly follows X in List.
  224
  225nextto(X, Y, [X,Y|_]).
  226nextto(X, Y, [_|Zs]) :-
  227    nextto(X, Y, Zs).
  228
  229%!  delete(+List1, @Elem, -List2) is det.
  230%
  231%   Delete matching elements from a list. True  when List2 is a list
  232%   with all elements from List1 except   for  those that unify with
  233%   Elem. Matching Elem with elements of List1  is uses =|\+ Elem \=
  234%   H|=, which implies that Elem is not changed.
  235%
  236%   @deprecated There are too many ways in which one might want to
  237%               delete elements from a list to justify the name.
  238%               Think of matching (= vs. ==), delete first/all,
  239%               be deterministic or not.
  240%   @see select/3, subtract/3.
  241
  242delete([], _, []).
  243delete([Elem|Tail], Del, Result) :-
  244    (   \+ Elem \= Del
  245    ->  delete(Tail, Del, Result)
  246    ;   Result = [Elem|Rest],
  247        delete(Tail, Del, Rest)
  248    ).
  249
  250
  251/*  nth0/3, nth1/3 are improved versions from
  252    Martin Jansche <martin@pc03.idf.uni-heidelberg.de>
  253*/
  254
  255%!  nth0(?Index, ?List, ?Elem)
  256%
  257%   True when Elem is the Index'th  element of List. Counting starts
  258%   at 0.
  259%
  260%   @error  type_error(integer, Index) if Index is not an integer or
  261%           unbound.
  262%   @see nth1/3.
  263
  264nth0(Index, List, Elem) :-
  265    (   integer(Index)
  266    ->  '$seek_list'(Index, List, RestIndex, RestList),
  267        nth0_det(RestIndex, RestList, Elem) % take nth det
  268    ;   var(Index)
  269    ->  List = [H|T],
  270        nth_gen(T, Elem, H, 0, Index)       % match
  271    ;   must_be(integer, Index)
  272    ).
  273
  274nth0_det(0, [Elem|_], Elem) :- !.
  275nth0_det(N, [_|Tail], Elem) :-
  276    M is N - 1,
  277    M >= 0,
  278    nth0_det(M, Tail, Elem).
  279
  280nth_gen(_, Elem, Elem, Base, Base).
  281nth_gen([H|Tail], Elem, _, N, Base) :-
  282    M is N + 1,
  283    nth_gen(Tail, Elem, H, M, Base).
  284
  285
  286%!  nth1(?Index, ?List, ?Elem)
  287%
  288%   Is true when Elem is  the   Index'th  element  of List. Counting
  289%   starts at 1.
  290%
  291%   @see nth0/3.
  292
  293nth1(Index, List, Elem) :-
  294    (   integer(Index)
  295    ->  Index0 is Index - 1,
  296        '$seek_list'(Index0, List, RestIndex, RestList),
  297        nth0_det(RestIndex, RestList, Elem) % take nth det
  298    ;   var(Index)
  299    ->  List = [H|T],
  300        nth_gen(T, Elem, H, 1, Index)       % match
  301    ;   must_be(integer, Index)
  302    ).
  303
  304%!  nth0(?N, ?List, ?Elem, ?Rest) is det.
  305%
  306%   Select/insert element at index.  True  when   Elem  is  the N'th
  307%   (0-based) element of List and Rest is   the  remainder (as in by
  308%   select/3) of List.  For example:
  309%
  310%     ==
  311%     ?- nth0(I, [a,b,c], E, R).
  312%     I = 0, E = a, R = [b, c] ;
  313%     I = 1, E = b, R = [a, c] ;
  314%     I = 2, E = c, R = [a, b] ;
  315%     false.
  316%     ==
  317%
  318%     ==
  319%     ?- nth0(1, L, a1, [a,b]).
  320%     L = [a, a1, b].
  321%     ==
  322
  323nth0(V, In, Element, Rest) :-
  324    var(V),
  325    !,
  326    generate_nth(0, V, In, Element, Rest).
  327nth0(V, In, Element, Rest) :-
  328    must_be(nonneg, V),
  329    find_nth0(V, In, Element, Rest).
  330
  331%!  nth1(?N, ?List, ?Elem, ?Rest) is det.
  332%
  333%   As nth0/4, but counting starts at 1.
  334
  335nth1(V, In, Element, Rest) :-
  336    var(V),
  337    !,
  338    generate_nth(1, V, In, Element, Rest).
  339nth1(V, In, Element, Rest) :-
  340    must_be(positive_integer, V),
  341    succ(V0, V),
  342    find_nth0(V0, In, Element, Rest).
  343
  344generate_nth(I, I, [Head|Rest], Head, Rest).
  345generate_nth(I, IN, [H|List], El, [H|Rest]) :-
  346    I1 is I+1,
  347    generate_nth(I1, IN, List, El, Rest).
  348
  349find_nth0(0, [Head|Rest], Head, Rest) :- !.
  350find_nth0(N, [Head|Rest0], Elem, [Head|Rest]) :-
  351    M is N-1,
  352    find_nth0(M, Rest0, Elem, Rest).
  353
  354
  355%!  last(?List, ?Last)
  356%
  357%   Succeeds when Last  is  the  last   element  of  List.  This
  358%   predicate is =semidet= if List is a  list and =multi= if List is
  359%   a partial list.
  360%
  361%   @compat There is no de-facto standard for the argument order of
  362%           last/2.  Be careful when porting code or use
  363%           append(_, [Last], List) as a portable alternative.
  364
  365last([X|Xs], Last) :-
  366    last_(Xs, X, Last).
  367
  368last_([], Last, Last).
  369last_([X|Xs], _, Last) :-
  370    last_(Xs, X, Last).
  371
  372
  373%!  proper_length(@List, -Length) is semidet.
  374%
  375%   True when Length is the number of   elements  in the proper list
  376%   List.  This is equivalent to
  377%
  378%     ==
  379%     proper_length(List, Length) :-
  380%           is_list(List),
  381%           length(List, Length).
  382%     ==
  383
  384proper_length(List, Length) :-
  385    '$skip_list'(Length0, List, Tail),
  386    Tail == [],
  387    Length = Length0.
  388
  389
  390%!  same_length(?List1, ?List2)
  391%
  392%   Is true when List1 and List2 are   lists with the same number of
  393%   elements. The predicate is deterministic if  at least one of the
  394%   arguments is a proper list.  It   is  non-deterministic  if both
  395%   arguments are partial lists.
  396%
  397%   @see length/2
  398
  399same_length([], []).
  400same_length([_|T1], [_|T2]) :-
  401    same_length(T1, T2).
  402
  403
  404%!  reverse(?List1, ?List2)
  405%
  406%   Is true when the elements of List2  are in reverse order compared to
  407%   List1. This predicate is deterministic if   either  list is a proper
  408%   list. If both  lists  are   _partial  lists_  backtracking generates
  409%   increasingly long lists.
  410
  411reverse(Xs, Ys) :-
  412    reverse(Xs, Ys, [], Ys).
  413
  414reverse([], [], Ys, Ys).
  415reverse([X|Xs], [_|Bound], Rs, Ys) :-
  416    reverse(Xs, Bound, [X|Rs], Ys).
  417
  418
  419%!  permutation(?Xs, ?Ys) is nondet.
  420%
  421%   True when Xs is a permutation of Ys. This can solve for Ys given
  422%   Xs or Xs given Ys, or  even   enumerate  Xs and Ys together. The
  423%   predicate  permutation/2  is  primarily   intended  to  generate
  424%   permutations. Note that a list of  length N has N! permutations,
  425%   and  unbounded  permutation  generation   becomes  prohibitively
  426%   expensive, even for rather short lists (10! = 3,628,800).
  427%
  428%   If both Xs and Ys are provided  and both lists have equal length
  429%   the order is |Xs|^2. Simply testing  whether Xs is a permutation
  430%   of Ys can be  achieved  in   order  log(|Xs|)  using  msort/2 as
  431%   illustrated below with the =semidet= predicate is_permutation/2:
  432%
  433%     ==
  434%     is_permutation(Xs, Ys) :-
  435%       msort(Xs, Sorted),
  436%       msort(Ys, Sorted).
  437%     ==
  438%
  439%   The example below illustrates that Xs   and Ys being proper lists
  440%   is not a sufficient condition to use the above replacement.
  441%
  442%     ==
  443%     ?- permutation([1,2], [X,Y]).
  444%     X = 1, Y = 2 ;
  445%     X = 2, Y = 1 ;
  446%     false.
  447%     ==
  448%
  449%   @error  type_error(list, Arg) if either argument is not a proper
  450%           or partial list.
  451
  452permutation(Xs, Ys) :-
  453    '$skip_list'(Xlen, Xs, XTail),
  454    '$skip_list'(Ylen, Ys, YTail),
  455    (   XTail == [], YTail == []            % both proper lists
  456    ->  Xlen == Ylen
  457    ;   var(XTail), YTail == []             % partial, proper
  458    ->  length(Xs, Ylen)
  459    ;   XTail == [], var(YTail)             % proper, partial
  460    ->  length(Ys, Xlen)
  461    ;   var(XTail), var(YTail)              % partial, partial
  462    ->  length(Xs, Len),
  463        length(Ys, Len)
  464    ;   must_be(list, Xs),                  % either is not a list
  465        must_be(list, Ys)
  466    ),
  467    perm(Xs, Ys).
  468
  469perm([], []).
  470perm(List, [First|Perm]) :-
  471    select(First, List, Rest),
  472    perm(Rest, Perm).
  473
  474%!  flatten(+NestedList, -FlatList) is det.
  475%
  476%   Is true if FlatList is a  non-nested version of NestedList. Note
  477%   that empty lists are removed. In   standard Prolog, this implies
  478%   that the atom '[]' is removed  too.   In  SWI7, `[]` is distinct
  479%   from '[]'.
  480%
  481%   Ending up needing flatten/2 often   indicates, like append/3 for
  482%   appending two lists, a bad design. Efficient code that generates
  483%   lists from generated small  lists   must  use  difference lists,
  484%   often possible through grammar rules for optimal readability.
  485%
  486%   @see append/2
  487
  488flatten(List, FlatList) :-
  489    flatten(List, [], FlatList0),
  490    !,
  491    FlatList = FlatList0.
  492
  493flatten(Var, Tl, [Var|Tl]) :-
  494    var(Var),
  495    !.
  496flatten([], Tl, Tl) :- !.
  497flatten([Hd|Tl], Tail, List) :-
  498    !,
  499    flatten(Hd, FlatHeadTail, List),
  500    flatten(Tl, Tail, FlatHeadTail).
  501flatten(NonList, Tl, [NonList|Tl]).
  502
  503
  504		 /*******************************
  505		 *            CLUMPS		*
  506		 *******************************/
  507
  508%!  clumped(+Items, -Pairs)
  509%
  510%   Pairs is a list  of  `Item-Count`   pairs  that  represents the _run
  511%   length encoding_ of Items.  For example:
  512%
  513%   ```
  514%   ?- clumped([a,a,b,a,a,a,a,c,c,c], R).
  515%   R = [a-2, b-1, a-4, c-3].
  516%   ```
  517%
  518%   @compat SICStus
  519
  520clumped(Items, Counts) :-
  521    clump(Items, Counts).
  522
  523clump([], []).
  524clump([H|T0], [H-C|T]) :-
  525    ccount(T0, H, T1, 1, C),
  526    clump(T1, T).
  527
  528ccount([H|T0], E, T, C0, C) :-
  529    E == H,
  530    !,
  531    C1 is C0+1,
  532    ccount(T0, E, T, C1, C).
  533ccount(List, _, List, C, C).
  534
  535
  536%!  subseq(+List, -SubList, -Complement) is nondet.
  537%!  subseq(-List, +SubList, +Complement) is nondet.
  538%
  539%   Is true when SubList contains a subset   of  the elements of List in
  540%   the same order and Complement contains all   elements of List not in
  541%   SubList, also in the order they appear in List.
  542%
  543%   @compat SICStus.  The SWI-Prolog version raises an error for less
  544%   instantiated modes as these do not terminate.
  545
  546subseq(L, S, C), is_list(L) => subseq_(L, S, C).
  547subseq(L, S, C), is_list(S), is_list(C) => subseq_(L, S, C).
  548subseq(L, S, C) =>
  549    must_be(list_or_partial_list, L),
  550    must_be(list_or_partial_list, S),
  551    must_be(list_or_partial_list, C),
  552    instantiation_error(L).
  553
  554subseq_([], [], []).
  555subseq_([H|T0], T1, [H|C]) :-
  556    subseq_(T0, T1, C).
  557subseq_([H|T0], [H|T1], C) :-
  558    subseq_(T0, T1, C).
  559
  560
  561                 /*******************************
  562                 *       ORDER OPERATIONS       *
  563                 *******************************/
  564
  565%!  max_member(-Max, +List) is semidet.
  566%
  567%   True when Max is the largest  member   in  the standard order of
  568%   terms.  Fails if List is empty.
  569%
  570%   @see compare/3
  571%   @see max_list/2 for the maximum of a list of numbers.
  572
  573max_member(Max, [H|T]) =>
  574    max_member_(T, H, Max).
  575max_member(_, []) =>
  576    fail.
  577
  578max_member_([], Max0, Max) =>
  579    Max = Max0.
  580max_member_([H|T], Max0, Max) =>
  581    (   H @=< Max0
  582    ->  max_member_(T, Max0, Max)
  583    ;   max_member_(T, H, Max)
  584    ).
  585
  586
  587%!  min_member(-Min, +List) is semidet.
  588%
  589%   True when Min is the smallest member   in  the standard order of
  590%   terms. Fails if List is empty.
  591%
  592%   @see compare/3
  593%   @see min_list/2 for the minimum of a list of numbers.
  594
  595min_member(Min, [H|T]) =>
  596    min_member_(T, H, Min).
  597min_member(_, []) =>
  598    fail.
  599
  600min_member_([], Min0, Min) =>
  601    Min = Min0.
  602min_member_([H|T], Min0, Min) =>
  603    (   H @>= Min0
  604    ->  min_member_(T, Min0, Min)
  605    ;   min_member_(T, H, Min)
  606    ).
  607
  608
  609%!  max_member(:Pred, -Max, +List) is semidet.
  610%
  611%   True when Max is the largest member according to Pred, which must be
  612%   a 2-argument callable that behaves like   (@=<)/2.  Fails if List is
  613%   empty.  The following call is equivalent to max_member/2:
  614%
  615%       ?- max_member(@=<, X, [6,1,8,4]).
  616%       X = 8.
  617%
  618%   @see max_list/2 for the maximum of a list of numbers.
  619
  620max_member(Pred, Max, [H|T]) =>
  621    max_member_(T, Pred, H, Max).
  622max_member(_, _, []) =>
  623    fail.
  624
  625max_member_([], _, Max0, Max) =>
  626    Max = Max0.
  627max_member_([H|T], Pred, Max0, Max) =>
  628    (   call(Pred, H, Max0)
  629    ->  max_member_(T, Pred, Max0, Max)
  630    ;   max_member_(T, Pred, H, Max)
  631    ).
  632
  633
  634%!  min_member(:Pred, -Min, +List) is semidet.
  635%
  636%   True when Min is the smallest member   according to Pred, which must
  637%   be a 2-argument callable that behaves like (@=<)/2. Fails if List is
  638%   empty. The following call is equivalent to max_member/2:
  639%
  640%       ?- min_member(@=<, X, [6,1,8,4]).
  641%       X = 1.
  642%
  643%   @see min_list/2 for the minimum of a list of numbers.
  644
  645min_member(Pred, Min, [H|T]) =>
  646    min_member_(T, Pred, H, Min).
  647min_member(_, _, []) =>
  648    fail.
  649
  650min_member_([], _, Min0, Min) =>
  651    Min = Min0.
  652min_member_([H|T], Pred, Min0, Min) =>
  653    (   call(Pred, Min0, H)
  654    ->  min_member_(T, Pred, Min0, Min)
  655    ;   min_member_(T, Pred, H, Min)
  656    ).
  657
  658
  659                 /*******************************
  660                 *       LISTS OF NUMBERS       *
  661                 *******************************/
  662
  663%!  sum_list(+List, -Sum) is det.
  664%
  665%   Sum is the result of adding all numbers in List.
  666
  667sum_list(Xs, Sum) :-
  668    sum_list(Xs, 0, Sum).
  669
  670sum_list([], Sum0, Sum) =>
  671    Sum = Sum0.
  672sum_list([X|Xs], Sum0, Sum) =>
  673    Sum1 is Sum0 + X,
  674    sum_list(Xs, Sum1, Sum).
  675
  676%!  max_list(+List:list(number), -Max:number) is semidet.
  677%
  678%   True if Max is the largest number in List.  Fails if List is
  679%   empty.
  680%
  681%   @see max_member/2.
  682
  683max_list([H|T], Max) =>
  684    max_list(T, H, Max).
  685max_list([], _) => fail.
  686
  687max_list([], Max0, Max) =>
  688    Max = Max0.
  689max_list([H|T], Max0, Max) =>
  690    Max1 is max(H, Max0),
  691    max_list(T, Max1, Max).
  692
  693
  694%!  min_list(+List:list(number), -Min:number) is semidet.
  695%
  696%   True if Min is the smallest  number   in  List. Fails if List is
  697%   empty.
  698%
  699%   @see min_member/2.
  700
  701min_list([H|T], Min) =>
  702    min_list(T, H, Min).
  703min_list([], _) => fail.
  704
  705min_list([], Min0, Min) =>
  706    Min = Min0.
  707min_list([H|T], Min0, Min) =>
  708    Min1 is min(H, Min0),
  709    min_list(T, Min1, Min).
  710
  711
  712%!  numlist(+Low, +High, -List) is semidet.
  713%
  714%   List is a list [Low, Low+1, ... High].  Fails if High < Low.
  715%
  716%   @error type_error(integer, Low)
  717%   @error type_error(integer, High)
  718
  719numlist(L, U, Ns) :-
  720    must_be(integer, L),
  721    must_be(integer, U),
  722    L =< U,
  723    numlist_(L, U, Ns).
  724
  725numlist_(U, U, List) :-
  726    !,
  727    List = [U].
  728numlist_(L, U, [L|Ns]) :-
  729    L2 is L+1,
  730    numlist_(L2, U, Ns).
  731
  732
  733                /********************************
  734                *       SET MANIPULATION        *
  735                *********************************/
  736
  737%!  is_set(@Set) is semidet.
  738%
  739%   True if Set is a proper  list without duplicates. Equivalence is
  740%   based on ==/2. The  implementation   uses  sort/2, which implies
  741%   that the complexity is N*log(N) and   the  predicate may cause a
  742%   resource-error. There are no other error conditions.
  743
  744is_set(Set) :-
  745    '$skip_list'(Len, Set, Tail),
  746    Tail == [],                             % Proper list
  747    sort(Set, Sorted),
  748    length(Sorted, Len).
  749
  750
  751%!  list_to_set(+List, ?Set) is det.
  752%
  753%   True when Set has the same elements   as List in the same order.
  754%   The left-most copy of duplicate elements   is retained. List may
  755%   contain  variables.  Elements  _E1_  and   _E2_  are  considered
  756%   duplicates iff _E1_  ==  _E2_  holds.   The  complexity  of  the
  757%   implementation is N*log(N).
  758%
  759%   @see    sort/2 can be used to create an ordered set.  Many
  760%           set operations on ordered sets are order N rather than
  761%           order N**2.  The list_to_set/2 predicate is more
  762%           expensive than sort/2 because it involves, two sorts
  763%           and a linear scan.
  764%   @compat Up to version 6.3.11, list_to_set/2 had complexity
  765%           N**2 and equality was tested using =/2.
  766%   @error  List is type-checked.
  767
  768list_to_set(List, Set) :-
  769    must_be(list, List),
  770    number_list(List, 1, Numbered),
  771    sort(1, @=<, Numbered, ONum),
  772    remove_dup_keys(ONum, NumSet),
  773    sort(2, @=<, NumSet, ONumSet),
  774    pairs_keys(ONumSet, Set).
  775
  776number_list([], _, []).
  777number_list([H|T0], N, [H-N|T]) :-
  778    N1 is N+1,
  779    number_list(T0, N1, T).
  780
  781remove_dup_keys([], []).
  782remove_dup_keys([H|T0], [H|T]) :-
  783    H = V-_,
  784    remove_same_key(T0, V, T1),
  785    remove_dup_keys(T1, T).
  786
  787remove_same_key([V1-_|T0], V, T) :-
  788    V1 == V,
  789    !,
  790    remove_same_key(T0, V, T).
  791remove_same_key(L, _, L).
  792
  793
  794%!  intersection(+Set1, +Set2, -Set3) is det.
  795%
  796%   True if Set3 unifies with the  intersection   of  Set1 and Set2. The
  797%   complexity of this predicate is |Set1|*|Set2|. A _set_ is defined to
  798%   be an unordered list  without   duplicates.  Elements are considered
  799%   duplicates if they can be unified.
  800%
  801%   @see ord_intersection/3.
  802
  803intersection([], _, Set) =>
  804    Set = [].
  805intersection([X|T], L, Intersect) =>
  806    (   memberchk(X, L)
  807    ->  Intersect = [X|R],
  808        intersection(T, L, R)
  809    ;   intersection(T, L, Intersect)
  810    ).
  811
  812%!  union(+Set1, +Set2, -Set3) is det.
  813%
  814%   True if Set3 unifies with the union of  the lists Set1 and Set2. The
  815%   complexity of this predicate is |Set1|*|Set2|. A _set_ is defined to
  816%   be an unordered list  without   duplicates.  Elements are considered
  817%   duplicates if they can be unified.
  818%
  819%   @see ord_union/3
  820
  821union([], L0, L) =>
  822    L = L0.
  823union([H|T], L, Union) =>
  824    (   memberchk(H, L)
  825    ->  union(T, L, Union)
  826    ;   Union = [H|R],
  827        union(T, L, R)
  828    ).
  829
  830%!  subset(+SubSet, +Set) is semidet.
  831%
  832%   True if all elements of SubSet  belong   to  Set as well. Membership
  833%   test is based on memberchk/2. The   complexity  is |SubSet|*|Set|. A
  834%   _set_ is defined  to  be  an   unordered  list  without  duplicates.
  835%   Elements are considered duplicates if they can be unified.
  836%
  837%   @see ord_subset/2.
  838
  839subset([], _) => true.
  840subset([E|R], Set) =>
  841    memberchk(E, Set),
  842    subset(R, Set).
  843
  844
  845%!  subtract(+Set, +Delete, -Result) is det.
  846%
  847%   Delete all elements  in  Delete  from   Set.  Deletion  is  based on
  848%   unification using memberchk/2. The complexity   is |Delete|*|Set|. A
  849%   _set_ is defined  to  be  an   unordered  list  without  duplicates.
  850%   Elements are considered duplicates if they can be unified.
  851%
  852%   @see ord_subtract/3.
  853
  854subtract([], _, R) =>
  855    R = [].
  856subtract([E|T], D, R) =>
  857    (   memberchk(E, D)
  858    ->  subtract(T, D, R)
  859    ;   R = [E|R1],
  860        subtract(T, D, R1)
  861    )