6.4 Practical Session

The purpose of Practical Session 6 is to help you get more experience with list manipulation. We first suggest some traces for you to carry out, and then some programming exercises.

The following traces will help you get to grips with the predicates discussed in the text:

1. Carry out traces of append/3 with the first two arguments instantiated, and the third argument uninstantiated. For example, append([a,b,c],[[],[2,3],b],X) Make sure the basic pattern is clear.
2. Next, carry out traces on append/3 as used to split up a list, that is, with the first two arguments given as variables, and the last argument instantiated. For example, append(L,R,[foo,wee,blup]).
3. Carry out some traces on prefix/2 and suffix/2 . Why does prefix/2 find shorter lists first, and suffix/2 longer lists first?
4. Carry out some traces on sublist/2 . As we said in the text, via backtracking this predicate generates all possible sublists, but as you’ll see, it generates several sublists more than once. Do you understand why?
5. Carry out traces on both naiverev/2 and rev/2 , and compare their behaviour.

Now for some programming work:

1. It is possible to write a one line definition of the member predicate by making use of append/3 . Do so. How does this new version of member compare in efficiency with the standard one?
2. Write a predicate set(InList,OutList) which takes as input an arbitrary list, and returns a list in which each element of the input list appears only once. For example, the query

   set([2,2,foo,1,foo, [],[]],X).

   should yield the result

   X = [2,foo,1,[]].

   (Hint: use the member predicate to test for repetitions of items you have already found.)

3. We ‘flatten’ a list by removing all the square brackets around any lists it contains as elements, and around any lists that its elements contain as elements, and so on, for all nested lists. For example, when we flatten the list

   ?- [a,b,[c,d],[[1,2]],foo].

   we get the list

   ?- [a,b,c,d,1,2,foo].

   and when we flatten the list

   ?- [a,b,[[[[[[[c,d]]]]]]],[[1,2]],foo,[]].

   we also get

   ?- [a,b,c,d,1,2,foo].

   Write a predicate flatten(List,Flat) that holds when the first argument List flattens to the second argument Flat . This should be done without making use of append/3 .

Ok, we’re now halfway through the book. And flattening a list is the Pons Asinorum of Prolog programming. Did you cross it ok? If so, great. Time to move on.