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-2022, 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 -> '$seek_list'(Index, List, RestIndex, RestList), 266 nth0_det(RestIndex, RestList, Elem) % take nth det 267 ; var(Index) 268 -> List = [H|T], 269 nth_gen(T, Elem, H, 0, Index) % match 270 ; must_be(integer, Index) 271 ). 272 273nth0_det(0, [Elem|_], Elem) :- !. 274nth0_det(N, [_|Tail], Elem) :- 275 M is N - 1, 276 M >= 0, 277 nth0_det(M, Tail, Elem). 278 279nth_gen(_, Elem, Elem, Base, Base). 280nth_gen([H|Tail], Elem, _, N, Base) :- 281 succ(N, M), 282 nth_gen(Tail, Elem, H, M, Base).
292nth1(Index, List, Elem) :-
293 ( integer(Index)
294 -> Index0 is Index - 1,
295 '$seek_list'(Index0, List, RestIndex, RestList),
296 nth0_det(RestIndex, RestList, Elem) % take nth det
297 ; var(Index)
298 -> List = [H|T],
299 nth_gen(T, Elem, H, 1, Index) % match
300 ; must_be(integer, Index)
301 ).
?- 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].
322nth0(V, In, Element, Rest) :- 323 var(V), 324 !, 325 generate_nth(0, V, In, Element, Rest). 326nth0(V, In, Element, Rest) :- 327 must_be(nonneg, V), 328 find_nth0(V, In, Element, Rest).
334nth1(V, In, Element, Rest) :- 335 var(V), 336 !, 337 generate_nth(1, V, In, Element, Rest). 338nth1(V, In, Element, Rest) :- 339 must_be(positive_integer, V), 340 succ(V0, V), 341 find_nth0(V0, In, Element, Rest). 342 343generate_nth(I, I, [Head|Rest], Head, Rest). 344generate_nth(I, IN, [H|List], El, [H|Rest]) :- 345 I1 is I+1, 346 generate_nth(I1, IN, List, El, Rest). 347 348find_nth0(0, [Head|Rest], Head, Rest) :- !. 349find_nth0(N, [Head|Rest0], Elem, [Head|Rest]) :- 350 M is N-1, 351 find_nth0(M, Rest0, Elem, Rest).
semidet
if List is a list and multi
if List is
a partial list.
364last([X|Xs], Last) :- 365 last_(Xs, X, Last). 366 367last_([], Last, Last). 368last_([X|Xs], _, Last) :- 369 last_(Xs, X, Last).
proper_length(List, Length) :- is_list(List), length(List, Length).
383proper_length(List, Length) :-
384 '$skip_list'(Length0, List, Tail),
385 Tail == [],
386 Length = Length0.
398same_length([], []). 399same_length([_|T1], [_|T2]) :- 400 same_length(T1, T2).
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).
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.
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).
[]
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.
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 *******************************/
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].
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 /******************************* 536 * ORDER OPERATIONS * 537 *******************************/
547max_member(Max, [H|T]) => 548 max_member_(T, H, Max). 549max_member(_, []) => 550 fail. 551 552max_member_([], Max0, Max) => 553 Max = Max0. 554max_member_([H|T], Max0, Max) => 555 ( H @=< Max0 556 -> max_member_(T, Max0, Max) 557 ; max_member_(T, H, Max) 558 ).
569min_member(Min, [H|T]) => 570 min_member_(T, H, Min). 571min_member(_, []) => 572 fail. 573 574min_member_([], Min0, Min) => 575 Min = Min0. 576min_member_([H|T], Min0, Min) => 577 ( H @>= Min0 578 -> min_member_(T, Min0, Min) 579 ; min_member_(T, H, Min) 580 ).
?- max_member(@=<, X, [6,1,8,4]). X = 8.
594max_member(Pred, Max, [H|T]) => 595 max_member_(T, Pred, H, Max). 596max_member(_, _, []) => 597 fail. 598 599max_member_([], _, Max0, Max) => 600 Max = Max0. 601max_member_([H|T], Pred, Max0, Max) => 602 ( call(Pred, H, Max0) 603 -> max_member_(T, Pred, Max0, Max) 604 ; max_member_(T, Pred, H, Max) 605 ).
?- min_member(@=<, X, [6,1,8,4]). X = 1.
619min_member(Pred, Min, [H|T]) => 620 min_member_(T, Pred, H, Min). 621min_member(_, _, []) => 622 fail. 623 624min_member_([], _, Min0, Min) => 625 Min = Min0. 626min_member_([H|T], Pred, Min0, Min) => 627 ( call(Pred, Min0, H) 628 -> min_member_(T, Pred, Min0, Min) 629 ; min_member_(T, Pred, H, Min) 630 ). 631 632 633 /******************************* 634 * LISTS OF NUMBERS * 635 *******************************/
641sum_list(Xs, Sum) :- 642 sum_list(Xs, 0, Sum). 643 644sum_list([], Sum0, Sum) => 645 Sum = Sum0. 646sum_list([X|Xs], Sum0, Sum) => 647 Sum1 is Sum0 + X, 648 sum_list(Xs, Sum1, Sum).
657max_list([H|T], Max) => 658 max_list(T, H, Max). 659max_list([], _) => fail. 660 661max_list([], Max0, Max) => 662 Max = Max0. 663max_list([H|T], Max0, Max) => 664 Max1 is max(H, Max0), 665 max_list(T, Max1, Max).
675min_list([H|T], Min) => 676 min_list(T, H, Min). 677min_list([], _) => fail. 678 679min_list([], Min0, Min) => 680 Min = Min0. 681min_list([H|T], Min0, Min) => 682 Min1 is min(H, Min0), 683 min_list(T, Min1, Min).
693numlist(L, U, Ns) :- 694 must_be(integer, L), 695 must_be(integer, U), 696 L =< U, 697 numlist_(L, U, Ns). 698 699numlist_(U, U, List) :- 700 !, 701 List = [U]. 702numlist_(L, U, [L|Ns]) :- 703 L2 is L+1, 704 numlist_(L2, U, Ns). 705 706 707 /******************************** 708 * SET MANIPULATION * 709 *********************************/
log(N)
and the predicate may cause a
resource-error. There are no other error conditions. 718is_set(Set) :-
719 '$skip_list'(Len, Set, Tail),
720 Tail == [], % Proper list
721 sort(Set, Sorted),
722 length(Sorted, Len).
log(N)
.
742list_to_set(List, Set) :- 743 must_be(list, List), 744 number_list(List, 1, Numbered), 745 sort(1, @=<, Numbered, ONum), 746 remove_dup_keys(ONum, NumSet), 747 sort(2, @=<, NumSet, ONumSet), 748 pairs_keys(ONumSet, Set). 749 750number_list([], _, []). 751number_list([H|T0], N, [H-N|T]) :- 752 N1 is N+1, 753 number_list(T0, N1, T). 754 755remove_dup_keys([], []). 756remove_dup_keys([H|T0], [H|T]) :- 757 H = V-_, 758 remove_same_key(T0, V, T1), 759 remove_dup_keys(T1, T). 760 761remove_same_key([V1-_|T0], V, T) :- 762 V1 == V, 763 !, 764 remove_same_key(T0, V, T). 765remove_same_key(L, _, L).
777intersection([], _, Set) => 778 Set = []. 779intersection([X|T], L, Intersect) => 780 ( memberchk(X, L) 781 -> Intersect = [X|R], 782 intersection(T, L, R) 783 ; intersection(T, L, Intersect) 784 ).
795union([], L0, L) => 796 L = L0. 797union([H|T], L, Union) => 798 ( memberchk(H, L) 799 -> union(T, L, Union) 800 ; Union = [H|R], 801 union(T, L, R) 802 ).
813subset([], _) => true. 814subset([E|R], Set) => 815 memberchk(E, Set), 816 subset(R, Set).
828subtract([], _, R) => 829 R = []. 830subtract([E|T], D, R) => 831 ( memberchk(E, D) 832 -> subtract(T, D, R) 833 ; R = [E|R1], 834 subtract(T, D, R1) 835 )
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.