COMP 333 Take Home Quiz #3 on Prolog Problem 1 Write a predicate ct1(L,X,C) that counts the number of occurrences of X in L, matching the count with C. Examples ?- ct1( [a,a,a], a, C). C = 3. ?- ct1( [a,a,b], a, C). C = 2. ?- ct1( [a,a,b], b, C). C = 1. Part A Solve the problem using recursion. Base case ct1( [], _, 0). % if L is empty, then C is 0 for any value of X General case ct1(L,X,C): Use a pattern to divide L into head and tail. Call predicate recursively on tail of L, yielding count CT. If X matches head of L, then C matches CT + 1 (match with is), Else C matches CT. Use the if-then-else expression inside a single rule or write two rules for the two cases.

Part B Now write a second version ct2(L,X,C) using backtracking instead of recursion. Look at the following query that uses interactive backtracking: ?- member( Y, [a,a,b] ), Y=a. % compound query: goal #1, goal #2 Y = a ; % match #1, user enters ; for backtrack Y = a ; % match #2, user enters ; for backtrack false. % no more matches In goal #1 of the query, Y matches with some element of the list. In goal #2, Y matches with 'a'. If goal #2 succeeds, then it reports a match for Y. If goal #2 fails, then it auto backtracks to goal #1 and tries another value of the list for Y. So the member predicate in goal #1 matches Y with three different values from the list, but only two of those values succeed in goal #2. Write ct2(L,X,C) using findall/3 to run the compound query member(Y,L), Y=X and provide all matching values in list T, which will be multiple copies of X in list T. findall(X, (compound query goes here), T) Then for the next goal, use length/2 to match length of list T with C. The value of C is based on the length of T, which is the number of times we found X in L. Note that if the 2nd argument to findall is a compound query, youll need to add parens around the entire compound query so that it looks like a single argument to findall. Also, dont confuse X and Y. X represents the item being counted. Y represents a value from the list generated by member(Y,L). Y may or may not match with X.

Problem 2 Write a predicate lg1(A,B,L) which is a list generator that takes two integers A and B and generates a list of all numbers from A to B inclusive in list L. Examples: ?- lg1(1,10,L). L = [1, 2, 3, 4, 5, 6, 7, 8, 9|...] . % Prolog auto truncates display of longer lists ?- lg1(1,10,L), writeln(L). [1,2,3,4,5,6,7,8,9,10] L = [1, 2, 3, 4, 5, 6, 7, 8, 9|...] . % add 2nd goal writeln(L) to see all items in a longer list Part A Use recursion to define lg1(A,B,L). Base case lg1( B, B, [B]). % if A = B, then L is list containing B General case Assert A

Part B Use backtracking to write a second version lg2(A,B,L). Note the use of the built-in predicate ?- between(1,5,X). X = 1 ; X = 2 ; X = 3 ; X = 4 ; X = 5. Write predicate lg2(A,B,L) that uses between/3 to generate values A through B in variable X, then use findall/3 to collect all values of X through backtracking and collect them into list L.