List Processing

The XSB library contains various list utilities, some of which are listed below. These predicates should be explicitly imported from the module specified after the skeletal specification of each predicate. There are a lot more useful list processing predicates in various modules of the XSB system, and the interested user can find them by looking at the sources.

append(?List1, ?List2, ?List3)

basics
Succeeds if list List3 is the concatenation of lists List1 and List2.

member(?Element, ?List)

basics
Checks whether Element unifies with any element of list List, succeeding more than once if there are multiple such elements.

memberchk(?Element, ?List)

basics
Similar to member/2, except that memberchk/2 is deterministic, i.e. does not succeed more than once for any call.

ith(?Index, ?List, ?Element)

basics
Succeeds if the ${\tt Index^{th}}$ element of the list List unifies with Element. Fails if Index is not a positive integer or greater than the length of List. Either Index and List, or List and Element, should be instantiated (but not necessarily ground) at the time of the call.

log_ith(?Index, ?Tree, ?Element)

basics
Succeeds if the ${\tt Index^{th}}$ element of the Tree Tree unifies with Element. Fails if Index is not a positive integer or greater than the number of elements that can be in Tree. Either Index and Tree, or Tree and Element, should be instantiated (but not necessarily ground) at the time of the call. Tree is a list of full binary trees, the first being of depth 0, and each one being of depth one greater than its predecessor. So log_ith/3 is very similar to ith/3 except it uses a tree instead of a list to obtain log-time access to its elements.

log_ith_bound(?Index, ?Tree, ?Element)

basics
is like log_ith/3, but only if the ${\tt Index^{th}}$ element of Tree is nonvariable and equal to Element. This predicate can be used in both directions, and is most useful with Index unbound, since it will then bind Index and Element for each nonvariable element in Tree (in time proportional to $N*logN$, for $N$ the number of nonvariable entries in Tree.)

length(?List, ?Length)

basics
Succeeds if the length of the list List is Length. This predicate is deterministic if List is instantiated to a list of definite length, but is nondeterministic if List is a variable or has a variable tail. If List is uninstantiated, it is unified with a list of length Length that contains variables.

same_length(?List1, ?List2)

basics
Succeeds if list List1 and List2 are both lists of the same number of elements. No relation between the types or values of their elements is implied. This predicate may be used to generate either list (containing variables as elements) given the other, or to generate two lists of the same length, in which case the arguments will be bound to lists of length $0,1,2,\ldots$.

select(?Element, ?L1, ?L2)

basics
List2 derives from List1 by selecting (removing) an Element non-deterministically.

reverse(+List, ?ReversedList)

basics
Succeeds if ReversedList is the reverse of list List. If List is not a proper list, reverse/2 can succeed arbitrarily many times. It works only one way.

perm(+List, ?Perm)

basics
Succeeds when List and Perm are permutations of each other. The main use of perm/2 is to generate permutations of a given list. List must be a proper list. Perm may be partly instantiated.

subseq(?Sequence, ?SubSequence, ?Complement)

basics
Succeeds when SubSequence and Complement are both subsequences of the list Sequence (the order of corresponding elements being preserved) and every element of Sequence which is not in SubSequence is in the Complement and vice versa. That is,

$$length({\tt Sequence}) = length({\tt SubSequence})+length({\tt Complement})$$

for example, subseq([1,2,3,4], [1,3], [2,4]). The main use of subseq/3 is to generate subsets and their complements together, but can also be used to interleave two lists in all possible ways.

merge(+List1, +List2, ?List3)

listutil
Succeeds if List3 is the list resulting from ``merging'' lists List1 and List2, i.e. the elements of List1 together with any element of List2 not occurring in List1. If  List1 or  List2 contain duplicates, List3 may also contain duplicates.

absmerge(+List1, +List2, ?List3)

listutil
Predicate absmerge/3 is similar to merge/3, except that it uses predicate absmember/2 described below rather than member/2.

absmember(+Element, +List)

listutil
Similar to member/2, except that it checks for identity (through the use of predicate '=='/2) rather than unifiability (through '='/2) of Element with elements of List.

member2(?Element, ?List)

listutil
Checks whether Element unifies with any of the actual elements of List. The only difference between this predicate and predicate member/2 is on lists having a variable tail, e.g. [a, b, c | _ ]: while member/2 would insert Element at the end of such a list if it did not find it, Predicate member2/2 only checks for membership but does not insert the Element into the list if it is not there.

delete_ith(+Index, +List, ?Element, ?RestList)

listutil
Succeeds if the ${\tt Index^{th}}$ element of the list List unifies with Element, and RestList is List with Element removed. Fails if Index is not a positive integer or greater than the length of List.

closetail(?List)

listutil
Predicate closetail/1 closes the tail of an open-ended list. It succeeds only once.