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).
member(X, [One]).
120member(El, [H|T]) :- 121 member_(T, El, H). 122 123member_(_, El, El). 124member_([H|T], El, _) :- 125 member_(T, El, H).
131append([], L, L). 132append([H|T], L, [H|R]) :- 133 append(T, L, R).
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).
append(Part, _, Whole)
.157prefix([], _). 158prefix([E|T0], [E|T]) :- 159 prefix(T0, T).
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).
181selectchk(Elem, List, Rest) :-
182 select(Elem, List, Rest0),
183 !,
184 Rest = Rest0.
?- select(b, [a,b,c,b], 2, X). X = [a, 2, c, b] ; X = [a, b, c, 2] ; false.
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).
216selectchk(X, XList, Y, YList) :-
217 select(X, XList, Y, YList),
218 !.
224nextto(X, Y, [X,Y|_]). 225nextto(X, Y, [_|Zs]) :- 226 nextto(X, Y, Zs).
\+ Elem \=
H
, which implies that Elem is not changed.
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*/
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).
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 ).
?- 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].
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).
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).
semidet
if List is a list and multi
if List is
a partial list.
367last([X|Xs], Last) :- 368 last_(Xs, X, Last). 369 370last_([], Last, Last). 371last_([X|Xs], _, Last) :- 372 last_(Xs, X, Last).
proper_length(List, Length) :- is_list(List), length(List, Length).
386proper_length(List, Length) :-
387 '$skip_list'(Length0, List, Tail),
388 Tail == [],
389 Length = Length0.
401same_length([], []). 402same_length([_|T1], [_|T2]) :- 403 same_length(T1, T2).
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).
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.
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).
[]
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.
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 *******************************/
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].
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 *******************************/
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 ).
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 ).
?- max_member(@=<, X, [6,1,8,4]). X = 8.
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 ).
?- min_member(@=<, X, [6,1,8,4]). X = 1.
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 *******************************/
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).
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).
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).
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 *********************************/
log(N)
and the predicate may cause a
resource-error. There are no other error conditions. 719is_set(Set) :-
720 '$skip_list'(Len, Set, Tail),
721 Tail == [], % Proper list
722 sort(Set, Sorted),
723 length(Sorted, Len).
log(N)
.
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).
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 ).
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 ).
814subset([], _) => true. 815subset([E|R], Set) => 816 memberchk(E, Set), 817 subset(R, Set).
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 )
List Manipulation
This library provides commonly accepted basic predicates for list manipulation in the Prolog community. Some additional list manipulations are built-in. See e.g., memberchk/2, length/2.
The implementation of this library is copied from many places. These include: "The Craft of Prolog", the DEC-10 Prolog library (LISTRO.PL) and the YAP lists library. Some predicates are reimplemented based on their specification by Quintus and SICStus.