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 memberchk/2, % ?X, ?List 39 append/2, % +ListOfLists, -List 40 append/3, % ?A, ?B, ?AB 41 prefix/2, % ?Part, ?Whole 42 select/3, % ?X, ?List, ?Rest 43 selectchk/3, % ?X, ?List, ?Rest 44 select/4, % ?X, ?XList, ?Y, ?YList 45 selectchk/4, % ?X, ?XList, ?Y, ?YList 46 nextto/3, % ?X, ?Y, ?List 47 delete/3, % ?List, ?X, ?Rest 48 nth0/3, % ?N, ?List, ?Elem 49 nth1/3, % ?N, ?List, ?Elem 50 nth0/4, % ?N, ?List, ?Elem, ?Rest 51 nth1/4, % ?N, ?List, ?Elem, ?Rest 52 last/2, % +List, -Element 53 proper_length/2, % @List, -Length 54 same_length/2, % ?List1, ?List2 55 reverse/2, % +List, -Reversed 56 permutation/2, % ?List, ?Permutation 57 flatten/2, % +Nested, -Flat 58 59 % Ordered operations 60 max_member/2, % -Max, +List 61 min_member/2, % -Min, +List 62 63 % Lists of numbers 64 sum_list/2, % +List, -Sum 65 max_list/2, % +List, -Max 66 min_list/2, % +List, -Min 67 numlist/3, % +Low, +High, -List 68 69 % set manipulation 70 is_set/1, % +List 71 list_to_set/2, % +List, -Set 72 intersection/3, % +List1, +List2, -Intersection 73 union/3, % +List1, +List2, -Union 74 subset/2, % +SubSet, +Set 75 subtract/3 % +Set, +Delete, -Remaining 76 ]). 77:- autoload(library(error),[must_be/2]). 78:- autoload(library(pairs),[pairs_keys/2]). 79 80 81:- set_prolog_flag(generate_debug_info, false).
member(X, [One]).
113member(El, [H|T]) :- 114 member_(T, El, H). 115 116member_(_, El, El). 117member_([H|T], El, _) :- 118 member_(T, El, H).
124append([], L, L). 125append([H|T], L, [H|R]) :- 126 append(T, L, R).
135append(ListOfLists, List) :- 136 must_be(list, ListOfLists), 137 append_(ListOfLists, List). 138 139append_([], []). 140append_([L|Ls], As) :- 141 append(L, Ws, As), 142 append_(Ls, Ws).
append(Part, _, Whole)
.150prefix([], _). 151prefix([E|T0], [E|T]) :- 152 prefix(T0, T).
161select(X, [Head|Tail], Rest) :- 162 select3_(Tail, Head, X, Rest). 163 164select3_(Tail, Head, Head, Tail). 165select3_([Head2|Tail], Head, X, [Head|Rest]) :- 166 select3_(Tail, Head2, X, Rest).
174selectchk(Elem, List, Rest) :-
175 select(Elem, List, Rest0),
176 !,
177 Rest = Rest0.
?- select(b, [a,b,c,b], 2, X). X = [a, 2, c, b] ; X = [a, b, c, 2] ; false.
198select(X, XList, Y, YList) :- 199 select4_(XList, X, Y, YList). 200 201select4_([X|List], X, Y, [Y|List]). 202select4_([X0|XList], X, Y, [X0|YList]) :- 203 select4_(XList, X, Y, YList).
209selectchk(X, XList, Y, YList) :-
210 select(X, XList, Y, YList),
211 !.
217nextto(X, Y, [X,Y|_]). 218nextto(X, Y, [_|Zs]) :- 219 nextto(X, Y, Zs).
\+ Elem \=
H
, which implies that Elem is not changed.
234delete([], _, []). 235delete([Elem|Tail], Del, Result) :- 236 ( \+ Elem \= Del 237 -> delete(Tail, Del, Result) 238 ; Result = [Elem|Rest], 239 delete(Tail, Del, Rest) 240 ). 241 242 243/* nth0/3, nth1/3 are improved versions from 244 Martin Jansche <martin@pc03.idf.uni-heidelberg.de> 245*/
256nth0(Index, List, Elem) :- 257 ( integer(Index) 258 -> nth0_det(Index, List, Elem) % take nth deterministically 259 ; var(Index) 260 -> List = [H|T], 261 nth_gen(T, Elem, H, 0, Index) % match 262 ; must_be(integer, Index) 263 ). 264 265nth0_det(0, [Elem|_], Elem) :- !. 266nth0_det(1, [_,Elem|_], Elem) :- !. 267nth0_det(2, [_,_,Elem|_], Elem) :- !. 268nth0_det(3, [_,_,_,Elem|_], Elem) :- !. 269nth0_det(4, [_,_,_,_,Elem|_], Elem) :- !. 270nth0_det(5, [_,_,_,_,_,Elem|_], Elem) :- !. 271nth0_det(N, [_,_,_,_,_,_ |Tail], Elem) :- 272 M is N - 6, 273 M >= 0, 274 nth0_det(M, Tail, Elem). 275 276nth_gen(_, Elem, Elem, Base, Base). 277nth_gen([H|Tail], Elem, _, N, Base) :- 278 succ(N, M), 279 nth_gen(Tail, Elem, H, M, Base).
289nth1(Index, List, Elem) :-
290 ( integer(Index)
291 -> Index0 is Index - 1,
292 nth0_det(Index0, List, Elem) % take nth deterministically
293 ; var(Index)
294 -> List = [H|T],
295 nth_gen(T, Elem, H, 1, Index) % match
296 ; must_be(integer, Index)
297 ).
?- 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].
318nth0(V, In, Element, Rest) :- 319 var(V), 320 !, 321 generate_nth(0, V, In, Element, Rest). 322nth0(V, In, Element, Rest) :- 323 must_be(nonneg, V), 324 find_nth0(V, In, Element, Rest).
330nth1(V, In, Element, Rest) :- 331 var(V), 332 !, 333 generate_nth(1, V, In, Element, Rest). 334nth1(V, In, Element, Rest) :- 335 must_be(positive_integer, V), 336 succ(V0, V), 337 find_nth0(V0, In, Element, Rest). 338 339generate_nth(I, I, [Head|Rest], Head, Rest). 340generate_nth(I, IN, [H|List], El, [H|Rest]) :- 341 I1 is I+1, 342 generate_nth(I1, IN, List, El, Rest). 343 344find_nth0(0, [Head|Rest], Head, Rest) :- !. 345find_nth0(N, [Head|Rest0], Elem, [Head|Rest]) :- 346 M is N-1, 347 find_nth0(M, Rest0, Elem, Rest).
semidet
if List is a list and multi
if List is
a partial list.
360last([X|Xs], Last) :- 361 last_(Xs, X, Last). 362 363last_([], Last, Last). 364last_([X|Xs], _, Last) :- 365 last_(Xs, X, Last).
proper_length(List, Length) :- is_list(List), length(List, Length).
379proper_length(List, Length) :-
380 '$skip_list'(Length0, List, Tail),
381 Tail == [],
382 Length = Length0.
394same_length([], []). 395same_length([_|T1], [_|T2]) :- 396 same_length(T1, T2).
404reverse(Xs, Ys) :- 405 reverse(Xs, [], Ys, Ys). 406 407reverse([], Ys, Ys, []). 408reverse([X|Xs], Rs, Ys, [_|Bound]) :- 409 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.
445permutation(Xs, Ys) :- 446 '$skip_list'(Xlen, Xs, XTail), 447 '$skip_list'(Ylen, Ys, YTail), 448 ( XTail == [], YTail == [] % both proper lists 449 -> Xlen == Ylen 450 ; var(XTail), YTail == [] % partial, proper 451 -> length(Xs, Ylen) 452 ; XTail == [], var(YTail) % proper, partial 453 -> length(Ys, Xlen) 454 ; var(XTail), var(YTail) % partial, partial 455 -> length(Xs, Len), 456 length(Ys, Len) 457 ; must_be(list, Xs), % either is not a list 458 must_be(list, Ys) 459 ), 460 perm(Xs, Ys). 461 462perm([], []). 463perm(List, [First|Perm]) :- 464 select(First, List, Rest), 465 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.
481flatten(List, FlatList) :- 482 flatten(List, [], FlatList0), 483 !, 484 FlatList = FlatList0. 485 486flatten(Var, Tl, [Var|Tl]) :- 487 var(Var), 488 !. 489flatten([], Tl, Tl) :- !. 490flatten([Hd|Tl], Tail, List) :- 491 !, 492 flatten(Hd, FlatHeadTail, List), 493 flatten(Tl, Tail, FlatHeadTail). 494flatten(NonList, Tl, [NonList|Tl]). 495 496 497 /******************************* 498 * ORDER OPERATIONS * 499 *******************************/
509max_member(Max, [H|T]) :- 510 max_member_(T, H, Max). 511 512max_member_([], Max, Max). 513max_member_([H|T], Max0, Max) :- 514 ( H @=< Max0 515 -> max_member_(T, Max0, Max) 516 ; max_member_(T, H, Max) 517 ).
528min_member(Min, [H|T]) :- 529 min_member_(T, H, Min). 530 531min_member_([], Min, Min). 532min_member_([H|T], Min0, Min) :- 533 ( H @>= Min0 534 -> min_member_(T, Min0, Min) 535 ; min_member_(T, H, Min) 536 ). 537 538 539 /******************************* 540 * LISTS OF NUMBERS * 541 *******************************/
547sum_list(Xs, Sum) :- 548 sum_list(Xs, 0, Sum). 549 550sum_list([], Sum, Sum). 551sum_list([X|Xs], Sum0, Sum) :- 552 Sum1 is Sum0 + X, 553 sum_list(Xs, Sum1, Sum).
562max_list([H|T], Max) :- 563 max_list(T, H, Max). 564 565max_list([], Max, Max). 566max_list([H|T], Max0, Max) :- 567 Max1 is max(H, Max0), 568 max_list(T, Max1, Max).
578min_list([H|T], Min) :- 579 min_list(T, H, Min). 580 581min_list([], Min, Min). 582min_list([H|T], Min0, Min) :- 583 Min1 is min(H, Min0), 584 min_list(T, Min1, Min).
594numlist(L, U, Ns) :- 595 must_be(integer, L), 596 must_be(integer, U), 597 L =< U, 598 numlist_(L, U, Ns). 599 600numlist_(U, U, List) :- 601 !, 602 List = [U]. 603numlist_(L, U, [L|Ns]) :- 604 L2 is L+1, 605 numlist_(L2, U, Ns). 606 607 608 /******************************** 609 * SET MANIPULATION * 610 *********************************/
log(N)
and the predicate may cause a
resource-error. There are no other error conditions. 619is_set(Set) :-
620 '$skip_list'(Len, Set, Tail),
621 Tail == [], % Proper list
622 sort(Set, Sorted),
623 length(Sorted, Len).
log(N)
.
643list_to_set(List, Set) :- 644 must_be(list, List), 645 number_list(List, 1, Numbered), 646 sort(1, @=<, Numbered, ONum), 647 remove_dup_keys(ONum, NumSet), 648 sort(2, @=<, NumSet, ONumSet), 649 pairs_keys(ONumSet, Set). 650 651number_list([], _, []). 652number_list([H|T0], N, [H-N|T]) :- 653 N1 is N+1, 654 number_list(T0, N1, T). 655 656remove_dup_keys([], []). 657remove_dup_keys([H|T0], [H|T]) :- 658 H = V-_, 659 remove_same_key(T0, V, T1), 660 remove_dup_keys(T1, T). 661 662remove_same_key([V1-_|T0], V, T) :- 663 V1 == V, 664 !, 665 remove_same_key(T0, V, T). 666remove_same_key(L, _, L).
678intersection([], _, []) :- !. 679intersection([X|T], L, Intersect) :- 680 memberchk(X, L), 681 !, 682 Intersect = [X|R], 683 intersection(T, L, R). 684intersection([_|T], L, R) :- 685 intersection(T, L, R).
697union([], L, L) :- !. 698union([H|T], L, R) :- 699 memberchk(H, L), 700 !, 701 union(T, L, R). 702union([H|T], L, [H|R]) :- 703 union(T, L, R).
715subset([], _) :- !. 716subset([E|R], Set) :- 717 memberchk(E, Set), 718 subset(R, Set).
730subtract([], _, []) :- !. 731subtract([E|T], D, R) :- 732 memberchk(E, D), 733 !, 734 subtract(T, D, R). 735subtract([H|T], D, [H|R]) :- 736 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.