## 6.4 Practical Session 6

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` 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` 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` and `suffix`. Why does `prefix` find shorter lists first, and `suffix` longer lists first?

4. Carry out some traces on `sublist`. 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` and `rev`, and compare their behavior.

Now for some programming work:

1. It is possible to write a one line definition of the `member` predicate by making use of `append`. 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 element, 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 exercise can be done without making use of `append`.

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