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