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