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:- autoload(library(error),[must_be/2]). 77:- autoload(library(pairs),[pairs_keys/2]). 78 79 80:- set_prolog_flag(generate_debug_info, false).
member(X, [One]).
112member(El, [H|T]) :- 113 member_(T, El, H). 114 115member_(_, El, El). 116member_([H|T], El, _) :- 117 member_(T, El, H).
123append([], L, L). 124append([H|T], L, [H|R]) :- 125 append(T, L, R).
134append(ListOfLists, List) :- 135 must_be(list, ListOfLists), 136 append_(ListOfLists, List). 137 138append_([], []). 139append_([L|Ls], As) :- 140 append(L, Ws, As), 141 append_(Ls, Ws).
append(Part, _, Whole)
.149prefix([], _). 150prefix([E|T0], [E|T]) :- 151 prefix(T0, T).
160select(X, [Head|Tail], Rest) :- 161 select3_(Tail, Head, X, Rest). 162 163select3_(Tail, Head, Head, Tail). 164select3_([Head2|Tail], Head, X, [Head|Rest]) :- 165 select3_(Tail, Head2, X, Rest).
173selectchk(Elem, List, Rest) :-
174 select(Elem, List, Rest0),
175 !,
176 Rest = Rest0.
?- select(b, [a,b,c,b], 2, X). X = [a, 2, c, b] ; X = [a, b, c, 2] ; false.
197select(X, XList, Y, YList) :- 198 select4_(XList, X, Y, YList). 199 200select4_([X|List], X, Y, [Y|List]). 201select4_([X0|XList], X, Y, [X0|YList]) :- 202 select4_(XList, X, Y, YList).
208selectchk(X, XList, Y, YList) :-
209 select(X, XList, Y, YList),
210 !.
216nextto(X, Y, [X,Y|_]). 217nextto(X, Y, [_|Zs]) :- 218 nextto(X, Y, Zs).
\+ Elem \=
H
, which implies that Elem is not changed.
233delete([], _, []). 234delete([Elem|Tail], Del, Result) :- 235 ( \+ Elem \= Del 236 -> delete(Tail, Del, Result) 237 ; Result = [Elem|Rest], 238 delete(Tail, Del, Rest) 239 ). 240 241 242/* nth0/3, nth1/3 are improved versions from 243 Martin Jansche <martin@pc03.idf.uni-heidelberg.de> 244*/
255nth0(Index, List, Elem) :- 256 ( integer(Index) 257 -> nth0_det(Index, List, Elem) % take nth deterministically 258 ; var(Index) 259 -> List = [H|T], 260 nth_gen(T, Elem, H, 0, Index) % match 261 ; must_be(integer, Index) 262 ). 263 264nth0_det(0, [Elem|_], Elem) :- !. 265nth0_det(1, [_,Elem|_], Elem) :- !. 266nth0_det(2, [_,_,Elem|_], Elem) :- !. 267nth0_det(3, [_,_,_,Elem|_], Elem) :- !. 268nth0_det(4, [_,_,_,_,Elem|_], Elem) :- !. 269nth0_det(5, [_,_,_,_,_,Elem|_], Elem) :- !. 270nth0_det(N, [_,_,_,_,_,_ |Tail], Elem) :- 271 M is N - 6, 272 M >= 0, 273 nth0_det(M, Tail, Elem). 274 275nth_gen(_, Elem, Elem, Base, Base). 276nth_gen([H|Tail], Elem, _, N, Base) :- 277 succ(N, M), 278 nth_gen(Tail, Elem, H, M, Base).
288nth1(Index, List, Elem) :-
289 ( integer(Index)
290 -> Index0 is Index - 1,
291 nth0_det(Index0, List, Elem) % take nth deterministically
292 ; var(Index)
293 -> List = [H|T],
294 nth_gen(T, Elem, H, 1, Index) % match
295 ; must_be(integer, Index)
296 ).
?- 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].
317nth0(V, In, Element, Rest) :- 318 var(V), 319 !, 320 generate_nth(0, V, In, Element, Rest). 321nth0(V, In, Element, Rest) :- 322 must_be(nonneg, V), 323 find_nth0(V, In, Element, Rest).
329nth1(V, In, Element, Rest) :- 330 var(V), 331 !, 332 generate_nth(1, V, In, Element, Rest). 333nth1(V, In, Element, Rest) :- 334 must_be(positive_integer, V), 335 succ(V0, V), 336 find_nth0(V0, In, Element, Rest). 337 338generate_nth(I, I, [Head|Rest], Head, Rest). 339generate_nth(I, IN, [H|List], El, [H|Rest]) :- 340 I1 is I+1, 341 generate_nth(I1, IN, List, El, Rest). 342 343find_nth0(0, [Head|Rest], Head, Rest) :- !. 344find_nth0(N, [Head|Rest0], Elem, [Head|Rest]) :- 345 M is N-1, 346 find_nth0(M, Rest0, Elem, Rest).
semidet
if List is a list and multi
if List is
a partial list.
359last([X|Xs], Last) :- 360 last_(Xs, X, Last). 361 362last_([], Last, Last). 363last_([X|Xs], _, Last) :- 364 last_(Xs, X, Last).
proper_length(List, Length) :- is_list(List), length(List, Length).
378proper_length(List, Length) :-
379 '$skip_list'(Length0, List, Tail),
380 Tail == [],
381 Length = Length0.
393same_length([], []). 394same_length([_|T1], [_|T2]) :- 395 same_length(T1, T2).
403reverse(Xs, Ys) :- 404 reverse(Xs, [], Ys, Ys). 405 406reverse([], Ys, Ys, []). 407reverse([X|Xs], Rs, Ys, [_|Bound]) :- 408 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.
444permutation(Xs, Ys) :- 445 '$skip_list'(Xlen, Xs, XTail), 446 '$skip_list'(Ylen, Ys, YTail), 447 ( XTail == [], YTail == [] % both proper lists 448 -> Xlen == Ylen 449 ; var(XTail), YTail == [] % partial, proper 450 -> length(Xs, Ylen) 451 ; XTail == [], var(YTail) % proper, partial 452 -> length(Ys, Xlen) 453 ; var(XTail), var(YTail) % partial, partial 454 -> length(Xs, Len), 455 length(Ys, Len) 456 ; must_be(list, Xs), % either is not a list 457 must_be(list, Ys) 458 ), 459 perm(Xs, Ys). 460 461perm([], []). 462perm(List, [First|Perm]) :- 463 select(First, List, Rest), 464 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.
480flatten(List, FlatList) :- 481 flatten(List, [], FlatList0), 482 !, 483 FlatList = FlatList0. 484 485flatten(Var, Tl, [Var|Tl]) :- 486 var(Var), 487 !. 488flatten([], Tl, Tl) :- !. 489flatten([Hd|Tl], Tail, List) :- 490 !, 491 flatten(Hd, FlatHeadTail, List), 492 flatten(Tl, Tail, FlatHeadTail). 493flatten(NonList, Tl, [NonList|Tl]). 494 495 496 /******************************* 497 * ORDER OPERATIONS * 498 *******************************/
508max_member(Max, [H|T]) :- 509 max_member_(T, H, Max). 510 511max_member_([], Max, Max). 512max_member_([H|T], Max0, Max) :- 513 ( H @=< Max0 514 -> max_member_(T, Max0, Max) 515 ; max_member_(T, H, Max) 516 ).
527min_member(Min, [H|T]) :- 528 min_member_(T, H, Min). 529 530min_member_([], Min, Min). 531min_member_([H|T], Min0, Min) :- 532 ( H @>= Min0 533 -> min_member_(T, Min0, Min) 534 ; min_member_(T, H, Min) 535 ). 536 537 538 /******************************* 539 * LISTS OF NUMBERS * 540 *******************************/
546sum_list(Xs, Sum) :- 547 sum_list(Xs, 0, Sum). 548 549sum_list([], Sum, Sum). 550sum_list([X|Xs], Sum0, Sum) :- 551 Sum1 is Sum0 + X, 552 sum_list(Xs, Sum1, Sum).
561max_list([H|T], Max) :- 562 max_list(T, H, Max). 563 564max_list([], Max, Max). 565max_list([H|T], Max0, Max) :- 566 Max1 is max(H, Max0), 567 max_list(T, Max1, Max).
577min_list([H|T], Min) :- 578 min_list(T, H, Min). 579 580min_list([], Min, Min). 581min_list([H|T], Min0, Min) :- 582 Min1 is min(H, Min0), 583 min_list(T, Min1, Min).
593numlist(L, U, Ns) :- 594 must_be(integer, L), 595 must_be(integer, U), 596 L =< U, 597 numlist_(L, U, Ns). 598 599numlist_(U, U, List) :- 600 !, 601 List = [U]. 602numlist_(L, U, [L|Ns]) :- 603 L2 is L+1, 604 numlist_(L2, U, Ns). 605 606 607 /******************************** 608 * SET MANIPULATION * 609 *********************************/
log(N)
and the predicate may cause a
resource-error. There are no other error conditions. 618is_set(Set) :-
619 '$skip_list'(Len, Set, Tail),
620 Tail == [], % Proper list
621 sort(Set, Sorted),
622 length(Sorted, Len).
log(N)
.
642list_to_set(List, Set) :- 643 must_be(list, List), 644 number_list(List, 1, Numbered), 645 sort(1, @=<, Numbered, ONum), 646 remove_dup_keys(ONum, NumSet), 647 sort(2, @=<, NumSet, ONumSet), 648 pairs_keys(ONumSet, Set). 649 650number_list([], _, []). 651number_list([H|T0], N, [H-N|T]) :- 652 N1 is N+1, 653 number_list(T0, N1, T). 654 655remove_dup_keys([], []). 656remove_dup_keys([H|T0], [H|T]) :- 657 H = V-_, 658 remove_same_key(T0, V, T1), 659 remove_dup_keys(T1, T). 660 661remove_same_key([V1-_|T0], V, T) :- 662 V1 == V, 663 !, 664 remove_same_key(T0, V, T). 665remove_same_key(L, _, L).
677intersection([], _, []) :- !. 678intersection([X|T], L, Intersect) :- 679 memberchk(X, L), 680 !, 681 Intersect = [X|R], 682 intersection(T, L, R). 683intersection([_|T], L, R) :- 684 intersection(T, L, R).
696union([], L, L) :- !. 697union([H|T], L, R) :- 698 memberchk(H, L), 699 !, 700 union(T, L, R). 701union([H|T], L, [H|R]) :- 702 union(T, L, R).
714subset([], _) :- !. 715subset([E|R], Set) :- 716 memberchk(E, Set), 717 subset(R, Set).
729subtract([], _, []) :- !. 730subtract([E|T], D, R) :- 731 memberchk(E, D), 732 !, 733 subtract(T, D, R). 734subtract([H|T], D, [H|R]) :- 735 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.