View source with raw 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 det.
 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).