Exercise Chapter 4.3 on Recursion

1. 
   

    
   print_every_second([]).
   
   print_every_second([X]).
   
   print_every_second([X,YT]):-
   
   			write(Y),
   
   			 print_every_second(T).
   
   

   The trick is to realise that the notation for the general list actually allows a fixed number of elements to be ripped off/ stuck on the front of a list. Here, we destruct the list by specifying that we take the first two elements off the front of any list with more than one element and then print the second of these two elements.

   Note that this does not do anything clever with nested lists: i.e. print_every_second([a,[b],c,[d]]) will print [b][d]!

2. 
   

    
   deconsonant([]).
   
   deconsonant([AB]):-
   
   			 vowel(A),
   
   			 write(A),
   
   			 deconsonant(B).
   
   deconsonant([AB]):-
   
   			deconsonant(B).
   
   vowel(a).
   
   vowel(e).
   
   vowel(i).
   
   vowel(o).
   
   vowel(u).
   
   

   Note that we need three clauses to cover the three basic cases: either the list has no elements or we want to print the first element (because it is a vowel) or we don't want to print the first element.

   Provided the list is not empty then, for either of the remaining cases, we want to take off the first element and process the remaining list ---we have described this procedurally as there is no good declarative reading.

   Observant readers will note that the logic of the case analysis is none too good. The third clause should really be something like

    
   deconsonant([AB]:-
   
   		 	consonant(A),
   
   			deconsonant(B).
   
   

   But it would be very tedious to write out all the clauses for consonant/1 --- e.g. consonant(b) etc. There is another way of doing this, however, which we meet in chapter 7.

3. 
   

    
   head([HT],H).
   
   

   The reading is that the second argument is related to the first via the `head' relation if the first element of the first argument (a list) is the second argument.

4. 
   

    
   tail([HT],T).
   
   

   A straightforward adaption of the previous case.

5. 
   

    
   vowels([],[]).
   
   vowels([HT],[HRest]):-
   
   			vowel(H),
   
   			vowels(T,Rest).
   
   vowels([HT],Rest):-
   
   			vowels(T,Rest).
   
   vowel(a).
   
   vowel(e).
   
   vowel(i).
   
   vowel(o).
   
   vowel(u).
   
   

   This is quite a different style of program from the very procedural deconsonant/1.

   The same case analysis has been done but now we have to think what these clauses mean. Procedurally, we can tell quite similar story: the first case is that whenever we encounter an empty list then we will return an empty list.

   The second case is that whenever we have a list with a vowel at the front then we return a list with that vowel at the front ---the rest of the list has to be determined by gathering up all the vowels from the tail of the input list.

   The third case is that whenever the previous two cases fail then we discard the first element and go off to pick up all the vowels in the tail.

   The second clause could have been written as:
   

    
   vowels([HT],Ans):-
   
   		vowel(H),
   
   		 vowels(T,Rest),
   
   		 Ans=[HRest].
   
   

   if you really wanted to do so. You might find this easier to understand but the two versions are logically identical here.

   The declarative reading runs something like this: for the first clause, the list of vowels in the empty list is the empty list.

   The second case has the meaning that the list of vowels in another list with a vowel at the front has that vowel at the front and its tail is the list of vowels found in the other list.

   The third case has the meaning that the list of vowels in another list with a consonant at the front is the list of vowels in the tail of that list.

6. 
   

    
   find_every_second([],[]).
   
   find_every_second([X],[]).
   
   find_every_second([X,YT],[YRest]):-
   
   			write(Y),
   
   			find_every_second(T,Rest).
   
   

   The first clause states that the list of every second element in the empty list is the empty list. The second states the corresponding thing for a list with a single element.

   The third clause is the interesting one: the list of every second element of another list is the second element together with the list of every second element of the remainder of the other list.