View source with raw comments or as raw
    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).

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.

Compatibility
- Virtually every Prolog system has library(lists), but the set of provided predicates is diverse. There is a fair agreement on the semantics of most of these predicates, although error handling may vary. */
 member(?Elem, ?List)
True if Elem is a member of List. The SWI-Prolog definition differs from the classical one. Our definition avoids unpacking each list element twice and provides determinism on the last element. E.g. this is deterministic:
    member(X, [One]).
author
- Gertjan van Noord
  113member(El, [H|T]) :-
  114    member_(T, El, H).
  115
  116member_(_, El, El).
  117member_([H|T], El, _) :-
  118    member_(T, El, H).
 append(?List1, ?List2, ?List1AndList2)
List1AndList2 is the concatenation of List1 and List2
  124append([], L, L).
  125append([H|T], L, [H|R]) :-
  126    append(T, L, R).
 append(+ListOfLists, ?List)
Concatenate a list of lists. Is true if ListOfLists is a list of lists, and List is the concatenation of these lists.
Arguments:
ListOfLists- must be a list of possibly partial lists
  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).
 prefix(?Part, ?Whole)
True iff Part is a leading substring of Whole. This is the same as append(Part, _, Whole).
  150prefix([], _).
  151prefix([E|T0], [E|T]) :-
  152    prefix(T0, T).
 select(?Elem, ?List1, ?List2)
Is true when List1, with Elem removed, results in List2. This implementation is determinsitic if the last element of List1 has been selected.
  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).
 selectchk(+Elem, +List, -Rest) is semidet
Semi-deterministic removal of first element in List that unifies with Elem.
  174selectchk(Elem, List, Rest) :-
  175    select(Elem, List, Rest0),
  176    !,
  177    Rest = Rest0.
 select(?X, ?XList, ?Y, ?YList) is nondet
Select from two lists at the same positon. True if XList is unifiable with YList apart a single element at the same position that is unified with X in XList and with Y in YList. A typical use for this predicate is to replace an element, as shown in the example below. All possible substitutions are performed on backtracking.
?- select(b, [a,b,c,b], 2, X).
X = [a, 2, c, b] ;
X = [a, b, c, 2] ;
false.
See also
- selectchk/4 provides a semidet version.
  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).
 selectchk(?X, ?XList, ?Y, ?YList) is semidet
Semi-deterministic version of select/4.
  209selectchk(X, XList, Y, YList) :-
  210    select(X, XList, Y, YList),
  211    !.
 nextto(?X, ?Y, ?List)
True if Y directly follows X in List.
  217nextto(X, Y, [X,Y|_]).
  218nextto(X, Y, [_|Zs]) :-
  219    nextto(X, Y, Zs).
 delete(+List1, @Elem, -List2) is det
Delete matching elements from a list. True when List2 is a list with all elements from List1 except for those that unify with Elem. Matching Elem with elements of List1 is uses \+ Elem \= H, which implies that Elem is not changed.
See also
- select/3, subtract/3.
deprecated
- There are too many ways in which one might want to delete elements from a list to justify the name. Think of matching (= vs. ==), delete first/all, be deterministic or not.
  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*/
 nth0(?Index, ?List, ?Elem)
True when Elem is the Index'th element of List. Counting starts at 0.
Errors
- type_error(integer, Index) if Index is not an integer or unbound.
See also
- nth1/3.
  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).
 nth1(?Index, ?List, ?Elem)
Is true when Elem is the Index'th element of List. Counting starts at 1.
See also
- nth0/3.
  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(?N, ?List, ?Elem, ?Rest) is det
Select/insert element at index. True when Elem is the N'th (0-based) element of List and Rest is the remainder (as in by select/3) of List. For example:
?- 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).
 nth1(?N, ?List, ?Elem, ?Rest) is det
As nth0/4, but counting starts at 1.
  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).
 last(?List, ?Last)
Succeeds when Last is the last element of List. This predicate is semidet if List is a list and multi if List is a partial list.
Compatibility
- There is no de-facto standard for the argument order of last/2. Be careful when porting code or use append(_, [Last], List) as a portable alternative.
  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 semidet
True when Length is the number of elements in the proper list List. This is equivalent to
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.
 same_length(?List1, ?List2)
Is true when List1 and List2 are lists with the same number of elements. The predicate is deterministic if at least one of the arguments is a proper list. It is non-deterministic if both arguments are partial lists.
See also
- length/2
  394same_length([], []).
  395same_length([_|T1], [_|T2]) :-
  396    same_length(T1, T2).
 reverse(?List1, ?List2)
Is true when the elements of List2 are in reverse order compared to List1.
  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).
 permutation(?Xs, ?Ys) is nondet
True when Xs is a permutation of Ys. This can solve for Ys given Xs or Xs given Ys, or even enumerate Xs and Ys together. The predicate permutation/2 is primarily intended to generate permutations. Note that a list of length N has N! permutations, and unbounded permutation generation becomes prohibitively expensive, even for rather short lists (10! = 3,628,800).

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.
Errors
- type_error(list, Arg) if either argument is not a proper or partial list.
  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).
 flatten(+NestedList, -FlatList) is det
Is true if FlatList is a non-nested version of NestedList. Note that empty lists are removed. In standard Prolog, this implies that the atom '[]' is removed too. In SWI7, [] 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.

See also
- append/2
  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                 *******************************/
 max_member(-Max, +List) is semidet
True when Max is the largest member in the standard order of terms. Fails if List is empty.
See also
- compare/3
- max_list/2 for the maximum of a list of numbers.
  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    ).
 min_member(-Min, +List) is semidet
True when Min is the smallest member in the standard order of terms. Fails if List is empty.
See also
- compare/3
- min_list/2 for the minimum of a list of numbers.
  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                 *******************************/
 sum_list(+List, -Sum) is det
Sum is the result of adding all numbers in List.
  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).
 max_list(+List:list(number), -Max:number) is semidet
True if Max is the largest number in List. Fails if List is empty.
See also
- max_member/2.
  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).
 min_list(+List:list(number), -Min:number) is semidet
True if Min is the smallest number in List. Fails if List is empty.
See also
- min_member/2.
  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).
 numlist(+Low, +High, -List) is semidet
List is a list [Low, Low+1, ... High]. Fails if High < Low.
Errors
- type_error(integer, Low)
- type_error(integer, High)
  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                *********************************/
 is_set(@Set) is semidet
True if Set is a proper list without duplicates. Equivalence is based on ==/2. The implementation uses sort/2, which implies that the complexity is N*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).
 list_to_set(+List, ?Set) is det
True when Set has the same elements as List in the same order. The left-most copy of duplicate elements is retained. List may contain variables. Elements E1 and E2 are considered duplicates iff E1 == E2 holds. The complexity of the implementation is N*log(N).
Errors
- List is type-checked.
See also
- sort/2 can be used to create an ordered set. Many set operations on ordered sets are order N rather than order N**2. The list_to_set/2 predicate is more expensive than sort/2 because it involves, two sorts and a linear scan.
Compatibility
- Up to version 6.3.11, list_to_set/2 had complexity N**2 and equality was tested using =/2.
  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).
 intersection(+Set1, +Set2, -Set3) is det
True if Set3 unifies with the intersection of Set1 and Set2. The complexity of this predicate is |Set1|*|Set2|. A set is defined to be an unordered list without duplicates. Elements are considered duplicates if they can be unified.
See also
- ord_intersection/3.
  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).
 union(+Set1, +Set2, -Set3) is det
True if Set3 unifies with the union of the lists Set1 and Set2. The complexity of this predicate is |Set1|*|Set2|. A set is defined to be an unordered list without duplicates. Elements are considered duplicates if they can be unified.
See also
- ord_union/3
  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).
 subset(+SubSet, +Set) is semidet
True if all elements of SubSet belong to Set as well. Membership test is based on memberchk/2. The complexity is |SubSet|*|Set|. A set is defined to be an unordered list without duplicates. Elements are considered duplicates if they can be unified.
See also
- ord_subset/2.
  715subset([], _) :- !.
  716subset([E|R], Set) :-
  717    memberchk(E, Set),
  718    subset(R, Set).
 subtract(+Set, +Delete, -Result) is det
Delete all elements in Delete from Set. Deletion is based on unification using memberchk/2. The complexity is |Delete|*|Set|. A set is defined to be an unordered list without duplicates. Elements are considered duplicates if they can be unified.
See also
- ord_subtract/3.
  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)