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).
157select(X, [X|Tail], Tail). 158select(Elem, [Head|Tail], [Head|Rest]) :- 159 select(Elem, Tail, Rest).
167selectchk(Elem, List, Rest) :-
168 select(Elem, List, Rest0),
169 !,
170 Rest = Rest0.
?- select(b, [a,b,c,b], 2, X). X = [a, 2, c, b] ; X = [a, b, c, 2] ; false.
191select(X, XList, Y, YList) :- 192 select_(XList, X, Y, YList). 193 194select_([X|List], X, Y, [Y|List]). 195select_([X0|XList], X, Y, [X0|YList]) :- 196 select_(XList, X, Y, YList).
202selectchk(X, XList, Y, YList) :-
203 select(X, XList, Y, YList),
204 !.
210nextto(X, Y, [X,Y|_]). 211nextto(X, Y, [_|Zs]) :- 212 nextto(X, Y, Zs).
\+ Elem \=
H
, which implies that Elem is not changed.
227delete([], _, []). 228delete([Elem|Tail], Del, Result) :- 229 ( \+ Elem \= Del 230 -> delete(Tail, Del, Result) 231 ; Result = [Elem|Rest], 232 delete(Tail, Del, Rest) 233 ). 234 235 236/* nth0/3, nth1/3 are improved versions from 237 Martin Jansche <martin@pc03.idf.uni-heidelberg.de> 238*/
249nth0(Index, List, Elem) :- 250 ( integer(Index) 251 -> nth0_det(Index, List, Elem) % take nth deterministically 252 ; var(Index) 253 -> List = [H|T], 254 nth_gen(T, Elem, H, 0, Index) % match 255 ; must_be(integer, Index) 256 ). 257 258nth0_det(0, [Elem|_], Elem) :- !. 259nth0_det(1, [_,Elem|_], Elem) :- !. 260nth0_det(2, [_,_,Elem|_], Elem) :- !. 261nth0_det(3, [_,_,_,Elem|_], Elem) :- !. 262nth0_det(4, [_,_,_,_,Elem|_], Elem) :- !. 263nth0_det(5, [_,_,_,_,_,Elem|_], Elem) :- !. 264nth0_det(N, [_,_,_,_,_,_ |Tail], Elem) :- 265 M is N - 6, 266 M >= 0, 267 nth0_det(M, Tail, Elem). 268 269nth_gen(_, Elem, Elem, Base, Base). 270nth_gen([H|Tail], Elem, _, N, Base) :- 271 succ(N, M), 272 nth_gen(Tail, Elem, H, M, Base).
282nth1(Index, List, Elem) :-
283 ( integer(Index)
284 -> Index0 is Index - 1,
285 nth0_det(Index0, List, Elem) % take nth deterministically
286 ; var(Index)
287 -> List = [H|T],
288 nth_gen(T, Elem, H, 1, Index) % match
289 ; must_be(integer, Index)
290 ).
?- 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].
311nth0(V, In, Element, Rest) :- 312 var(V), 313 !, 314 generate_nth(0, V, In, Element, Rest). 315nth0(V, In, Element, Rest) :- 316 must_be(nonneg, V), 317 find_nth0(V, In, Element, Rest).
323nth1(V, In, Element, Rest) :- 324 var(V), 325 !, 326 generate_nth(1, V, In, Element, Rest). 327nth1(V, In, Element, Rest) :- 328 must_be(positive_integer, V), 329 succ(V0, V), 330 find_nth0(V0, In, Element, Rest). 331 332generate_nth(I, I, [Head|Rest], Head, Rest). 333generate_nth(I, IN, [H|List], El, [H|Rest]) :- 334 I1 is I+1, 335 generate_nth(I1, IN, List, El, Rest). 336 337find_nth0(0, [Head|Rest], Head, Rest) :- !. 338find_nth0(N, [Head|Rest0], Elem, [Head|Rest]) :- 339 M is N-1, 340 find_nth0(M, Rest0, Elem, Rest).
semidet
if List is a list and multi
if List is
a partial list.
353last([X|Xs], Last) :- 354 last_(Xs, X, Last). 355 356last_([], Last, Last). 357last_([X|Xs], _, Last) :- 358 last_(Xs, X, Last).
proper_length(List, Length) :- is_list(List), length(List, Length).
372proper_length(List, Length) :-
373 '$skip_list'(Length0, List, Tail),
374 Tail == [],
375 Length = Length0.
387same_length([], []). 388same_length([_|T1], [_|T2]) :- 389 same_length(T1, T2).
397reverse(Xs, Ys) :- 398 reverse(Xs, [], Ys, Ys). 399 400reverse([], Ys, Ys, []). 401reverse([X|Xs], Rs, Ys, [_|Bound]) :- 402 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.
438permutation(Xs, Ys) :- 439 '$skip_list'(Xlen, Xs, XTail), 440 '$skip_list'(Ylen, Ys, YTail), 441 ( XTail == [], YTail == [] % both proper lists 442 -> Xlen == Ylen 443 ; var(XTail), YTail == [] % partial, proper 444 -> length(Xs, Ylen) 445 ; XTail == [], var(YTail) % proper, partial 446 -> length(Ys, Xlen) 447 ; var(XTail), var(YTail) % partial, partial 448 -> length(Xs, Len), 449 length(Ys, Len) 450 ; must_be(list, Xs), % either is not a list 451 must_be(list, Ys) 452 ), 453 perm(Xs, Ys). 454 455perm([], []). 456perm(List, [First|Perm]) :- 457 select(First, List, Rest), 458 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.
474flatten(List, FlatList) :- 475 flatten(List, [], FlatList0), 476 !, 477 FlatList = FlatList0. 478 479flatten(Var, Tl, [Var|Tl]) :- 480 var(Var), 481 !. 482flatten([], Tl, Tl) :- !. 483flatten([Hd|Tl], Tail, List) :- 484 !, 485 flatten(Hd, FlatHeadTail, List), 486 flatten(Tl, Tail, FlatHeadTail). 487flatten(NonList, Tl, [NonList|Tl]). 488 489 490 /******************************* 491 * ORDER OPERATIONS * 492 *******************************/
502max_member(Max, [H|T]) :- 503 max_member_(T, H, Max). 504 505max_member_([], Max, Max). 506max_member_([H|T], Max0, Max) :- 507 ( H @=< Max0 508 -> max_member_(T, Max0, Max) 509 ; max_member_(T, H, Max) 510 ).
521min_member(Min, [H|T]) :- 522 min_member_(T, H, Min). 523 524min_member_([], Min, Min). 525min_member_([H|T], Min0, Min) :- 526 ( H @>= Min0 527 -> min_member_(T, Min0, Min) 528 ; min_member_(T, H, Min) 529 ). 530 531 532 /******************************* 533 * LISTS OF NUMBERS * 534 *******************************/
540sum_list(Xs, Sum) :- 541 sum_list(Xs, 0, Sum). 542 543sum_list([], Sum, Sum). 544sum_list([X|Xs], Sum0, Sum) :- 545 Sum1 is Sum0 + X, 546 sum_list(Xs, Sum1, Sum).
555max_list([H|T], Max) :- 556 max_list(T, H, Max). 557 558max_list([], Max, Max). 559max_list([H|T], Max0, Max) :- 560 Max1 is max(H, Max0), 561 max_list(T, Max1, Max).
571min_list([H|T], Min) :- 572 min_list(T, H, Min). 573 574min_list([], Min, Min). 575min_list([H|T], Min0, Min) :- 576 Min1 is min(H, Min0), 577 min_list(T, Min1, Min).
587numlist(L, U, Ns) :- 588 must_be(integer, L), 589 must_be(integer, U), 590 L =< U, 591 numlist_(L, U, Ns). 592 593numlist_(U, U, List) :- 594 !, 595 List = [U]. 596numlist_(L, U, [L|Ns]) :- 597 L2 is L+1, 598 numlist_(L2, U, Ns). 599 600 601 /******************************** 602 * SET MANIPULATION * 603 *********************************/
log(N)
and the predicate may cause a
resource-error. There are no other error conditions. 612is_set(Set) :-
613 '$skip_list'(Len, Set, Tail),
614 Tail == [], % Proper list
615 sort(Set, Sorted),
616 length(Sorted, Len).
log(N)
.
636list_to_set(List, Set) :- 637 must_be(list, List), 638 number_list(List, 1, Numbered), 639 sort(1, @=<, Numbered, ONum), 640 remove_dup_keys(ONum, NumSet), 641 sort(2, @=<, NumSet, ONumSet), 642 pairs_keys(ONumSet, Set). 643 644number_list([], _, []). 645number_list([H|T0], N, [H-N|T]) :- 646 N1 is N+1, 647 number_list(T0, N1, T). 648 649remove_dup_keys([], []). 650remove_dup_keys([H|T0], [H|T]) :- 651 H = V-_, 652 remove_same_key(T0, V, T1), 653 remove_dup_keys(T1, T). 654 655remove_same_key([V1-_|T0], V, T) :- 656 V1 == V, 657 !, 658 remove_same_key(T0, V, T). 659remove_same_key(L, _, L).
671intersection([], _, []) :- !. 672intersection([X|T], L, Intersect) :- 673 memberchk(X, L), 674 !, 675 Intersect = [X|R], 676 intersection(T, L, R). 677intersection([_|T], L, R) :- 678 intersection(T, L, R).
690union([], L, L) :- !. 691union([H|T], L, R) :- 692 memberchk(H, L), 693 !, 694 union(T, L, R). 695union([H|T], L, [H|R]) :- 696 union(T, L, R).
708subset([], _) :- !. 709subset([E|R], Set) :- 710 memberchk(E, Set), 711 subset(R, Set).
723subtract([], _, []) :- !. 724subtract([E|T], D, R) :- 725 memberchk(E, D), 726 !, 727 subtract(T, D, R). 728subtract([H|T], D, [H|R]) :- 729 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.