## 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.

Patrick Blackburn, Johan Bos and Kristina Striegnitz
Version 1.2.5 (20030212)