4.5 Practical Session 4

The purpose of Practical Session 4 is to help you get familiar with the idea of recursing down lists. We first suggest some traces for you to carry out, and then some programming exercises.

First, systematically carry out a number of traces on a2b/2 to make sure you fully understand how it works. In particular:

1. Trace some examples, not involving variables, that succeed. E.g., trace the query a2b([a,a,a,a],[b,b,b,b]) and relate the output to the discussion in the text.

2. Trace some simple examples that fail. Try examples involving lists of different lengths (such as a2b([a,a,a,a],[b,b,b])) and examples involving symbols other than a and b (such as a2b([a,c,a,a],[b,b,5,4])).

3. Trace some examples involving variables. For example, try tracing a2b([a,a,a,a],X) and a2b(X,[b,b,b,b]).

4. Make sure you understand what happens when both arguments in the query are variables. For example, carry out a trace on the query a2b(X,Y).

5. Carry out a series of similar traces involving member. That is, carry out traces involving simple queries that succeed (such as member(a,[1,2,a,b])), simple queries that fail (such as member(z,[1,2,a,b])), and queries involving variables (such as member(X,[1,2,a,b])). In all cases, make sure that you understand why the recursion halts.

Having done this, try the following.

1. Write a 3-place predicate combine1 which takes three lists as arguments and combines the elements of the first two lists into the third as follows:

   ?- combine1([a,b,c],[1,2,3],X).
 
X = [a,1,b,2,c,3]
 
?- combine1([foo,bar,yip,yup],[glub,glab,glib,glob],Result).
 
Result = [foo,glub,bar,glab,yip,glib,yup,glob]

2. Now write a 3-place predicate combine2 which takes three lists as arguments and combines the elements of the first two lists into the third as follows:

   ?- combine2([a,b,c],[1,2,3],X).
 
X = [[a,1],[b,2],[c,3]]
 
?- combine2([foo,bar,yip,yup],[glub,glab,glib,glob],Result).
 
Result = [[foo,glub],[bar,glab],[yip,glib],[yup,glob]]

3. Finally, write a 3-place predicate combine3 which takes three lists as arguments and combines the elements of the first two lists into the third as follows:

   ?- combine3([a,b,c],[1,2,3],X).
 
X = [join(a,1),join(b,2),join(c,3)]
 
?- combine3([foo,bar,yip,yup],[glub,glab,glib,glob],R).
 
R = [join(foo,glub),join(bar,glab),join(yip,glib),join(yup,glob)]

All three programs are pretty much the same as a2b/2 (though of course they manipulate three lists, not two). That is, all three can be written by recursing down the lists, doing something to the heads, and then recursively doing the same thing to the tails. Indeed, once you have written combine1, you just need to change the `something' you do to the heads to get combine2 and combine3.

Now, you should have a pretty good idea of what the basic pattern of predicates for processing lists looks like. Here are a couple of list processing exercises that are a bit more interesting. Hint: you can of course use predicates that we defined earlier, like e.g. member/2 in your predicate definition.

1. Write a predicate mysubset/2 that takes two lists (of constants) as arguments and checks, whether the first list is a subset of the second.

2. Write a predicate mysuperset/2 that takes two lists as arguments and checks, whether the first list is a superset of the second.