Lists themselves have the following syntax. They always start and end with square brackets, and each of the items they contain is separated by a comma. Here is a simple list [a,freddie,A_Variable,apple]
Prolog also has a special facility to split the first part of the list (called the head) away from the rest of the list (known as the tail). We can place a special symbol | (pronounced 'bar') in the list to distinguish between the first item in the list and the remaining list. For example, consider the following.
where A = first and B=[second,third]
[first,second,third] = [A|B]
The unification here succeeds. A is bound to the first item in the list, and B to the remaining list.
Now lets consider some comparisons of lists:
[ ] /* this is a special list, it is called the empty list because it contains nothing */
[a,b,c] unifies with [Head|Tail] resulting in Head=a and Tail=[b,c]
[a] unifies with [H|T] resulting in H=a and T=
[a,b,c] unifies with [a|T] resulting in T=[b,c]
[a,b,c] doesn't unify with [b|T]
 doesn't unify with [H|T]
 unifies with . Two empty lists always match
Lets see what happens when we ask some simple queries.
p([H|T], H, T).
?- p([a,b,c], X, Y).
?- p([a], X, Y).
?- p(, X, Y).
This method constitutes the basis of the searching method. We shall use it to pull apart a list, looking at the first item each time, recursively looking at the tail, until we reach the empty list , when we will stop.
Otherwise we could prove something was on a list if we could prove that although it didn't match the existing head of the list, it nonetheless would match another head of the list if we disregarded the first item and just considered the rest of the list i.e.
on(Item,[Item|Rest]). /* is the target item the head of the list */
We now have a program consisting of a fact and a rule for testing if something is on a rule. To recap, it sees if something is the first item in the list. If it is we succeed. If it is not, then we throw away the first item in the list and look at the rest.
Let's go through the last example again in more detail. Suppose we pose the query:
The first clause of on requires the first argument of on to match with the list head. However apples and pears do not match. Thus we must move on to the second clause. This splits the list up as follows:
?- on(apples, [pears, tomatoes, apples, grapes]).
This now gives us the following goal in the body of our rule:
DisregardHead = pears
Tail = [tomatoes,apples,grapes]
Again, we see if apples and tomatoes match using our initial facts. Since they don't, we again use our second clause to strip off the current list head, giving us the new goal: on(apples,[apples,grapes]). Since apples matches apples our first clause succeeds as does our query.
on(apples, [tomatoes, apples, grapes]).
Write a program called member, that would be able to see if something was a member of a list. The program would inform me that sydney_opera_house was not on list by failing, yet confirm all the above were on the list by succeeding (answering yes).
[london_buckingham_palace, paris_eiffel_tower, york_minster, pisa_leaning_tower, athens_parthenon]
This again is pure unification. List2 now consists of the head prolog plus whatever List1 was bound to. If List1 were to be bound e.g. List1 = [list,c,pascal,basic], List2 would now be the list [prolog,lisp,c,pascal,basic]
List2 = [prolog|List1]
We can use this construction technique to build lists during recursion. We'll present three examples of this in the forthcoming cards.
The way we do this in Prolog uses both list construction and list deconstruction. Recall that on the previous card we saw how we could glue an item onto the front of a list to produce a new list. Thus we can produce the list [c,one,two,three] from the list [one,two three] by saying NewList = [c|[one,two,three]. This results in NewList being bound to the list [c,one,two,three]. This is the clue to how we write append in Prolog. We can recursively split the first list into single items by the deconstruction techniques discussed earlier. We can then use the construction method above to glue together a new list, which we shall illustrate next.
Result = [a,b,c,one,two,three]
Now for the rule which does most of the work. This says search through the
first list can each time stick the first thing on the first list onto the
Now lets go through in detail how this actual works.
Let's now follow the program as it executes. Using the second rule we first reduce the query to
and then to
and finally to
This final clause can match against the initial fact, giving append(,[one,two,three],[one,two,three]). Since this is a fact, this terminates the recursion. As we pop out of each recursive step we then add on (respectively) c,b, and a to the list, giving the list [a,b,c.one,two,three].
Next we need to say that if the item passes our test, put it in the output list
sift([X|T],[X|Result]):- X > 6, /* is X greater than 6 */
sift(T,Result). /* if so then go find the rest */
Otherwise we are will disgard the head and look for other hits in the tail
sift([ThrowAway|Tail],Result):- /* disgard the head */
sift(Tail,Result). /* and look in the tail */
To this goal, we first unify with clause 2. The result is to evaluate the subgoal 1 > 6, this clearly fails, so we move on to the third clause and try the goal sift([12,3,14,5,8],Result). This again matches on the second clause of sift. We now try the subgoal 12>6, this succeeds and we now attempt the goal sift([3,14,5,8],Result). However, notice what also happens. By using this clause we also place 12 on our output list.
?- sift([1,12,3,14,5,8], Result).
Stepping further through our example, we see that greater than subgoal in clause 2 succeeds for 14 and 8, till finally we get the goal sift(,Result). This matches the first goal, with Result bound to . As we come out of the recursion, we see that clause 2 builds up the result for to the list , then [14,8], then finally [12,14,8], before the query finally succeeds.
Result = [b,c,d]
Result = [a,a,c,a,d]
Result = [a,b,a,c,a,d]
This is the end of the prolog tutorial.
Result = [mike,b,mike,c,mike,d]
Result = [a,foo,a,c,a,d]
Result = [a,b,a,c,a,d]