lists.pl -- 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.
- 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]). - append(?List1, ?List2, ?List1AndList2)
- List1AndList2 is the concatenation of List1 and List2
- 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.
- 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.
- selectchk(+Elem, +List, -Rest) is semidet
- Semi-deterministic removal of first element in List that unifies with Elem.
- select(?X, ?XList, ?Y, ?YList) is nondet
- 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].
- selectchk(?X, ?XList, ?Y, ?YList) is semidet
- Semi-deterministic version of select/4.
- nextto(?X, ?Y, ?List)
- True if Y follows X in List.
- delete(?List1, ?Elem, ?List2) is det
- Is true when List1, with all occurrences of Elem deleted, results in List2.
- nth0(?Index, ?List, ?Elem)
- True when Elem is the Index'th element of List. Counting starts at 0.
- nth1(?Index, ?List, ?Elem)
- Is true when Elem is the Index'th element of List. Counting starts at 1.
- 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].
- nth1(?N, ?List, ?Elem, ?Rest) is det
- As nth0/4, but counting starts at 1.
- last(?List, ?Last)
- Succeeds when Last is the last element of List. This
predicate is
semidetif List is a list andmultiif List is a partial list. - 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). - 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.
- reverse(?List1, ?List2)
- Is true when the elements of List2 are in reverse order compared to List1.
- 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
semidetpredicate 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.
- flatten(+List1, ?List2) is det
- Is true if List2 is a non-nested version of List1.
- max_member(-Max, +List) is semidet
- True when Max is the largest member in the standard order of terms. Fails if List is empty.
- min_member(-Min, +List) is semidet
- True when Min is the smallest member in the standard order of terms. Fails if List is empty.
- sum_list(+List, -Sum) is det
- Sum is the result of adding all numbers in List.
- max_list(+List:list(number), -Max:number) is semidet
- True if Max is the largest number in List. Fails if List is empty.
- min_list(+List:list(number), -Min:number) is semidet
- True if Min is the smallest number in List. Fails if List is empty.
- numlist(+Low, +High, -List) is semidet
- List is a list [Low, Low+1, ... High]. Fails if High < Low.
- is_set(@Set) is det
- 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.
- 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 the duplicate is retained. The complexity of this operation is |List|^2.
- 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|
- union(+Set1, +Set2, -Set3) is det
- True if Set3 unifies with the union of Set1 and Set2. The complexity of this predicate is |Set1|*|Set2|
- 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|.
- subtract(+Set, +Delete, -Result) is det
- 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|.