/* Here are solutions I came up with. They're not the only ones possible, I'm sure. */ /* ---------------------------------------------------------- Problem 1 (10 points): Write a relation shorter(L1,L2) that is true if list L1 contains the same number or fewer elements than list L2. The relation is false if list L1 contains more elements than list L2. */ /* This one is pretty straightforward. The first rule just says that the empty list is shorter than everything. The second rule says that if you want to prove that the list on the left is shorter than the list on the right, take the first elements off of each and, recursively, prove that the list on the left is shorter than the list on the right. */ shorter([],X). shorter([X1|Y1],[X2|Y2]) <- shorter(Y1,Y2). /* ---------------------------------------------------------- Problem 2 (10 points): Write a relation delete_one(E,L,R) that is true if R is the resulting list of removing one instance of E from L. The relation is false if E is not a member of L. */ /* This one was explained in class on Friday. */ delete_one(X,[X|Y],Y). delete_one(X,[Y|Z],[Y|Q]) <- delete_one(X,Z,Q). /* Here's another version using append to do the slicing and dicing. This little proof procedure asks: is there a way to partition list L into two parts, L1 and [E|R2], such that the second begins with element E, and that when you append L1 and R2 (i.e., the original list L without element E) you get the list R? */ delete_one(E, L, R) <- append(L1, [E|R2], L)&append(L1, R2, R). /* ---------------------------------------------------------- Problem 3 (10 points): Write a relation subsequence(L1,L2) that is true if list L1 contains a subset of the elements of L2 in the same order. */ /* We explained this in class on Wednesday...before the homework was due!...using prefix and suffix predicates. Below we've just replaced prefix and suffix with the equivalent append predicates. */ subsequence(S,L) <- append(L1,L2,L) & append(S,L3,L2). append([],Z,Z). append([A|X],Y,[A|Z]) <- append(X,Y,Z). /* ---------------------------------------------------------- Problem 4 (10 points): Write a relation substitute(X,Y,L1,L2) that is true is the list L2 is the result of substituting Y for all occurrences of X in the list L1. */ /* Start with an example. How would you prove this?: substitute(a,x,[a,b,c],[x,b,c]). Since you're now tuned to thinking recursively, you'd note that the above is true if this is true: substitute(a,x,[b,c],[b,c]) Rewrite this as: substitute(a,x,[a,b,c],[x,b,c]) <- substitute(a,x,[b,c],[b,c]). Generalize like this (you could use different variable names): substitute(Old,New,[Old|Rest1],[New|Rest2]) <- substitute(Old,New,Rest1,Rest2). Now how do you prove this?: substitute(a,x,[d,b,c],[g,b,c]). Well, if the first element of the first list isn't the same as Old, then it doesn't matter what the first element of the second list is...again you just need to prove the following: substitute(a,x,[b,c],[b,c]). Rewrite like this: substitute(a,x,[d,b,c],[g,b,c]) <- substitute(a,x,[b,c],[b,c]). Generalize like this: substitute(Old,New,[Any|Rest1],[Any|Rest2]) <- substitute(Old,New,Rest1,Rest2) & Old \= Any. Finally, the base case involves empty lists: substitute(Old,New,[],[]). Put 'em all together give that inequality a name, and it looks like this: */ substitute(Old,New,[],[]). substitute(Old,New,[Old|Rest1],[New|Rest2]) <- substitute(Old,New,Rest1,Rest2). substitute(Old,New,[Any|Rest1],[Any|Rest2]) <- different(Old,Any) & substitute(Old,New,Rest1,Rest2). different(A,B) <- A\=B. /* ---------------------------------------------------------- Problem 5 (10 points): Write a relation last(L,E) that is true if E is the last element of list L. */ /* Again, let's start with an example. What's the last of the list [a]? Well, that would be a. We know then that this is true: last([e],e). And we can generalize that like this: last([E],E). That's our base case. You could rewrite it like this too, if it makes more sense this way: last([E|[]],E). They mean the same thing, but the latter version perhaps makes it more apparent to the reader that whatever E is, it's the last thing in the list because all that's left when you take away E is the empty list. But how do you prove this example?: last([a,b,c],c). Again, your keen eye for recursive solutions tells you that the above is true if this is true: last([b,c],c). Which is true if this is true: last([c],c). And that's true because it's our base case from above. Generalizing this: last([a,b,c],c) <- last([b,c],c). gives this: last([H|T],E) <- last(T,E). So one solution is: */ last([E], E). last([H|T], E) <- last(T, E). /* Another solution comes about like this: Now that you understand the power of append, you see that last([a,b,c],c). is the same as asking "If I take that constant c and make a list of it, is there some way to partition the original list [a,b,c] into two parts such that the first part can be appended onto the list made of the constant c giving the original list [a,b,c]?" Or, written in CILOG, it looks like this: */ last(L,E) <- append(M,[E],L). /* That's all there is for now. */
Last revised: October 2, 2004