## A.12 library(lists): 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.

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
append(?List1, ?List2, ?List1AndList2)
  List1AndList2 is the concatination of List1 and List2
append(+ListOfLists, ?List)
  Concatenate a list of lists. Is true if Lists is a list of lists, and List is the concatenation of these lists.

  ListOfLists | must be a list of -possibly- partial lists

prefix(?Part, ?Whole)
  True iff Part is a leading substring of Whole. This is the same as append(Part, _, Whole).
select(?Elem, ?List1, ?List2)
  Is true when List1, with Elem removed results in List2.
[semidet]selectchk(+Elem, +List, -Rest)
  Semi-deterministic removal of first element in List that unifies Elem.
[nondet]select(?X, ?XList, ?Y, ?YList)
  Is true when select(X, XList) and select(Y, YList) are true, X and Y appear in the same locations of their respective lists and same_length(XList, YList) is true. A typical use for this predicate is to replace an element:

      ?- select(b, [a,b,c], 2, X).
      X = [a, 2, c] ;
      X = [a, b, c].

[semidet]selectchk(X, XList, Y, YList)
  Semi-deterministic version of select/4.
nextto(?X, ?Y, ?List)
  True of Y follows X in List.
delete(?List1, ?Elem, ?List2)
  Is true when Lis1, with all occurences of Elem deleted results in List2.
  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.
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.
nth1(?Index, ?List, ?Elem)
  Is true when Elem is the Index'th element of List. Counting starts at 1.
  See also
    nth0/3.
last(?List, ?Last)
  Succeeds if `Last' unifies with the last element of `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.
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
reverse(?List1, ?List2)
  Is true when the elements of List2 are in reverse order compared to List1.
[nondet]permutation(?Xs, ?Ys)
  permutation(Xs, Ys) is 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 illustrate 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.
[det]flatten(+List1, ?List2)
  Is true it List2 is a non nested version of List1.
  See also
    append/2
  deprecated
    Ending up needing flatten/3 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.
[det]sumlist(+List, -Sum)
  Sum is the result of adding all numbers in List.
[det]max_list(+List:list(number), -Max:number)
  True if Max is the largest number in List.
[det]min_list(+List:list(number), -Min:number)
  True if Min is the largest number in List.
[semidet]numlist(+Low, +High, -List)
  List is a list [Low, Low+1, ... High]. Fails if High < Low.
  Errors
    - type_error(integer, Low)
    - type_error(integer, High)
[det]is_set(@Set)
  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.
[det]list_to_set(+List, ?Set)
  True when Set has the same element as List in the same order. The left-most copy of the duplicate is retained. The complexity of this operation is `|`List`|``^`2.
  See also
    sort/2.
[det]intersection(+Set1, +Set2, -Set3)
  True if Set3 unifies with the intersection of Set1 and Set2. The complexity of this predicate is `|`Set1`|`*`|`Set2`|`
  See also
    ord_intersection/3.
[det]union(+Set1, +Set2, -Set3)
  True if Set3 unifies with the union of Set1 and Set2. The complexity of this predicate is `|`Set1`|`*`|`Set2`|`
  See also
    ord_union/3.
[semidet]subset(+SubSet, +Set)
  True if all elements of SubSet belong to Set as well. Membership test is based on memberchk/2. The complexity is `|`SubSet`|`*`|`Set`|`.
  See also
    ord_subset/2.
[det]subtract(+Set, +Delete, -Result)
  Delete all elements from `Set' that occur in `Delete' (a set) and unify the result with `Result'. Deletion is based on unification using memberchk/2. The complexity is `|`Delete`|`*`|`Set`|`.
  See also
    ord_subtract/3.