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( , , ), 87 min_member( , , ). 88 89:- set_prolog_flag(generate_debug_info, false).
member(X, [One]).
121member(El, [H|T]) :- 122 member_(T, El, H). 123 124member_(_, El, El). 125member_([H|T], El, _) :- 126 member_(T, El, H).
132append([], L, L). 133append([H|T], L, [H|R]) :- 134 append(T, L, R).
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).
append(Part, _, Whole)
.158prefix([], _). 159prefix([E|T0], [E|T]) :- 160 prefix(T0, T).
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).
182selectchk(Elem, List, Rest) :-
183 select(Elem, List, Rest0),
184 !,
185 Rest = Rest0.
?- select(b, [a,b,c,b], 2, X). X = [a, 2, c, b] ; X = [a, b, c, 2] ; false.
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).
217selectchk(X, XList, Y, YList) :-
218 select(X, XList, Y, YList),
219 !.
225nextto(X, Y, [X,Y|_]). 226nextto(X, Y, [_|Zs]) :- 227 nextto(X, Y, Zs).
\+ Elem \=
H
, which implies that Elem is not changed.
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*/
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).
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(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).
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).
semidet
if List is a list and multi
if List is
a partial list.
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_list(List), length(List, Length).
384proper_length(List, Length) :-
385 '$skip_list'(Length0, List, Tail),
386 Tail == [],
387 Length = Length0.
399same_length([], []). 400same_length([_|T1], [_|T2]) :- 401 same_length(T1, T2).
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).
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).
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 *******************************/
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 ).
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(@=<, X, [6,1,8,4]). X = 8.
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(@=<, X, [6,1,8,4]). X = 1.
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 *******************************/
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).
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).
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).
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 *********************************/
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).
log(N)
.
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).
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 ).
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 ).
839subset([], _) => true. 840subset([E|R], Set) => 841 memberchk(E, Set), 842 subset(R, Set).
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 )
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.