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).
member(X, [One]).
111member(El, [H|T]) :- 112 member_(T, El, H). 113 114member_(_, El, El). 115member_([H|T], El, _) :- 116 member_(T, El, H).
122append([], L, L). 123append([H|T], L, [H|R]) :- 124 append(T, L, R).
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).
append(Part, _, Whole)
.148prefix([], _). 149prefix([E|T0], [E|T]) :- 150 prefix(T0, T).
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).
172selectchk(Elem, List, Rest) :-
173 select(Elem, List, Rest0),
174 !,
175 Rest = Rest0.
?- select(b, [a,b,c,b], 2, X). X = [a, 2, c, b] ; X = [a, b, c, 2] ; false.
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).
207selectchk(X, XList, Y, YList) :-
208 select(X, XList, Y, YList),
209 !.
215nextto(X, Y, [X,Y|_]). 216nextto(X, Y, [_|Zs]) :- 217 nextto(X, Y, Zs).
\+ Elem \=
H
, which implies that Elem is not changed.
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*/
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).
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 ).
?- 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].
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).
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).
semidet
if List is a list and multi
if List is
a partial list.
358last([X|Xs], Last) :- 359 last_(Xs, X, Last). 360 361last_([], Last, Last). 362last_([X|Xs], _, Last) :- 363 last_(Xs, X, Last).
proper_length(List, Length) :- is_list(List), length(List, Length).
377proper_length(List, Length) :-
378 '$skip_list'(Length0, List, Tail),
379 Tail == [],
380 Length = Length0.
392same_length([], []). 393same_length([_|T1], [_|T2]) :- 394 same_length(T1, T2).
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).
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.
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).
[]
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.
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 *******************************/
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 ).
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 *******************************/
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).
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).
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).
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 *********************************/
log(N)
and the predicate may cause a
resource-error. There are no other error conditions. 617is_set(Set) :-
618 '$skip_list'(Len, Set, Tail),
619 Tail == [], % Proper list
620 sort(Set, Sorted),
621 length(Sorted, Len).
log(N)
.
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).
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).
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).
713subset([], _) :- !. 714subset([E|R], Set) :- 715 memberchk(E, Set), 716 subset(R, Set).
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)
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.