Session 3: Introduction to Lists

Definition of a pair

A pair containing a and b is denoted as .(a,b).

Recursive definition of lists

Many students have problems when working with lists. This is because they use their intuitive feeling instead of the definition of lists. Lists look like as if they are 'flat', but in reality they are not: they are nested pairs. So when things become confusing think of the (recursive) definition of lists. A list is: The empty list is denoted as []. So, a list with three elements a, b and c is denoted as .(a, .(b, .(c,[]) ) )

Exercise 1: Is a pair that somewhere contains the empty list a list?

A list can contain anything as elements: constants, variables and ... lists! We illustrate this by showing a list that contains three elements: a, a list (containing b and c) and d: .(a, .(.(b,.(c,[])),.(d,[]))). Try to draw the tree representation of the above list!

Shorthand notation for lists

As you see, the notation rapidly becomes complex to write down and read. This is why a shorthand notation for lists has been introduced. Always keep in mind that you can always rewrite the shorthand notation in the full notation. Often looking at a list in the full notation helps you understand things better than in the shorthand notation!

The shorthand notation for the empty list stays the same []. A list with one element .(a,[]) becomes [a], a list two elements .(a,.(b,[])) becomes [a,b] etc. The complex nested list we used in the previous paragraph becomes [a,[b,c],d]. When you are at home or in the pc-rooms, try out how you can use the prolog engine to rewrite these expressions, e.g. try to type the following at the prompt: 

?- List = .(a, .(.(b,.(c,[])),.(d,[]))).
Exercise 2 Can you guess the result of the following queries? 
?- [A,B] = .(a, .(.(b,.(c,[])),.(d,[]))).
?- [A,B,C] = .(a, .(.(b,.(c,[])),.(d,[]))).
?- [A,B,C,D] = .(a, .(.(b,.(c,[])),.(d,[]))).

Splitting a list

There is also a shorthand notation for the pair functor '.' namely '|', which is written infix. This means that .(a,b) is also written as [a|b]. So [a] means the same as .(a,[]) or [a|[]]. As another example, [a,b] means the same as .(a,.(b,[])) or [a|[b|[]]] or [a|[b]].

Now what is the use of this (except confusing students)? This mechanism makes it easy to split up lists. For instance suppose we have a list [a,b,c,d] and we want to split it up into its head (first element: a) and its tail (the rest: [b,c,d]). We can do this by typing something like ?- [Head | Tail] = [a,b,c,d].. Because [a,b,c,d] means the same as [a | [b,c,d]], the result is that Head is a and Tail is [b,c,d]. We will use things like this often when we are writing recursive predicates! Finally note that the tail of a list is always a list itself (this follows from the definition of lists)!

Exercise 3: Consider the following queries (if you like you can of course try these out on your computer later). Will these queries succeed? If so, what will be the variable bindings? If not, why does it fail? If you are not sure, draw the tree representations of the lists!! 

1 ?- .(a, .(b, .(c,.(d,[])))) = [A,B|C].
2 ?- [A|B] = .(a, .(.(b,.(c,[])),.(d,[]))).
3 ?- [A,B|C] = .(a, .(.(b,.(c,[])),.(d,[]))).
4 ?- [ a, b | [] ] = [ H | T].   
5 ?- [ a, b, c] = [ E1, E2 | T ].
6 ?- X = a, Y = [ 1, [2,3] ], Z = [X | Y].
7 ?- X = a, Y = [ 1, [2,3] ], Z = [X,Y]. 
8 ?- X = [a], Y = [ 1, [2,3] ], Z = [X | Y].

List processing

Reread the definition for lists. This is clearly a recursive definition. As a consequence, the programs that process lists will also be recursive. We repeat from the previous session that a recursive program consists of at least 2 clauses: When dealing with lists, the basic clause usually (but not always!) specifies how to solve the problem for the empty list. The recursive clause usually specifies how to solve the problem for the complete list if we have a solution for the tail of the list.

Let's illustrate this on the problem of writing a predicate that, given a list, counts the number of elements in that list (we call this the length of the list). First we have to think about the basic clause. What is the most simple list for which we can solve this problem? Some people will think of a list that only contains a single element, but there exists an even simpler list: the empty list! So our basic clause is one that solves the problem for the empty list: 

listlength([],0).
Now we can think about the recursive clause: if I can solve a smaller problem, how can I solve this problem? A smaller problem is counting the number of elements in a shorter list. Suppose I split the given list into its head and tail and I can solve the problem for the tail, how to solve the problem for the complete list? Well, if I know that the tail has N elements, I know that the list itself must have N + 1 elements. When we write this in prolog, we get this solution: 
listlength([Head|Tail],Count):-
	listlength(Tail,PartialCount),
	Count is PartialCount + 1 .

Exercise 4: What will be the result of the following queries ?- listlength([1,[2,3]],L). and ?- listlength([1|[2,3]],L).? Does this predicate work like you had expected?

Exercise 5: The predicate listlength/2 calculates the length of the list. Now write a predicate that, given a list of numbers, calculates the sum of all these numbers. Then write a predicate for calculating the average. Can you do this by traversing the list only once?

Exercise 6: During the first exercise session many students wonder if there exists a way to do multiple writes with a single predicate (such as you can do in e.g. Java or C/C++). Lists provide the answer: write a predicate printlist/1 that takes as input a list and writes every item of the list, followed by a newline (nl).

Exercise 7: LOA is a game comparable to checkers. Suppose we represent a row on a LOA board as a list where each element is either the atom w (white disk), the atom b (black disk) or the atom n (no disk). Define the predicate countdisk/2 that given a row, returns the number of disks on that row. Try the following queries later on your computer (at home or in the PC-rooms) and ask for all answers using ';'. 

?- countdisk([w,b,n,n],Count).
?- countdisk([w,b,n,n],4).
?- countdisk([w,b,n,n],2).
?- countdisk([n,n,n,n,n,n,n,n,n,n],Count).


?- countdisk([w,n,b|Tail],Count).
Did you expect the result for that last query? Can you explain it?

Exercise 8: We store a LOA game as a list of all moves (in chronological order). A move (starting on one position on the board, going to another position) is represented with a move functor with 4 arguments. The first and second argument are the column (a letter) and row (a number) of the from-position. The third and fourth argument are the column and row of the to-position. E.g. we can have the following game: [move(b,1,b,3), move(c,10,c,8), move(b,3,b,5)]. In this game the first player moved from b1 to b3, then the second player moved from c10 to c8 and then the first player moved from b3 to b5.

  1. Write a predicate that, given a movelist, calculates the number of 'rounds' played in the game. With 'round' we mean one move of each of the two players (unless at the end of the game). E.g. the movelist [move(b,1,b,3), move(c,10,c,8), move(b,3,b,5)] is from a game with two rounds. What will be the result of the query ?- nb_rounds(List,Number). if you ask for multiple answers (by typing ;)?
  2. Write a predicate that splits a given movelist into two lists: one with the black moves, the other with the white moves. Keep in mind that a movelist can contain an odd number of moves (like in the movelist given above)!
  3. Write a predicate that given a list with the moves from black and a list with the moves from white, merges both into a chronological movelist.

Exercise 9: During a student initiation ritual some years ago, several students got injured when they came in contact with a mix of 'daily use' products such as vinegar, oil,... . Suppose that we want to prevent such accidents from happening in the future by developing a system that tests whether a certain mixture is dangerous or not. To help us, a chemical expert gave us a database of mixtures of 'daily products' and numbers indicating how dangerous the mixtures are. The database is written as prolog facts: 

reacts(vinegar,salt,25).
reacts(salt,water,3).
reacts('brown soap',water,10).
reacts('pili pili', milk,7).
reacts(tonic,bailey,8).
Higher numbers are more dangerous. The order of the elements is not important: e.g. salt and vinegar react the same as vinegar and salt do. Now suppose that you can add the numbers for all reacting pairs: e.g. the total number for a mixture of vinegar, salt and water is 25 (vinegar & salt) + 3 (salt & water) + 0 (vinegar & water) = 28. Also, suppose that a total number less than 5 results in no irritation, between 6 and 12 results in minor irritation, between 13 and 20 results in minor burning wounds, between 21 and 30 results in severe burning wounds and higher values can be lethal.
Write a predicate advice/1 that given a mixture, writes to the screen what the result of using that mixture would be, e.g. 
?- advice([vinegar,salt,water]).
Warning: this mixture causes severe burning wounds, never use this!
Yes

?- advice([jam, salt, pepper, water, 'red onions', 'brown soap']).
Warning: this mixture could result in minor burning wounds!
Yes
As you can see, the mixture can contain items that are not in our database! Test your predicate on the following lists:
  1. [vinegar,water,salt,soup,'brown soap']
  2. [water]
  3. []
  4. [pineapple,strawberry,tunafish]