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-2021, University of Amsterdam 7 VU University Amsterdam 8 SWI-Prolog Solutions b.v. 9 All rights reserved. 10 11 Redistribution and use in source and binary forms, with or without 12 modification, are permitted provided that the following conditions 13 are met: 14 15 1. Redistributions of source code must retain the above copyright 16 notice, this list of conditions and the following disclaimer. 17 18 2. Redistributions in binary form must reproduce the above copyright 19 notice, this list of conditions and the following disclaimer in 20 the documentation and/or other materials provided with the 21 distribution. 22 23 THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 24 "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 25 LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS 26 FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE 27 COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, 28 INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, 29 BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; 30 LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER 31 CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 32 LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN 33 ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE 34 POSSIBILITY OF SUCH DAMAGE. 35*/ 36 37:- module(lists, 38 [ member/2, % ?X, ?List 39 memberchk/2, % ?X, ?List 40 append/2, % +ListOfLists, -List 41 append/3, % ?A, ?B, ?AB 42 prefix/2, % ?Part, ?Whole 43 select/3, % ?X, ?List, ?Rest 44 selectchk/3, % ?X, ?List, ?Rest 45 select/4, % ?X, ?XList, ?Y, ?YList 46 selectchk/4, % ?X, ?XList, ?Y, ?YList 47 nextto/3, % ?X, ?Y, ?List 48 delete/3, % ?List, ?X, ?Rest 49 nth0/3, % ?N, ?List, ?Elem 50 nth1/3, % ?N, ?List, ?Elem 51 nth0/4, % ?N, ?List, ?Elem, ?Rest 52 nth1/4, % ?N, ?List, ?Elem, ?Rest 53 last/2, % +List, -Element 54 proper_length/2, % @List, -Length 55 same_length/2, % ?List1, ?List2 56 reverse/2, % +List, -Reversed 57 permutation/2, % ?List, ?Permutation 58 flatten/2, % +Nested, -Flat 59 clumped/2, % +Items,-Pairs 60 61 % Ordered operations 62 max_member/2, % -Max, +List 63 min_member/2, % -Min, +List 64 max_member/3, % :Pred, -Max, +List 65 min_member/3, % :Pred, -Min, +List 66 67 % Lists of numbers 68 sum_list/2, % +List, -Sum 69 max_list/2, % +List, -Max 70 min_list/2, % +List, -Min 71 numlist/3, % +Low, +High, -List 72 73 % set manipulation 74 is_set/1, % +List 75 list_to_set/2, % +List, -Set 76 intersection/3, % +List1, +List2, -Intersection 77 union/3, % +List1, +List2, -Union 78 subset/2, % +SubSet, +Set 79 subtract/3 % +Set, +Delete, -Remaining 80 ]). 81:- autoload(library(error),[must_be/2]). 82:- autoload(library(pairs),[pairs_keys/2]). 83 84:- meta_predicate 85 max_member(, , ), 86 min_member(, , ). 87 88:- set_prolog_flag(generate_debug_info, false). 89 90/** <module> List Manipulation 91 92This library provides commonly accepted basic predicates for list 93manipulation in the Prolog community. Some additional list manipulations 94are built-in. See e.g., memberchk/2, length/2. 95 96The implementation of this library is copied from many places. These 97include: "The Craft of Prolog", the DEC-10 Prolog library (LISTRO.PL) 98and the YAP lists library. Some predicates are reimplemented based on 99their specification by Quintus and SICStus. 100 101@compat Virtually every Prolog system has library(lists), but the set 102 of provided predicates is diverse. There is a fair agreement 103 on the semantics of most of these predicates, although error 104 handling may vary. 105*/ 106 107%! member(?Elem, ?List) 108% 109% True if Elem is a member of List. The SWI-Prolog definition 110% differs from the classical one. Our definition avoids unpacking 111% each list element twice and provides determinism on the last 112% element. E.g. this is deterministic: 113% 114% == 115% member(X, [One]). 116% == 117% 118% @author Gertjan van Noord 119 120member(El, [H|T]) :- 121 member_(T, El, H). 122 123member_(_, El, El). 124member_([H|T], El, _) :- 125 member_(T, El, H). 126 127%! append(?List1, ?List2, ?List1AndList2) 128% 129% List1AndList2 is the concatenation of List1 and List2 130 131append([], L, L). 132append([H|T], L, [H|R]) :- 133 append(T, L, R). 134 135%! append(+ListOfLists, ?List) 136% 137% Concatenate a list of lists. Is true if ListOfLists is a list of 138% lists, and List is the concatenation of these lists. 139% 140% @param ListOfLists must be a list of _possibly_ partial lists 141 142append(ListOfLists, List) :- 143 must_be(list, ListOfLists), 144 append_(ListOfLists, List). 145 146append_([], []). 147append_([L|Ls], As) :- 148 append(L, Ws, As), 149 append_(Ls, Ws). 150 151 152%! prefix(?Part, ?Whole) 153% 154% True iff Part is a leading substring of Whole. This is the same 155% as append(Part, _, Whole). 156 157prefix([], _). 158prefix([E|T0], [E|T]) :- 159 prefix(T0, T). 160 161 162%! select(?Elem, ?List1, ?List2) 163% 164% Is true when List1, with Elem removed, results in List2. This 165% implementation is determinsitic if the last element of List1 has 166% been selected. 167 168select(X, [Head|Tail], Rest) :- 169 select3_(Tail, Head, X, Rest). 170 171select3_(Tail, Head, Head, Tail). 172select3_([Head2|Tail], Head, X, [Head|Rest]) :- 173 select3_(Tail, Head2, X, Rest). 174 175 176%! selectchk(+Elem, +List, -Rest) is semidet. 177% 178% Semi-deterministic removal of first element in List that unifies 179% with Elem. 180 181selectchk(Elem, List, Rest) :- 182 select(Elem, List, Rest0), 183 !, 184 Rest = Rest0. 185 186 187%! select(?X, ?XList, ?Y, ?YList) is nondet. 188% 189% Select from two lists at the same position. True if XList is 190% unifiable with YList apart a single element at the same position 191% that is unified with X in XList and with Y in YList. A typical use 192% for this predicate is to _replace_ an element, as shown in the 193% example below. All possible substitutions are performed on 194% backtracking. 195% 196% == 197% ?- select(b, [a,b,c,b], 2, X). 198% X = [a, 2, c, b] ; 199% X = [a, b, c, 2] ; 200% false. 201% == 202% 203% @see selectchk/4 provides a semidet version. 204 205select(X, XList, Y, YList) :- 206 select4_(XList, X, Y, YList). 207 208select4_([X|List], X, Y, [Y|List]). 209select4_([X0|XList], X, Y, [X0|YList]) :- 210 select4_(XList, X, Y, YList). 211 212%! selectchk(?X, ?XList, ?Y, ?YList) is semidet. 213% 214% Semi-deterministic version of select/4. 215 216selectchk(X, XList, Y, YList) :- 217 select(X, XList, Y, YList), 218 !. 219 220%! nextto(?X, ?Y, ?List) 221% 222% True if Y directly follows X in List. 223 224nextto(X, Y, [X,Y|_]). 225nextto(X, Y, [_|Zs]) :- 226 nextto(X, Y, Zs). 227 228%! delete(+List1, @Elem, -List2) is det. 229% 230% Delete matching elements from a list. True when List2 is a list 231% with all elements from List1 except for those that unify with 232% Elem. Matching Elem with elements of List1 is uses =|\+ Elem \= 233% H|=, which implies that Elem is not changed. 234% 235% @deprecated There are too many ways in which one might want to 236% delete elements from a list to justify the name. 237% Think of matching (= vs. ==), delete first/all, 238% be deterministic or not. 239% @see select/3, subtract/3. 240 241delete([], _, []). 242delete([Elem|Tail], Del, Result) :- 243 ( \+ Elem \= Del 244 -> delete(Tail, Del, Result) 245 ; Result = [Elem|Rest], 246 delete(Tail, Del, Rest) 247 ). 248 249 250/* nth0/3, nth1/3 are improved versions from 251 Martin Jansche <martin@pc03.idf.uni-heidelberg.de> 252*/ 253 254%! nth0(?Index, ?List, ?Elem) 255% 256% True when Elem is the Index'th element of List. Counting starts 257% at 0. 258% 259% @error type_error(integer, Index) if Index is not an integer or 260% unbound. 261% @see nth1/3. 262 263nth0(Index, List, Elem) :- 264 ( integer(Index) 265 -> nth0_det(Index, List, Elem) % take nth deterministically 266 ; var(Index) 267 -> List = [H|T], 268 nth_gen(T, Elem, H, 0, Index) % match 269 ; must_be(integer, Index) 270 ). 271 272nth0_det(0, [Elem|_], Elem) :- !. 273nth0_det(1, [_,Elem|_], Elem) :- !. 274nth0_det(2, [_,_,Elem|_], Elem) :- !. 275nth0_det(3, [_,_,_,Elem|_], Elem) :- !. 276nth0_det(4, [_,_,_,_,Elem|_], Elem) :- !. 277nth0_det(5, [_,_,_,_,_,Elem|_], Elem) :- !. 278nth0_det(N, [_,_,_,_,_,_ |Tail], Elem) :- 279 M is N - 6, 280 M >= 0, 281 nth0_det(M, Tail, Elem). 282 283nth_gen(_, Elem, Elem, Base, Base). 284nth_gen([H|Tail], Elem, _, N, Base) :- 285 succ(N, M), 286 nth_gen(Tail, Elem, H, M, Base). 287 288 289%! nth1(?Index, ?List, ?Elem) 290% 291% Is true when Elem is the Index'th element of List. Counting 292% starts at 1. 293% 294% @see nth0/3. 295 296nth1(Index, List, Elem) :- 297 ( integer(Index) 298 -> Index0 is Index - 1, 299 nth0_det(Index0, List, Elem) % take nth deterministically 300 ; var(Index) 301 -> List = [H|T], 302 nth_gen(T, Elem, H, 1, Index) % match 303 ; must_be(integer, Index) 304 ). 305 306%! nth0(?N, ?List, ?Elem, ?Rest) is det. 307% 308% Select/insert element at index. True when Elem is the N'th 309% (0-based) element of List and Rest is the remainder (as in by 310% select/3) of List. For example: 311% 312% == 313% ?- nth0(I, [a,b,c], E, R). 314% I = 0, E = a, R = [b, c] ; 315% I = 1, E = b, R = [a, c] ; 316% I = 2, E = c, R = [a, b] ; 317% false. 318% == 319% 320% == 321% ?- nth0(1, L, a1, [a,b]). 322% L = [a, a1, b]. 323% == 324 325nth0(V, In, Element, Rest) :- 326 var(V), 327 !, 328 generate_nth(0, V, In, Element, Rest). 329nth0(V, In, Element, Rest) :- 330 must_be(nonneg, V), 331 find_nth0(V, In, Element, Rest). 332 333%! nth1(?N, ?List, ?Elem, ?Rest) is det. 334% 335% As nth0/4, but counting starts at 1. 336 337nth1(V, In, Element, Rest) :- 338 var(V), 339 !, 340 generate_nth(1, V, In, Element, Rest). 341nth1(V, In, Element, Rest) :- 342 must_be(positive_integer, V), 343 succ(V0, V), 344 find_nth0(V0, In, Element, Rest). 345 346generate_nth(I, I, [Head|Rest], Head, Rest). 347generate_nth(I, IN, [H|List], El, [H|Rest]) :- 348 I1 is I+1, 349 generate_nth(I1, IN, List, El, Rest). 350 351find_nth0(0, [Head|Rest], Head, Rest) :- !. 352find_nth0(N, [Head|Rest0], Elem, [Head|Rest]) :- 353 M is N-1, 354 find_nth0(M, Rest0, Elem, Rest). 355 356 357%! last(?List, ?Last) 358% 359% Succeeds when Last is the last element of List. This 360% predicate is =semidet= if List is a list and =multi= if List is 361% a partial list. 362% 363% @compat There is no de-facto standard for the argument order of 364% last/2. Be careful when porting code or use 365% append(_, [Last], List) as a portable alternative. 366 367last([X|Xs], Last) :- 368 last_(Xs, X, Last). 369 370last_([], Last, Last). 371last_([X|Xs], _, Last) :- 372 last_(Xs, X, Last). 373 374 375%! proper_length(@List, -Length) is semidet. 376% 377% True when Length is the number of elements in the proper list 378% List. This is equivalent to 379% 380% == 381% proper_length(List, Length) :- 382% is_list(List), 383% length(List, Length). 384% == 385 386proper_length(List, Length) :- 387 '$skip_list'(Length0, List, Tail), 388 Tail == [], 389 Length = Length0. 390 391 392%! same_length(?List1, ?List2) 393% 394% Is true when List1 and List2 are lists with the same number of 395% elements. The predicate is deterministic if at least one of the 396% arguments is a proper list. It is non-deterministic if both 397% arguments are partial lists. 398% 399% @see length/2 400 401same_length([], []). 402same_length([_|T1], [_|T2]) :- 403 same_length(T1, T2). 404 405 406%! reverse(?List1, ?List2) 407% 408% Is true when the elements of List2 are in reverse order compared to 409% List1. 410 411reverse(Xs, Ys) :- 412 reverse(Xs, [], Ys, Ys). 413 414reverse([], Ys, Ys, []). 415reverse([X|Xs], Rs, Ys, [_|Bound]) :- 416 reverse(Xs, [X|Rs], Ys, Bound). 417 418 419%! permutation(?Xs, ?Ys) is nondet. 420% 421% True when Xs is a permutation of Ys. This can solve for Ys given 422% Xs or Xs given Ys, or even enumerate Xs and Ys together. The 423% predicate permutation/2 is primarily intended to generate 424% permutations. Note that a list of length N has N! permutations, 425% and unbounded permutation generation becomes prohibitively 426% expensive, even for rather short lists (10! = 3,628,800). 427% 428% If both Xs and Ys are provided and both lists have equal length 429% the order is |Xs|^2. Simply testing whether Xs is a permutation 430% of Ys can be achieved in order log(|Xs|) using msort/2 as 431% illustrated below with the =semidet= predicate is_permutation/2: 432% 433% == 434% is_permutation(Xs, Ys) :- 435% msort(Xs, Sorted), 436% msort(Ys, Sorted). 437% == 438% 439% The example below illustrates that Xs and Ys being proper lists 440% is not a sufficient condition to use the above replacement. 441% 442% == 443% ?- permutation([1,2], [X,Y]). 444% X = 1, Y = 2 ; 445% X = 2, Y = 1 ; 446% false. 447% == 448% 449% @error type_error(list, Arg) if either argument is not a proper 450% or partial list. 451 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). 473 474%! flatten(+NestedList, -FlatList) is det. 475% 476% Is true if FlatList is a non-nested version of NestedList. Note 477% that empty lists are removed. In standard Prolog, this implies 478% that the atom '[]' is removed too. In SWI7, `[]` is distinct 479% from '[]'. 480% 481% Ending up needing flatten/2 often indicates, like append/3 for 482% appending two lists, a bad design. Efficient code that generates 483% lists from generated small lists must use difference lists, 484% often possible through grammar rules for optimal readability. 485% 486% @see append/2 487 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 *******************************/ 507 508%! clumped(+Items, -Pairs) 509% 510% Pairs is a list of `Item-Count` pairs that represents the _run 511% length encoding_ of Items. For example: 512% 513% ``` 514% ?- clumped([a,a,b,a,a,a,a,c,c,c], R). 515% R = [a-2, b-1, a-4, c-3]. 516% ``` 517% 518% @compat SICStus 519 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). 534 535 536 /******************************* 537 * ORDER OPERATIONS * 538 *******************************/ 539 540%! max_member(-Max, +List) is semidet. 541% 542% True when Max is the largest member in the standard order of 543% terms. Fails if List is empty. 544% 545% @see compare/3 546% @see max_list/2 for the maximum of a list of numbers. 547 548max_member(Max, [H|T]) => 549 max_member_(T, H, Max). 550max_member(_, []) => 551 fail. 552 553max_member_([], Max0, Max) => 554 Max = Max0. 555max_member_([H|T], Max0, Max) => 556 ( H @=< Max0 557 -> max_member_(T, Max0, Max) 558 ; max_member_(T, H, Max) 559 ). 560 561 562%! min_member(-Min, +List) is semidet. 563% 564% True when Min is the smallest member in the standard order of 565% terms. Fails if List is empty. 566% 567% @see compare/3 568% @see min_list/2 for the minimum of a list of numbers. 569 570min_member(Min, [H|T]) => 571 min_member_(T, H, Min). 572min_member(_, []) => 573 fail. 574 575min_member_([], Min0, Min) => 576 Min = Min0. 577min_member_([H|T], Min0, Min) => 578 ( H @>= Min0 579 -> min_member_(T, Min0, Min) 580 ; min_member_(T, H, Min) 581 ). 582 583 584%! max_member(:Pred, -Max, +List) is semidet. 585% 586% True when Max is the largest member according to Pred, which must be 587% a 2-argument callable that behaves like (@=<)/2. Fails if List is 588% empty. The following call is equivalent to max_member/2: 589% 590% ?- max_member(@=<, X, [6,1,8,4]). 591% X = 8. 592% 593% @see max_list/2 for the maximum of a list of numbers. 594 595max_member(Pred, Max, [H|T]) => 596 max_member_(T, Pred, H, Max). 597max_member(_, _, []) => 598 fail. 599 600max_member_([], _, Max0, Max) => 601 Max = Max0. 602max_member_([H|T], Pred, Max0, Max) => 603 ( call(Pred, H, Max0) 604 -> max_member_(T, Pred, Max0, Max) 605 ; max_member_(T, Pred, H, Max) 606 ). 607 608 609%! min_member(:Pred, -Min, +List) is semidet. 610% 611% True when Min is the smallest member according to Pred, which must 612% be a 2-argument callable that behaves like (@=<)/2. Fails if List is 613% empty. The following call is equivalent to max_member/2: 614% 615% ?- min_member(@=<, X, [6,1,8,4]). 616% X = 1. 617% 618% @see min_list/2 for the minimum of a list of numbers. 619 620min_member(Pred, Min, [H|T]) => 621 min_member_(T, Pred, H, Min). 622min_member(_, _, []) => 623 fail. 624 625min_member_([], _, Min0, Min) => 626 Min = Min0. 627min_member_([H|T], Pred, Min0, Min) => 628 ( call(Pred, Min0, H) 629 -> min_member_(T, Pred, Min0, Min) 630 ; min_member_(T, Pred, H, Min) 631 ). 632 633 634 /******************************* 635 * LISTS OF NUMBERS * 636 *******************************/ 637 638%! sum_list(+List, -Sum) is det. 639% 640% Sum is the result of adding all numbers in List. 641 642sum_list(Xs, Sum) :- 643 sum_list(Xs, 0, Sum). 644 645sum_list([], Sum0, Sum) => 646 Sum = Sum0. 647sum_list([X|Xs], Sum0, Sum) => 648 Sum1 is Sum0 + X, 649 sum_list(Xs, Sum1, Sum). 650 651%! max_list(+List:list(number), -Max:number) is semidet. 652% 653% True if Max is the largest number in List. Fails if List is 654% empty. 655% 656% @see max_member/2. 657 658max_list([H|T], Max) => 659 max_list(T, H, Max). 660max_list([], _) => fail. 661 662max_list([], Max0, Max) => 663 Max = Max0. 664max_list([H|T], Max0, Max) => 665 Max1 is max(H, Max0), 666 max_list(T, Max1, Max). 667 668 669%! min_list(+List:list(number), -Min:number) is semidet. 670% 671% True if Min is the smallest number in List. Fails if List is 672% empty. 673% 674% @see min_member/2. 675 676min_list([H|T], Min) => 677 min_list(T, H, Min). 678min_list([], _) => fail. 679 680min_list([], Min0, Min) => 681 Min = Min0. 682min_list([H|T], Min0, Min) => 683 Min1 is min(H, Min0), 684 min_list(T, Min1, Min). 685 686 687%! numlist(+Low, +High, -List) is semidet. 688% 689% List is a list [Low, Low+1, ... High]. Fails if High < Low. 690% 691% @error type_error(integer, Low) 692% @error type_error(integer, High) 693 694numlist(L, U, Ns) :- 695 must_be(integer, L), 696 must_be(integer, U), 697 L =< U, 698 numlist_(L, U, Ns). 699 700numlist_(U, U, List) :- 701 !, 702 List = [U]. 703numlist_(L, U, [L|Ns]) :- 704 L2 is L+1, 705 numlist_(L2, U, Ns). 706 707 708 /******************************** 709 * SET MANIPULATION * 710 *********************************/ 711 712%! is_set(@Set) is semidet. 713% 714% True if Set is a proper list without duplicates. Equivalence is 715% based on ==/2. The implementation uses sort/2, which implies 716% that the complexity is N*log(N) and the predicate may cause a 717% resource-error. There are no other error conditions. 718 719is_set(Set) :- 720 '$skip_list'(Len, Set, Tail), 721 Tail == [], % Proper list 722 sort(Set, Sorted), 723 length(Sorted, Len). 724 725 726%! list_to_set(+List, ?Set) is det. 727% 728% True when Set has the same elements as List in the same order. 729% The left-most copy of duplicate elements is retained. List may 730% contain variables. Elements _E1_ and _E2_ are considered 731% duplicates iff _E1_ == _E2_ holds. The complexity of the 732% implementation is N*log(N). 733% 734% @see sort/2 can be used to create an ordered set. Many 735% set operations on ordered sets are order N rather than 736% order N**2. The list_to_set/2 predicate is more 737% expensive than sort/2 because it involves, two sorts 738% and a linear scan. 739% @compat Up to version 6.3.11, list_to_set/2 had complexity 740% N**2 and equality was tested using =/2. 741% @error List is type-checked. 742 743list_to_set(List, Set) :- 744 must_be(list, List), 745 number_list(List, 1, Numbered), 746 sort(1, @=<, Numbered, ONum), 747 remove_dup_keys(ONum, NumSet), 748 sort(2, @=<, NumSet, ONumSet), 749 pairs_keys(ONumSet, Set). 750 751number_list([], _, []). 752number_list([H|T0], N, [H-N|T]) :- 753 N1 is N+1, 754 number_list(T0, N1, T). 755 756remove_dup_keys([], []). 757remove_dup_keys([H|T0], [H|T]) :- 758 H = V-_, 759 remove_same_key(T0, V, T1), 760 remove_dup_keys(T1, T). 761 762remove_same_key([V1-_|T0], V, T) :- 763 V1 == V, 764 !, 765 remove_same_key(T0, V, T). 766remove_same_key(L, _, L). 767 768 769%! intersection(+Set1, +Set2, -Set3) is det. 770% 771% True if Set3 unifies with the intersection of Set1 and Set2. The 772% complexity of this predicate is |Set1|*|Set2|. A _set_ is defined to 773% be an unordered list without duplicates. Elements are considered 774% duplicates if they can be unified. 775% 776% @see ord_intersection/3. 777 778intersection([], _, Set) => 779 Set = []. 780intersection([X|T], L, Intersect) => 781 ( memberchk(X, L) 782 -> Intersect = [X|R], 783 intersection(T, L, R) 784 ; intersection(T, L, Intersect) 785 ). 786 787%! union(+Set1, +Set2, -Set3) is det. 788% 789% True if Set3 unifies with the union of the lists Set1 and Set2. The 790% complexity of this predicate is |Set1|*|Set2|. A _set_ is defined to 791% be an unordered list without duplicates. Elements are considered 792% duplicates if they can be unified. 793% 794% @see ord_union/3 795 796union([], L0, L) => 797 L = L0. 798union([H|T], L, Union) => 799 ( memberchk(H, L) 800 -> union(T, L, Union) 801 ; Union = [H|R], 802 union(T, L, R) 803 ). 804 805%! subset(+SubSet, +Set) is semidet. 806% 807% True if all elements of SubSet belong to Set as well. Membership 808% test is based on memberchk/2. The complexity is |SubSet|*|Set|. A 809% _set_ is defined to be an unordered list without duplicates. 810% Elements are considered duplicates if they can be unified. 811% 812% @see ord_subset/2. 813 814subset([], _) => true. 815subset([E|R], Set) => 816 memberchk(E, Set), 817 subset(R, Set). 818 819 820%! subtract(+Set, +Delete, -Result) is det. 821% 822% Delete all elements in Delete from Set. Deletion is based on 823% unification using memberchk/2. The complexity is |Delete|*|Set|. A 824% _set_ is defined to be an unordered list without duplicates. 825% Elements are considered duplicates if they can be unified. 826% 827% @see ord_subtract/3. 828 829subtract([], _, R) => 830 R = []. 831subtract([E|T], D, R) => 832 ( memberchk(E, D) 833 -> subtract(T, D, R) 834 ; R = [E|R1], 835 subtract(T, D, R1) 836 )