TEACH LISTEX STEVE TORRANCE 4 FEB 1986 MSc Prolog Programming. ====================== Some exercises with lists. 1. Using (a) a tree diagram; (b) a box diagram, show how each of the following list structures could be represented as dotted pairs: [a,b,c] [a,b] [a] [a,[b,c]] [[a],[b,[c]]] [a|X] [a,b|X] [[A|B]|[C|D]] 2. What are the heads and tails (in the strict sense of "head" and "tail") of the following list-structures? [a,b,c,d] [a] [a,[]] [a,b,[c]] [a,[b,c]] [[a,b],c] [a | X] [a,b | X] [] [[]] [[],[]] [[]|[]] [a|[]] [[a|X]|[Y|Z]] [a | [b,c]] [a|[b|[c|[d]]]] 3. Write a program to test your answers to the last question. The program should have a predicate headtail(L,H,T) in which the first argument is a list and the second and third are output values returning respectively the head and tail of the list L. You will have to USE the head-tail pattern structure in your definition of 'headtail'. What happens when you call your predicate on either of the following "listoid" structures? [a,b | c] [a | b,c] 4. What valuables do the variables X,Y and Z get when the following pairs of list-structures are unified together? (Try to resist the temptation to control-D before you've had a go at working them out cranially.) ?- [X,Y] = [this, [is,a,list]]. ?- [X,Y,Z] = [[this,is],[a,[quite,heavily,[nested]]],list]. ?- [X,Y | Z] = [[this,is],[another,[quite,heavily]],[nested,list]]. ?- [[[this,is],X],Y] = [[Z,another], [[quite,heavily,[nested,[list]]]]]. ?- [here,is,a,different | X] = [here,is,Y,Z,[set,of,words], [just,to,relieve,the,[],tedium]]. ?- [[i,really,must],stop,_| X ] = [Y,Z, thinking,up,[such,stupid,examples]] . ?- [[_],[X]] = [[a|Z],[Z|Y]]. ?- [[X],[X]] = [[a|_],[Y|Z]]. 5. Write a definition of the member relation, using the 'headtail' relation defined earlier. Write a short account in English of the behaviour of 'member'. Explain in English what happens if you call 'member' with an item specified and the list unspecified. 6. Write a program that will change: [the, pavement, was, crowded] to [the, sidewalk, was, crowded] [the, line, was, engaged] to [the, line, was, busy] [the, tap, was, on] to [the, faucet, was, on] [the, film, was, colourful] to [the, movie, was, colorful] [maggie, was, angry] to [ronnie, was, mad] [open, the, bonnet] to [open, the, trunk] etc. Define a predicate 'change' which will swap individual words, (for instance the definition should include the clause 'change(pavement,sidewalk)') and a predicate 'alter' that will alter a list of words, by changing individual ones. Write a (non-recursive) version of alter which will only work on lists of the form '[the,X,was,Y]'. Modify 'alter' so that it will work on lists of any structure. This version will have to be recursive. You will need a 'bottoming-out' clause for 'alter' that deals with altering an empty list. You'll also need a clause which says that List1 can be 'altered' to List2 if the head of List1 can be 'changed' to the head of List2, and if the tail of List1 can be 'altered' to the tail of List2. In order to make this work, you'll need to add a clause to the end of your list of clauses for 'change' which says that, if a word has not already been found in the previous clauses, then 'change' it into itself. (If you need help with this exercise, look at section 3.4 of Clocksin and Mellish.) 7. Write a short explanation in English of the behaviour of the 'append' predicate. Define the following relations, using 'append', or predicates defined in terms of 'append', in as many definitions as possible. Where you can, give alternative definitions of the relations without using 'append'. Comment, in the cases where you have parallel definitions of the same relation, on which definition seems to be the more (or most) efficient and/or clear. a. List L contains the elements E1 and E2 occurring contiguously somewhere in it. b. List L1 is a sublist of list L. c. List L1 comprises the last N members of list L. d. List L1 comprises the first N members of list L. e. Lists L1 and L2 are alike except that L2 contains element E2 instead of E1 at the first occurrence of the latter in L1. f. Lists L1 and L2 are alike except every occurrence of E1 in L1 has been replaced by E2 in L2. g. List L1 is list L with the elements reversed. h. List L is a palindrome (it reads the same backwards as forwards). i. List L contains element E in the Nth position. j. Element E1 occurs earlier than element E2 in list L. 8. The built-in predicate 'atomic(X)' succeeds if its argument is either an atom or an integer. Using 'atomic', write a predicate 'simple_list(L)' which succeeds iff its argument contains only atomic elements. Use 'simple_list' to define a predicate 'nesting(L,N)', which gives the maximum nesting of a given list L (so that, for example, the list [[a], [b], [c]] will have a nesting of degree 1, and [[a], [b,[c]], [d,[e,[f]]], g] will have a nesting of degree 3. Write a predicate 'flatten(L1,L2)', where L1 is given as a list of any degree of nesting, and L2 contains all the atomic elements of L1, in a list nested to degree 0. You will need to account for three sorts of cases: - the empty list; - lists containing at least one atomic element; - other kinds of lists. Use 'atomic' in your definition; you will also have to use the built-in predicate 'not'. 9. Given the solution of the 'fox and chicken' variant of the river-crossing problem (see TEACH CROSSRIVER), construct a solution for the 'missionaries and cannibals' variant. Use the following representations for the initial and final states: startstate([1,3,3]). goalstate([0,0,0]). - where the numbers specify the number of (a) boats; (b) missionaries; and (c) cannibals on the left bank. 10. Write a program to solve the Towers of Hanoi problem for four discs, by searching through a state-transition space, where each node is defined as a list specifying membership of the start-peg, the destination peg, and the spare peg, respectively. Thus startstate ( [ [4,3,2,1], [], [] ] ). goalstate ( [ [], [4,3,2,1], [] ] ).