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).

 member(?Elem, ?List)

True if Elem is a member of List. The SWI-Prolog definition differs from the classical one. Our definition avoids unpacking each list element twice and provides determinism on the last element. E.g. this is deterministic:

    member(X, [One]).

author

- Gertjan van Noord

  121member(El, [H|T]) :-
  122    member_(T, El, H).
  123
  124member_(_, El, El).
  125member_([H|T], El, _) :-
  126    member_(T, El, H).

 append(?List1, ?List2, ?List1AndList2)

List1AndList2 is the concatenation of List1 and List2

  132append([], L, L).
  133append([H|T], L, [H|R]) :-
  134    append(T, L, R).

 append(+ListOfLists, ?List)

Concatenate a list of lists. Is true if ListOfLists is a list of lists, and List is the concatenation of these lists.

Arguments:

ListOfLists

- must be a list of possibly partial lists

  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).

 prefix(?Part, ?Whole)

True iff Part is a leading substring of Whole. This is the same as append(Part, _, Whole).

  158prefix([], _).
  159prefix([E|T0], [E|T]) :-
  160    prefix(T0, T).

 select(?Elem, ?List1, ?List2)

Is true when List1, with Elem removed, results in List2. This implementation is determinsitic if the last element of List1 has been selected.

  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).

 selectchk(+Elem, +List, -Rest) is semidet

Semi-deterministic removal of first element in List that unifies with Elem.

  182selectchk(Elem, List, Rest) :-
  183    select(Elem, List, Rest0),
  184    !,
  185    Rest = Rest0.

 select(?X, ?XList, ?Y, ?YList) is nondet

Select from two lists at the same position. True if XList is unifiable with YList apart a single element at the same position that is unified with X in XList and with Y in YList. A typical use for this predicate is to replace an element, as shown in the example below. All possible substitutions are performed on backtracking.

?- select(b, [a,b,c,b], 2, X).
X = [a, 2, c, b] ;
X = [a, b, c, 2] ;
false.

See also

- selectchk/4 provides a semidet version.

  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).

 selectchk(?X, ?XList, ?Y, ?YList) is semidet

Semi-deterministic version of select/4.

  217selectchk(X, XList, Y, YList) :-
  218    select(X, XList, Y, YList),
  219    !.

 nextto(?X, ?Y, ?List)

True if Y directly follows X in List.

  225nextto(X, Y, [X,Y|_]).
  226nextto(X, Y, [_|Zs]) :-
  227    nextto(X, Y, Zs).

 delete(+List1, @Elem, -List2) is det

Delete matching elements from a list. True when List2 is a list with all elements from List1 except for those that unify with Elem. Matching Elem with elements of List1 is uses \+ Elem \= H, which implies that Elem is not changed.

See also

- select/3, subtract/3.

deprecated

- There are too many ways in which one might want to delete elements from a list to justify the name. Think of matching (= vs. ==), delete first/all, be deterministic or not.

  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*/

 nth0(?Index, ?List, ?Elem)

True when Elem is the Index'th element of List. Counting starts at 0.

Errors

- type_error(integer, Index) if Index is not an integer or unbound.

See also

- nth1/3.

  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).

 nth1(?Index, ?List, ?Elem)

Is true when Elem is the Index'th element of List. Counting starts at 1.

See also

- nth0/3.

  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    ).

 nth0(?N, ?List, ?Elem, ?Rest) is det

Select/insert element at index. True when Elem is the N'th (0-based) element of List and Rest is the remainder (as in by select/3) of List. For example:

?- nth0(I, [a,b,c], E, R).
I = 0, E = a, R = [b, c] ;
I = 1, E = b, R = [a, c] ;
I = 2, E = c, R = [a, b] ;
false.

?- nth0(1, L, a1, [a,b]).
L = [a, a1, b].

  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).

 nth1(?N, ?List, ?Elem, ?Rest) is det

As nth0/4, but counting starts at 1.

  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).

 last(?List, ?Last)

Succeeds when Last is the last element of List. This predicate is semidet if List is a list and multi if List is a partial list.

Compatibility

- There is no de-facto standard for the argument order of last/2. Be careful when porting code or use append(_, [Last], List) as a portable alternative.

  365last([X|Xs], Last) :-
  366    last_(Xs, X, Last).
  367
  368last_([], Last, Last).
  369last_([X|Xs], _, Last) :-
  370    last_(Xs, X, Last).

 proper_length(@List, -Length) is semidet

True when Length is the number of elements in the proper list List. This is equivalent to

proper_length(List, Length) :-
      is_list(List),
      length(List, Length).

  384proper_length(List, Length) :-
  385    '$skip_list'(Length0, List, Tail),
  386    Tail == [],
  387    Length = Length0.

 same_length(?List1, ?List2)

Is true when List1 and List2 are lists with the same number of elements. The predicate is deterministic if at least one of the arguments is a proper list. It is non-deterministic if both arguments are partial lists.

See also

- length/2

  399same_length([], []).
  400same_length([_|T1], [_|T2]) :-
  401    same_length(T1, T2).

 reverse(?List1, ?List2)

Is true when the elements of List2 are in reverse order compared to List1. This predicate is deterministic if either list is a proper list. If both lists are partial lists backtracking generates increasingly long lists.

  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).

 permutation(?Xs, ?Ys) is nondet

True when Xs is a permutation of Ys. This can solve for Ys given Xs or Xs given Ys, or even enumerate Xs and Ys together. The predicate permutation/2 is primarily intended to generate permutations. Note that a list of length N has N! permutations, and unbounded permutation generation becomes prohibitively expensive, even for rather short lists (10! = 3,628,800).

If both Xs and Ys are provided and both lists have equal length the order is |Xs|^2. Simply testing whether Xs is a permutation of Ys can be achieved in order log(|Xs|) using msort/2 as illustrated below with the semidet predicate is_permutation/2:

is_permutation(Xs, Ys) :-
  msort(Xs, Sorted),
  msort(Ys, Sorted).

The example below illustrates that Xs and Ys being proper lists is not a sufficient condition to use the above replacement.

?- permutation([1,2], [X,Y]).
X = 1, Y = 2 ;
X = 2, Y = 1 ;
false.

Errors

- type_error(list, Arg) if either argument is not a proper or partial list.

  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).

 flatten(+NestedList, -FlatList) is det

Is true if FlatList is a non-nested version of NestedList. Note that empty lists are removed. In standard Prolog, this implies that the atom '[]' is removed too. In SWI7, [] is distinct from '[]'.

Ending up needing flatten/2 often indicates, like append/3 for appending two lists, a bad design. Efficient code that generates lists from generated small lists must use difference lists, often possible through grammar rules for optimal readability.

See also

- append/2

  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		 *******************************/

 clumped(+Items, -Pairs)

Pairs is a list of Item-Count pairs that represents the run length encoding of Items. For example:

?- clumped([a,a,b,a,a,a,a,c,c,c], R).
R = [a-2, b-1, a-4, c-3].

Compatibility

- SICStus

  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).

 subseq(+List, -SubList, -Complement) is nondet

subseq(-List, +SubList, +Complement) is nondet

Is true when SubList contains a subset of the elements of List in the same order and Complement contains all elements of List not in SubList, also in the order they appear in List.

Compatibility

- SICStus. The SWI-Prolog version raises an error for less instantiated modes as these do not terminate.

  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                 *******************************/

 max_member(-Max, +List) is semidet

True when Max is the largest member in the standard order of terms. Fails if List is empty.

See also

- compare/3

- max_list/2 for the maximum of a list of numbers.

  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    ).

 min_member(-Min, +List) is semidet

True when Min is the smallest member in the standard order of terms. Fails if List is empty.

See also

- compare/3

- min_list/2 for the minimum of a list of numbers.

  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    ).

 max_member(:Pred, -Max, +List) is semidet

True when Max is the largest member according to Pred, which must be a 2-argument callable that behaves like (@=<)/2. Fails if List is empty. The following call is equivalent to max_member/2:

?- max_member(@=<, X, [6,1,8,4]).
X = 8.

See also

- max_list/2 for the maximum of a list of numbers.

  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    ).

 min_member(:Pred, -Min, +List) is semidet

True when Min is the smallest member according to Pred, which must be a 2-argument callable that behaves like (@=<)/2. Fails if List is empty. The following call is equivalent to max_member/2:

?- min_member(@=<, X, [6,1,8,4]).
X = 1.

See also

- min_list/2 for the minimum of a list of numbers.

  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                 *******************************/

 sum_list(+List, -Sum) is det

Sum is the result of adding all numbers in List.

  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).

 max_list(+List:list(number), -Max:number) is semidet

True if Max is the largest number in List. Fails if List is empty.

See also

- max_member/2.

  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).

 min_list(+List:list(number), -Min:number) is semidet

True if Min is the smallest number in List. Fails if List is empty.

See also

- min_member/2.

  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).

 numlist(+Low, +High, -List) is semidet

List is a list [Low, Low+1, ... High]. Fails if High < Low.

Errors

- type_error(integer, Low)

- type_error(integer, High)

  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                *********************************/

 is_set(@Set) is semidet

True if Set is a proper list without duplicates. Equivalence is based on ==/2. The implementation uses sort/2, which implies that the complexity is N*log(N) and the predicate may cause a resource-error. There are no other error conditions.

  744is_set(Set) :-
  745    '$skip_list'(Len, Set, Tail),
  746    Tail == [],                             % Proper list
  747    sort(Set, Sorted),
  748    length(Sorted, Len).

 list_to_set(+List, ?Set) is det

True when Set has the same elements as List in the same order. The left-most copy of duplicate elements is retained. List may contain variables. Elements E1 and E2 are considered duplicates iff E1 == E2 holds. The complexity of the implementation is N*log(N).

Errors

- List is type-checked.

See also

- sort/2 can be used to create an ordered set. Many set operations on ordered sets are order N rather than order N**2. The list_to_set/2 predicate is more expensive than sort/2 because it involves, two sorts and a linear scan.

Compatibility

- Up to version 6.3.11, list_to_set/2 had complexity N**2 and equality was tested using =/2.

  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).

 intersection(+Set1, +Set2, -Set3) is det

True if Set3 unifies with the intersection of Set1 and Set2. The complexity of this predicate is |Set1|*|Set2|. A set is defined to be an unordered list without duplicates. Elements are considered duplicates if they can be unified.

See also

- ord_intersection/3.

  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    ).

 union(+Set1, +Set2, -Set3) is det

True if Set3 unifies with the union of the lists Set1 and Set2. The complexity of this predicate is |Set1|*|Set2|. A set is defined to be an unordered list without duplicates. Elements are considered duplicates if they can be unified.

See also

- ord_union/3

  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    ).

 subset(+SubSet, +Set) is semidet

True if all elements of SubSet belong to Set as well. Membership test is based on memberchk/2. The complexity is |SubSet|*|Set|. A set is defined to be an unordered list without duplicates. Elements are considered duplicates if they can be unified.

See also

- ord_subset/2.

  839subset([], _) => true.
  840subset([E|R], Set) =>
  841    memberchk(E, Set),
  842    subset(R, Set).

 subtract(+Set, +Delete, -Result) is det

Delete all elements in Delete from Set. Deletion is based on unification using memberchk/2. The complexity is |Delete|*|Set|. A set is defined to be an unordered list without duplicates. Elements are considered duplicates if they can be unified.

See also

- ord_subtract/3.

  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    )