/***************************/ /* */ /* Answers to worksheet 5 */ /* */ /***************************/ /* Exercise 5.1 Tail of a list */ tail([], []). tail([X|Xs], Xs). /* Exercise 5.2 Zum Fritz */ /* This following was already given: */ vorspeisen_available([wurstsalat, zwiebelsuppe]). meat_available([rinderbraten, brathahnchen, schweinekotelett]). fish_available([matjesfilet, blaue_forelle]). nachspeisen_available([apfelstrudel, obstsalat]). meal(H, M, D) :- hors_d_oeuvre(H), maincourse(M), dessert(D). maincourse(M) :- meat(M). maincourse(M) :- fish(M). member(X, [X|Xs]). member(X, [Y|Ys]) :- member(X, Ys). /* These are the new bits: */ hors_d_oeuvre(H) :- vorspeisen_available(VA), member(H, VA). meat(M) :- meat_available(MA), member(M, MA). fish(F) :- fish_available(FA), member(F, FA). dessert(D) :- nachspeisen_available(NA), member(D, NA). /* Explanations of how some of the following definitions work can */ /* be found in Bratko. */ /* Exercise 5.3 Adding an item to the front of a list */ add(X, Xs, [X|Xs]). /* Exercise 5.4 Deleting an occurrence of an item */ del(X, [X|Xs], Xs). del(X, [Y|Ys], [Y|Zs]) :- del(X, Ys, Zs). /* Exercise 5.5 Inserting an occurrence of an item */ insert(X, Ys, NewYs) :- del(X, NewYs, Ys). /* Exercise 5.6 Checking for consecutive elements */ next_to(X1, X2, [X1,X2|Xs]). next_to(X1, X2, [Y|Ys]) :- next_to(X1, X2, Ys). /* Exercise 5.7 Checking list lengths */ evenlength([]). evenlength([X|Xs]) :- oddlength(Xs). oddlength([X]). oddlength([X|Xs]) :- evenlength(Xs). /* Exercise 5.8 Translation */ dict(the, le). dict(dog, chien). dict(chases, chasse). dict(cat, chat). translate([], []). translate([Word|Words], [Mot|Mots]) :- dict(Word, Mot), translate(Words, Mots). /* The limitations include: it does not handle agreement (``chat'' */ /* is feminine and so the translation of, e.g., ``the'' before */ /* ``cat'' needs to be ``la''); and the order of, e.g., adjectives */ /* and nouns in French is often the reverse of what it is in */ /* English. */ /* Exercise 5.9 Monkey planning revisited */ /* This is as before: */ move(state(under_banana, on_box, under_banana, has_not), grasp, state(under_banana, on_box, under_banana, has)). move(state(Place, on_floor, Place, H), climb, state(Place, on_box, Place, H)). move(state(Place1, on_floor, Place1, H), push(Place1, Place2), state(Place2, on_floor, Place2, H)). move(state(Place1, on_floor, B, H), walk(Place1, Place2), state(Place2, on_floor, B, H)). /* This is revised to accumulate the list of actions: */ canget(state(X, Y, Z, has), []). canget(State, [Action|Actions]) :- move(State, Action, Newstate), canget(Newstate, Actions). /* Exercise 5.10 Sun headlines */ start(s1). start(s2). final(s7). final(s8). trans(s1, [dirty, skinflint, barmy], s2). trans(s2, [charles, diana, queen], s3). trans(s3, [sex_romps, death_plunge], s4). trans(s3, [shuns, scoffs_at], s5). trans(s3, [joins, tells_of], s6). trans(s4, [fury], s7). trans(s5, [drugs, babies, widows], s6). trans(s6, [crackdown, riddle, war], s7). trans(s7, [crisis], s8). headline(H) :- start(S), path(S, H). path(S, []) :- final(S). path(S, [H|T]) :- trans(S, List, Snew), member(H, List), path(Snew, T). /* Exercise 5.11 Final and Consec in terms of append */ append([], Xs, Xs). append([X|Xs], Ys, [X|Zs]) :- append(Xs, Ys, Zs). contains(Item, List) :- append(X, [Item|T], List). final(Item, List) :- append(X, [Item], List). consec(Item1, Item2, List) :- append(X, [Item1, Item2 | T], List). /* Exercise 5.12 Sublist in terms of append */ sublist(List1, List2) :- append(L1, L2, List2), append(List1, L3, L2). /* Exercise 5.13 Reverse */ reverse([], []). reverse([Head|Tail], Reversed) :- reverse(Tail, Revtail), append(Revtail, [Head], Reversed). /* Exercise 5.14 Reverse using an accumulator */ reverse2(List, Reversed) :- revacc(List, [], Reversed). revacc([], Acc, Acc). revacc([Head|Tail], Acc, Reversed) :- revacc(Tail, [Head|Acc], Reversed). /* The difference in general is that the size of the proof tree */ /* for the earlier program is quadratic in the number of elements */ /* in the list to be reversed, while that of the second program is */ /* linear. */ /* Exercise 5.15 Palindromes */ palindrome(L) :- reverse(L, L). /* Exercise 5.16 Tree traversals */ prefix(void, []). prefix(tree(Node, LeftTree, RightTree), Pre) :- prefix(LeftTree, PreL), prefix(RightTree, PreR), append([Node | PreL], PreR, Pre). postfix(void, []). postfix(tree(Node, LeftTree, RightTree), Post) :- postfix(LeftTree, PostL), postfix(RightTree, PostR), append(PostL, PostR, PostInt), append(PostInt, [Node], Post). infix(void, []). infix(tree(Node, LeftTree, RightTree), Inf) :- infix(LeftTree, InfL), infix(RightTree, InfR), append(InfL, [Node], InfInt), append(InfInt, InfR, Inf). /* Exercise 5.17 Tree membership */ tree_member(X, tree(X, L, R)). tree_member(X, tree(N, L, R)) :- tree_member(X, L). tree_member(X, tree(N, L, R)) :- tree_member(X, R). /* Exercise 5.18 Permutation sort */ perm([], []). perm([X|Xs], Ps) :- perm(Xs, PTail), insert(X, PTail, Ps). permsort(OriginalList, SortedList) :- perm(OriginalList, SortedList), is_ordered(SortedList). is_ordered([]). is_ordered([X]). is_ordered([X1, X2 | Xs]) :- X1 =< X2, is_ordered([X2 | Xs]). /* Exercise 5.19 Insertion Sort */ insertsort([], []). insertsort([X|Xs], SortedList) :- insertsort(Xs, SortedTail), rightful_insert(X, SortedTail, SortedList). rightful_insert(X, [], [X]). rightful_insert(X, [Y|Ys], [X, Y | Ys]) :- X =< Y. rightful_insert(X, [Y|Ys], [Y | NewTail]) :- X > Y, rightful_insert(X, Ys, NewTail). /* Exercise 5.20 Quick sort */ quicksort([], []). quicksort([X|Xs], NewList) :- split(X, Xs, Smalls, Bigs), quicksort(Smalls, S_Smalls), quicksort(Bigs, S_Bigs), append(S_Smalls, [X | S_Bigs], NewList). split(X, [], [], []). split(X, [Y|Ys], [Y|Smalls], Bigs) :- X > Y, split(X, Ys, Smalls, Bigs). split(X, [Y|Ys], Smalls, [Y|Bigs]) :- X =< Y, split(X, Ys, Smalls, Bigs). /* Exercise 5.21 Merge sort */ merger([], [], []). merger([], [X|Xs], [X|Xs]). merger([X|Xs], [], [X|Xs]). merger([X|Xs], [Y|Ys], [X|Zs]) :- X =< Y, merger(Xs, [Y | Ys], Zs). merger([X|Xs], [Y|Ys], [Y|Zs]) :- X > Y, merger([X|Xs], Ys, Zs). mergesort([], []). mergesort([X], [X]). mergesort([X1, X2 | Xs], NewList) :- divide([X1, X2 | Xs], Half1, Half2), mergesort(Half1, S_Half1), mergesort(Half2, S_Half2), merger(S_Half1, S_Half2, NewList). divide([], [], []). divide([X], [X], []). divide([X1, X2 | Xs], [X1 | Ys], [X2 | Zs]) :- divide(Xs, Ys, Zs). /* Exercise 5.22 Polymodal sort */ polypermsort(OriginalList, SortedList) :- polyperm(OriginalList, SortedList), is_ordered(SortedList). polyperm(Xs, Ys) :- samelength(Xs, Ys), perm(Xs, Ys). samelength([], []). samelength([X|Xs], [Y|Ys]) :- samelength(Xs, Ys).