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-2020, 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 65 % Lists of numbers 66 sum_list/2, % +List, -Sum 67 max_list/2, % +List, -Max 68 min_list/2, % +List, -Min 69 numlist/3, % +Low, +High, -List 70 71 % set manipulation 72 is_set/1, % +List 73 list_to_set/2, % +List, -Set 74 intersection/3, % +List1, +List2, -Intersection 75 union/3, % +List1, +List2, -Union 76 subset/2, % +SubSet, +Set 77 subtract/3 % +Set, +Delete, -Remaining 78 ]). 79:- autoload(library(error),[must_be/2]). 80:- autoload(library(pairs),[pairs_keys/2]). 81 82 83:- set_prolog_flag(generate_debug_info, false).
member(X, [One]).
115member(El, [H|T]) :- 116 member_(T, El, H). 117 118member_(_, El, El). 119member_([H|T], El, _) :- 120 member_(T, El, H).
126append([], L, L). 127append([H|T], L, [H|R]) :- 128 append(T, L, R).
137append(ListOfLists, List) :- 138 must_be(list, ListOfLists), 139 append_(ListOfLists, List). 140 141append_([], []). 142append_([L|Ls], As) :- 143 append(L, Ws, As), 144 append_(Ls, Ws).
append(Part, _, Whole)
.152prefix([], _). 153prefix([E|T0], [E|T]) :- 154 prefix(T0, T).
163select(X, [Head|Tail], Rest) :- 164 select3_(Tail, Head, X, Rest). 165 166select3_(Tail, Head, Head, Tail). 167select3_([Head2|Tail], Head, X, [Head|Rest]) :- 168 select3_(Tail, Head2, X, Rest).
176selectchk(Elem, List, Rest) :-
177 select(Elem, List, Rest0),
178 !,
179 Rest = Rest0.
?- select(b, [a,b,c,b], 2, X). X = [a, 2, c, b] ; X = [a, b, c, 2] ; false.
200select(X, XList, Y, YList) :- 201 select4_(XList, X, Y, YList). 202 203select4_([X|List], X, Y, [Y|List]). 204select4_([X0|XList], X, Y, [X0|YList]) :- 205 select4_(XList, X, Y, YList).
211selectchk(X, XList, Y, YList) :-
212 select(X, XList, Y, YList),
213 !.
219nextto(X, Y, [X,Y|_]). 220nextto(X, Y, [_|Zs]) :- 221 nextto(X, Y, Zs).
\+ Elem \=
H
, which implies that Elem is not changed.
236delete([], _, []). 237delete([Elem|Tail], Del, Result) :- 238 ( \+ Elem \= Del 239 -> delete(Tail, Del, Result) 240 ; Result = [Elem|Rest], 241 delete(Tail, Del, Rest) 242 ). 243 244 245/* nth0/3, nth1/3 are improved versions from 246 Martin Jansche <martin@pc03.idf.uni-heidelberg.de> 247*/
258nth0(Index, List, Elem) :- 259 ( integer(Index) 260 -> nth0_det(Index, List, Elem) % take nth deterministically 261 ; var(Index) 262 -> List = [H|T], 263 nth_gen(T, Elem, H, 0, Index) % match 264 ; must_be(integer, Index) 265 ). 266 267nth0_det(0, [Elem|_], Elem) :- !. 268nth0_det(1, [_,Elem|_], Elem) :- !. 269nth0_det(2, [_,_,Elem|_], Elem) :- !. 270nth0_det(3, [_,_,_,Elem|_], Elem) :- !. 271nth0_det(4, [_,_,_,_,Elem|_], Elem) :- !. 272nth0_det(5, [_,_,_,_,_,Elem|_], Elem) :- !. 273nth0_det(N, [_,_,_,_,_,_ |Tail], Elem) :- 274 M is N - 6, 275 M >= 0, 276 nth0_det(M, Tail, Elem). 277 278nth_gen(_, Elem, Elem, Base, Base). 279nth_gen([H|Tail], Elem, _, N, Base) :- 280 succ(N, M), 281 nth_gen(Tail, Elem, H, M, Base).
291nth1(Index, List, Elem) :-
292 ( integer(Index)
293 -> Index0 is Index - 1,
294 nth0_det(Index0, List, Elem) % take nth deterministically
295 ; var(Index)
296 -> List = [H|T],
297 nth_gen(T, Elem, H, 1, Index) % match
298 ; must_be(integer, Index)
299 ).
?- 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].
320nth0(V, In, Element, Rest) :- 321 var(V), 322 !, 323 generate_nth(0, V, In, Element, Rest). 324nth0(V, In, Element, Rest) :- 325 must_be(nonneg, V), 326 find_nth0(V, In, Element, Rest).
332nth1(V, In, Element, Rest) :- 333 var(V), 334 !, 335 generate_nth(1, V, In, Element, Rest). 336nth1(V, In, Element, Rest) :- 337 must_be(positive_integer, V), 338 succ(V0, V), 339 find_nth0(V0, In, Element, Rest). 340 341generate_nth(I, I, [Head|Rest], Head, Rest). 342generate_nth(I, IN, [H|List], El, [H|Rest]) :- 343 I1 is I+1, 344 generate_nth(I1, IN, List, El, Rest). 345 346find_nth0(0, [Head|Rest], Head, Rest) :- !. 347find_nth0(N, [Head|Rest0], Elem, [Head|Rest]) :- 348 M is N-1, 349 find_nth0(M, Rest0, Elem, Rest).
semidet
if List is a list and multi
if List is
a partial list.
362last([X|Xs], Last) :- 363 last_(Xs, X, Last). 364 365last_([], Last, Last). 366last_([X|Xs], _, Last) :- 367 last_(Xs, X, Last).
proper_length(List, Length) :- is_list(List), length(List, Length).
381proper_length(List, Length) :-
382 '$skip_list'(Length0, List, Tail),
383 Tail == [],
384 Length = Length0.
396same_length([], []). 397same_length([_|T1], [_|T2]) :- 398 same_length(T1, T2).
406reverse(Xs, Ys) :- 407 reverse(Xs, [], Ys, Ys). 408 409reverse([], Ys, Ys, []). 410reverse([X|Xs], Rs, Ys, [_|Bound]) :- 411 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.
447permutation(Xs, Ys) :- 448 '$skip_list'(Xlen, Xs, XTail), 449 '$skip_list'(Ylen, Ys, YTail), 450 ( XTail == [], YTail == [] % both proper lists 451 -> Xlen == Ylen 452 ; var(XTail), YTail == [] % partial, proper 453 -> length(Xs, Ylen) 454 ; XTail == [], var(YTail) % proper, partial 455 -> length(Ys, Xlen) 456 ; var(XTail), var(YTail) % partial, partial 457 -> length(Xs, Len), 458 length(Ys, Len) 459 ; must_be(list, Xs), % either is not a list 460 must_be(list, Ys) 461 ), 462 perm(Xs, Ys). 463 464perm([], []). 465perm(List, [First|Perm]) :- 466 select(First, List, Rest), 467 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.
483flatten(List, FlatList) :- 484 flatten(List, [], FlatList0), 485 !, 486 FlatList = FlatList0. 487 488flatten(Var, Tl, [Var|Tl]) :- 489 var(Var), 490 !. 491flatten([], Tl, Tl) :- !. 492flatten([Hd|Tl], Tail, List) :- 493 !, 494 flatten(Hd, FlatHeadTail, List), 495 flatten(Tl, Tail, FlatHeadTail). 496flatten(NonList, Tl, [NonList|Tl]). 497 498 499 /******************************* 500 * CLUMPS * 501 *******************************/
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].
515clumped(Items, Counts) :- 516 clump(Items, Counts). 517 518clump([], []). 519clump([H|T0], [H-C|T]) :- 520 ccount(T0, H, T1, 1, C), 521 clump(T1, T). 522 523ccount([H|T0], E, T, C0, C) :- 524 E == H, 525 !, 526 C1 is C0+1, 527 ccount(T0, E, T, C1, C). 528ccount(List, _, List, C, C). 529 530 531 /******************************* 532 * ORDER OPERATIONS * 533 *******************************/
543max_member(Max, [H|T]) => 544 max_member_(T, H, Max). 545max_member(_, []) => 546 fail. 547 548max_member_([], Max0, Max) => 549 Max = Max0. 550max_member_([H|T], Max0, Max) => 551 ( H @=< Max0 552 -> max_member_(T, Max0, Max) 553 ; max_member_(T, H, Max) 554 ).
565min_member(Min, [H|T]) => 566 min_member_(T, H, Min). 567min_member(_, []) => 568 fail. 569 570min_member_([], Min0, Min) => 571 Min = Min0. 572min_member_([H|T], Min0, Min) => 573 ( H @>= Min0 574 -> min_member_(T, Min0, Min) 575 ; min_member_(T, H, Min) 576 ). 577 578 579 /******************************* 580 * LISTS OF NUMBERS * 581 *******************************/
587sum_list(Xs, Sum) :- 588 sum_list(Xs, 0, Sum). 589 590sum_list([], Sum0, Sum) => 591 Sum = Sum0. 592sum_list([X|Xs], Sum0, Sum) => 593 Sum1 is Sum0 + X, 594 sum_list(Xs, Sum1, Sum).
603max_list([H|T], Max) => 604 max_list(T, H, Max). 605max_list([], _) => fail. 606 607max_list([], Max0, Max) => 608 Max = Max0. 609max_list([H|T], Max0, Max) => 610 Max1 is max(H, Max0), 611 max_list(T, Max1, Max).
621min_list([H|T], Min) => 622 min_list(T, H, Min). 623min_list([], _) => fail. 624 625min_list([], Min0, Min) => 626 Min = Min0. 627min_list([H|T], Min0, Min) => 628 Min1 is min(H, Min0), 629 min_list(T, Min1, Min).
639numlist(L, U, Ns) :- 640 must_be(integer, L), 641 must_be(integer, U), 642 L =< U, 643 numlist_(L, U, Ns). 644 645numlist_(U, U, List) :- 646 !, 647 List = [U]. 648numlist_(L, U, [L|Ns]) :- 649 L2 is L+1, 650 numlist_(L2, U, Ns). 651 652 653 /******************************** 654 * SET MANIPULATION * 655 *********************************/
log(N)
and the predicate may cause a
resource-error. There are no other error conditions. 664is_set(Set) :-
665 '$skip_list'(Len, Set, Tail),
666 Tail == [], % Proper list
667 sort(Set, Sorted),
668 length(Sorted, Len).
log(N)
.
688list_to_set(List, Set) :- 689 must_be(list, List), 690 number_list(List, 1, Numbered), 691 sort(1, @=<, Numbered, ONum), 692 remove_dup_keys(ONum, NumSet), 693 sort(2, @=<, NumSet, ONumSet), 694 pairs_keys(ONumSet, Set). 695 696number_list([], _, []). 697number_list([H|T0], N, [H-N|T]) :- 698 N1 is N+1, 699 number_list(T0, N1, T). 700 701remove_dup_keys([], []). 702remove_dup_keys([H|T0], [H|T]) :- 703 H = V-_, 704 remove_same_key(T0, V, T1), 705 remove_dup_keys(T1, T). 706 707remove_same_key([V1-_|T0], V, T) :- 708 V1 == V, 709 !, 710 remove_same_key(T0, V, T). 711remove_same_key(L, _, L).
723intersection([], _, Set) => 724 Set = []. 725intersection([X|T], L, Intersect) => 726 ( memberchk(X, L) 727 -> Intersect = [X|R], 728 intersection(T, L, R) 729 ; intersection(T, L, Intersect) 730 ).
741union([], L0, L) => 742 L = L0. 743union([H|T], L, Union) => 744 ( memberchk(H, L) 745 -> union(T, L, Union) 746 ; Union = [H|R], 747 union(T, L, R) 748 ).
759subset([], _) => true. 760subset([E|R], Set) => 761 memberchk(E, Set), 762 subset(R, Set).
774subtract([], _, R) => 775 R = []. 776subtract([E|T], D, R) => 777 ( memberchk(E, D) 778 -> subtract(T, D, R) 779 ; R = [E|R1], 780 subtract(T, D, R1) 781 )
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.