A list is an ordered sequence of elements that can have any length. Lists are a common data structure in computer programming.
In Prolog, lists are represented as a tree consisting of structures that have no arguments, an empty list, or two arguments: a head and a tail. The head is a used to store a particular term in the list and the tail is recursively the rest of the list. The end of a list is customarily represented as a tail that is set to an empty list.
The data structure used to represent lists in Prolog has a functor (name) of ".". Thus, a list with the single element a can be represented as: .(a, .()) and a list with elements a, b and c can be represented as: .(a, .(b, .(c, .()))). Prolog also supports a more concise syntax for writing lists. List notation consists of elements of the list separated by commas, and the whole list enclosed in square brackets. Thus, a list with the single element a can be represented as: [a] and a list with elements a, b and c can be represented as: [a, b, c]. An empty list can be represented by a opening square bracket followed by a closing square bracket: [].
It is common for Prolog programs to manipulate lists by splitting them into a head and a tail. The | character has a special meaning in Prolog syntax to separate the head and tail of a list. Thus the Prolog syntax [X|Y] represents a list with head X and tail Y.
Examples
Determining if a term is a list. (Note: Projog provides a built-in is_list(X) predicate.)
list([]).
list([X|Xs]) :- list(Xs).
?- list([a,b,c]).
yes
?- list(abc).
noDetermining is a term is contained in a list. (Note: Projog provides built-in member(X,Y) and memberchk(X,Y) predicates.)
list_member(X,[X|Xs]).
list_member(X,[Y|Ys]) :- list_member(X,Ys).
?- list_member(X, [a,b,c]).
X = a
yes;
X = b
yes;
X = c
yes;
no
?- list_member(a, [a,b,c]).
yes;
no
?- list_member(b, [a,b,c]).
yes;
no
?- list_member(c, [a,b,c]).
yes;
no
?- list_member(d, [a,b,c]).
no
?- list_member(a,[a,a,a]).
yes;
yes;
yes;
noFinding prefixes of a list.
prefix([],Ys).
prefix([X|Xs],[X|Ys]) :- prefix(Xs,Ys).
?- prefix(X, [a,b,c,d,e,f]).
X = []
yes;
X = [a]
yes;
X = [a,b]
yes;
X = [a,b,c]
yes;
X = [a,b,c,d]
yes;
X = [a,b,c,d,e]
yes;
X = [a,b,c,d,e,f]
yes;
no
?- prefix([a],[a,b,c]).
yes
?- prefix([a,b],[a,b,c]).
yes
?- prefix([a,b,c],[a,b,c]).
yes
?- prefix([x,a,b,c],[a,b,c]).
no
?- prefix([a,c],[a,b,c]).
no
?- prefix([b,c],[a,b,c]).
no
?- prefix([X,b],[a,b,c]).
X = a
yes;
noFinding suffixes of a list.
suffix(Xs,Xs).
suffix(Xs,[Y|Ys]) :- suffix(Xs,Ys).
?- suffix(X, [a,b,c,d,e,f]).
X = [a,b,c,d,e,f]
yes;
X = [b,c,d,e,f]
yes;
X = [c,d,e,f]
yes;
X = [d,e,f]
yes;
X = [e,f]
yes;
X = [f]
yes;
X = []
yes;
no
?- suffix([c],[a,b,c]).
yes;
no
?- suffix([b,c],[a,b,c]).
yes;
no
?- suffix([a,b,c],[a,b,c]).
yes;
no
?- suffix([x,a,b,c],[a,b,c]).
no
?- suffix([a,c],[a,b,c]).
no
?- suffix([a,b],[a,b,c]).
no
?- suffix([X,c],[a,b,c]).
X = b
yes;
noDetermining sublists of lists.
sublist(Xs,Ys) :- prefix(Xs,Ys).
sublist(Xs,[Y|Ys]) :- sublist(Xs,Ys).
?- sublist([a,b,c],[a,b,c,d,e,f]).
yes;
no
?- sublist([b,c,d],[a,b,c,d,e,f]).
yes;
no
?- sublist([c,d,e],[a,b,c,d,e,f]).
yes;
no
?- sublist([b,c,e],[a,b,c,d,e,f]).
no
?- sublist([b,X,d],[a,b,c,Y,e,f]).
X = c
Y = d
yes;
noAppending two lists. (Note: Projog provides a built-in append(X,Y,Z) predicate.)
append_to_list([],Ys,Ys).
append_to_list([X|Xs],Ys,[X|Zs]) :- append_to_list(Xs,Ys,Zs).
?- append_to_list([a,b,c],[d,e,f],[a,b,c,d,e,f]).
yes
?- append_to_list([a,b,c],[d,e,f],[a,b,c,d,e,g]).
no
?- append_to_list([a,b,c],[d,e,f],[a,b,c,d,e,f,g]).
no
?- append_to_list([a,X,c],[d,e,Y],[a,b,c,Z,e,f]).
X = b
Y = f
Z = d
yes;
no
?- append_to_list([a,X,c],[Y,e(X,Y),f],[a,b,c,d,Z,f]).
X = b
Y = d
Z = e(b, d)
yes;
no
?- append_to_list([a,b,c],[d,e,f],X).
X = [a,b,c,d,e,f]
yes
?- append_to_list([a,b,c],X,[a,b,c,d,e,f]).
X = [d,e,f]
yes
?- append_to_list(X,[d,e,f],[a,b,c,d,e,f]).
X = [a,b,c]
yes;
noReversing the order of terms in a list. (Note: Projog provides a built-in reverse(X,Y) predicate.)
reverse_list(Xs,Ys) :- reverse_list(Xs,[],Ys).
reverse_list([X|Xs],Acc,Ys) :- reverse_list(Xs,[X|Acc],Ys).
reverse_list([],Ys,Ys).
?- reverse_list([],[]).
yes
?- reverse_list([a],[a]).
yes;
no
?- reverse_list([a],[b]).
no
?- reverse_list([a,b],[b,a]).
yes;
no
?- reverse_list([a,b],[a,b]).
no
?- reverse_list([a,b],[a,a]).
no
?- reverse_list([a,b],[b,b]).
no
?- reverse_list([a,b],[a]).
no
?- reverse_list([a,b],[b]).
no
?- reverse_list([a,b],[c,b,a]).
no
?- reverse_list([a,b,c,d,e,f],[f,e,d,c,b,a]).
yes;
no
?- reverse_list([a,b,c,d,e,f],[f,e,d,c,a,b]).
no
?- reverse_list([a,b,c,X,e,Y],[f,Z,d,c,b,a]).
X = d
Y = f
Z = e
yes;
no
?- reverse_list([a,b,c,d,e,f],X).
X = [f,e,d,c,b,a]
yes;
no
?- reverse_list([a,b,c,[1,2,3]],X).
X = [[1,2,3],c,b,a]
yes;
noDetermine if elements are next to each other in a list.
adjacent(X,Y,Zs) :- append_to_list(As,[X,Y|Ys],Zs).
?- adjacent(a,b,[a,b,c,d,e,f]).
yes;
no
?- adjacent(c,d,[a,b,c,d,e,f]).
yes;
no
?- adjacent(e,f,[a,b,c,d,e,f]).
yes;
no
?- adjacent(a,c,[a,b,c,d,e,f]).
no
?- adjacent(b,z,[a,b,c,d,e,f]).
no
?- adjacent(b,X,[a,b,c,d,e,f]).
X = c
yes;
no
?- adjacent(X,e,[a,b,c,d,e,f]).
X = d
yes;
no
?- adjacent(X,Y,[a,b,c,d,e,f]).
X = a
Y = b
yes;
X = b
Y = c
yes;
X = c
Y = d
yes;
X = d
Y = e
yes;
X = e
Y = f
yes;
noFind the last element of a list. (Note: Projog provides a built-in last(X,Y) predicate.)
last_element(X,Xs) :- append_to_list(As,[X],Xs).
?- last_element(f,[a,b,c,d,e,f]).
yes;
no
?- last_element(a,[a,b,c,d,e,f]).
no
?- last_element(b,[a,b,c,d,e,f]).
no
?- last_element(c,[a,b,c,d,e,f]).
no
?- last_element(d,[a,b,c,d,e,f]).
no
?- last_element(e,[a,b,c,d,e,f]).
no
?- last_element(f,[a,b,c,d,e,f]).
yes;
no
?- last_element(z,[a,b,c,d,e,f]).
no
?- last_element(X,[a,b,c,d,e,f]).
X = f
yes;
no
?- last_element(f,[a,b,c,d,e,X]).
X = f
yes;
noGet a count of the number of terms contained in a list. (Note: Projog provides a built-in length(X,Y) predicate.)
list_length([],0).
list_length([X|Xs],A) :- list_length(Xs,B), A is B+1.
?- list_length([],X).
X = 0
yes
?- list_length([a],X).
X = 1
yes;
no
?- list_length([a,b],X).
X = 2
yes;
no
?- list_length([a,b,c,d,e,f],X).
X = 6
yes;
no
?- list_length([a,b,c,d,e,f],6).
yes;
no
?- list_length([a,b,c,d,e,f],5).
noDelete elements from a list. (Note: Projog provides a built-in delete(X,Y,Z) predicate.)
delete_from_list([X|Xs],X,Ys) :- delete_from_list(Xs,X,Ys).
delete_from_list([X|Xs],Z,[X|Ys]) :- \+ X==Z, delete_from_list(Xs, Z, Ys).
delete_from_list([],X,[]).
?- delete_from_list([a,z,c],z,[a,c]).
yes;
no
?- delete_from_list([a,z,c],y,X).
X = [a,z,c]
yes;
no
?- delete_from_list([z,a,z,z,b,c,z,d,e,f,z],z,[a,b,c,d,e,f]).
yes;
no
?- delete_from_list([z,a,z,z,b,c,z,d,e,f,z],X,[a,b,c,d,e,f]).
X = z
yes;
noSelect elements from a list. (Note: Projog provides a built-in select(X,Y,Z) predicate.)
select_from_list(X,[X|Xs],Xs).
select_from_list(X,[Y|Ys],[Y|Zs]) :- select_from_list(X,Ys,Zs).
?- select_from_list(b,[a,b,c],[a,c]).
yes;
no
?- select_from_list(z,[a,b,c],[a,b,c]).
no
?- select_from_list(z,[z,a,z,z,b,c,z,d,e,f,z],X).
X = [a,z,z,b,c,z,d,e,f,z]
yes;
X = [z,a,z,b,c,z,d,e,f,z]
yes;
X = [z,a,z,b,c,z,d,e,f,z]
yes;
X = [z,a,z,z,b,c,d,e,f,z]
yes;
X = [z,a,z,z,b,c,z,d,e,f]
yes;
noChecks terms in list are ordered.
ordered([]).
ordered([X]).
ordered([X,Y|Ys]) :- X @=< Y, ordered([Y|Ys]).
?- ordered([a,b,c,d,e,f]).
yes;
no
?- ordered([a,b,c,e,d,f]).
noFind permuatations of terms in a list.
permutation(Xs,[Z|Zs]) :- select_from_list(Z,Xs,Ys), permutation(Ys,Zs).
permutation([],[]).
?- permutation([a,b],X).
X = [a,b]
yes;
X = [b,a]
yes;
no
?- permutation([a,b,c],X).
X = [a,b,c]
yes;
X = [a,c,b]
yes;
X = [b,a,c]
yes;
X = [b,c,a]
yes;
X = [c,a,b]
yes;
X = [c,b,a]
yes;
no
?- permutation([a,b,c,d,e,f],[f,e,d,c,b,a]).
yes;
no
?- permutation([q,w,e,r,t,y,u,i,o,p,a,s,d,f,g,h,j,k,l,z,x,c,v,b,n,m],[a,b,c,d,e,f,g,h,i,j,k,l,m,n,o,p,q,r,s,t,u,v,w,x,y,Z]).
Z = z
yes;
no