ASSIGNMENT 2. Due December 18. ---------------------------- 1. Write a predicate substitute(X,Y,Xs,Ys) that is true if the list Ys is the result of substituting Y for all occurrences of X in the list Xs. ======================================================= 2. Write a predicate without_doubles_1(Xs, Ys) that is true if Ys is the list of the elements appearing in Xs without duplication. The elements in Ys are in the same order as in Xs with the last duplicate values being kept. Sample run: ?- without_doubles_1([1,2,3,4,5,6,4,4],X). X = [1, 2, 3, 5, 6, 4]; No ======================================================= 3. Write a predicate without_doubles_2(Xs, Ys) that is true if Ys is the list of the elements appearing in Xs without duplication. The elements in Ys are in the reversed order of Xs with the first duplicate values being kept. Sample run: ?- without_doubles_2([1,2,3,4,5,6,4,4],X). X = [6, 5, 4, 3, 2, 1]; No ======================================================= 4. Given a list of elements colored red, white, and blue, reorder the list so that all the red elements appear first, then all the white elements, followed by the blue elements. The reordering should preserve the original relative order of elements of the same color. Sample run: ?- reorder([red(1), white(2), blue(3), red(4), white(5)], Reordered). Reordered = [red(1), red(4), white(2), white(5), blue(3)]; no Write two versions of the reordering program: with and without difference lists. ======================================================== 5. Write a ternary predicate delete_all(item,list,result) that is true if result is obtained from 'list' by deleting all occurrences of 'item'. Use cut to prevent backtracking. Sample run: ?-delete_all(a,[a,b,c,a,d,a],X). X=[b,c,d]; No ?-delete_all(a,[b,c,d],X). X=[b,c,d]; No ====================================================== 6. Write a ternary predicate delete_nth that deletes every N'th element from a list. Sample runs: ?- delete_nth([a,b,c,d,e,f],2,L). L = [a, c, e] ; No ?- delete_nth([a,b,c,d,e,f],1,L). L = [] ; No ?- delete_nth([a,b,c,d,e,f],0,L). No ?- delete_nth([a,b,c,d,e,f],10,L). L = [a, b, c, d, e, f] ; No ======================================================= 7. Write a predicate that starts interaction with the user, asking her to input a number, then another number, and then the operation (addition or multiplication). After that, the program performs the operation on the numbers and writes the result in a file. The process repeats until the user types 'finish'. All the results should be written in one file. If the user makes a wrong input (it is not a number, or it is neither addition nor multiplication), the program should repeat the question, indicating that what has been typed in is not a number, or is a wrong operation. IO predicates can be found in the Section 5 of the book. Check also Prolog manual. ====================================================== 8. Write a predicate merge(L1,L2,L) which is satisfied by the ordered lists of integers L1, L2, and L so that L is the result of merging L1 and L2. ?- merge([1,3,5],[2,4,6,8], X). X=[1,2,3,4,5,6,8]; false ====================================================== 9. Write the following as a set of Prolog predicates: Eat at the restaurant if it looks nice but if it stinks don't eat there using: (a) cut and fail combination (b) the '\+' predicate. ===================================================== 10. Consider the program for findall: findall(X,G,_) :- asserta(found(mark)), call(G), asserta(found(X)), fail. findall(_,_,L) :- collect_found([],M), !, L=M. collect_found(S,L) :- getnext(X), !, collect_found([X|S],L). collect_found(L,L). getnext(X) :- retract(found(X)), !, X \== mark. Let collect_found([a,b],L) be the goal. Draw the complete derivation tree for this goal as discussed in the lecture, indicating the parts of the tree cut by the cut predicate.