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