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