Please use the standard commenting convention of your name, file name, and date in each file. In addition, please have at least a one-line comment for each function that you implement. Finally, please BE SURE TO NAME YOUR FILES AND FUNCTIONS EXACTLY AS WE'VE SPECIFIED. The grading procedure for this assignment is partially automated and files and functions whose spellings differ from those below will cause our scripts to "barf".
This part of the assignment should be submitted in a file called part1.rex.
In class we wrote a function called from(N) which takes a number N as input and generates the infinite list of integers greater than or equal to N. The function was written as:
from(N) => [N |$ from(N+1)];Another useful function is get(N,L) which takes a non-negative integer N and an arbitrary infinite list L as input and returns the Nth element in the list (where the first element is assumed to have index 0). This function can be written as:
get(N, [F | R]) => N == 0 ? F : get(N-1, R);Notice that this function definition assumes that N is not larger than the length of the list. (This is OK here because the lists we'll be dealing with are, well, um, infinitely long!) Finally, one last function which you'll use is find_index(X,L). This function takes an element X and an arbitrary list L and returns the index of the first occurrence of X in list L. This function can be written as:
find_index(X, [Y | L]) => X == Y ? 0 : 1 + find_index(X, L);Notice that this implementation also implicitly assumes that the list is infinitely long. (Otherwise, we would need a base case!)
Now you could use these functions as follows:
rex > get(2, from(10));You're welcome to use these functions in your code if you like.
12
rex > find_index(5, from(4));
1
lai(L1, L2) => [F1 | R1] = L1, [F1 |$ lai(R1, L2)];You can try this function out in rex. For example, try lai(from(100), from(0)). What you'll discover is that the numbers from the second infinite list [0, 1, 2, ...] never ever get put on this list. That is, no matter how long you wait, you will never see 0, for example, in this infinite list. So, if you try to run
find_index(0, lai(from(100), from(0)));you'll end up running forever! Professor Z. Ip of the Massachusetts Institutue of Typing has proposed another approach to merging infinite lists L1 and L2 which he calls "zipping". Zipping takes the first element of L1, then the first element of L2 then it goes back and takes the next element from L1 followed by the next element of L2, etc. For example, here's what would happen if we zipped from(100) with from(0):
rex > zip(from(100), from(0));Your first task (and it's very short) is to implement the zip function. Use delayed evaluation, of course! Specifically, your delayed evaluation implementation of zip should put some finite number of elements on the output list (it can be more than one) and then should delay the evaluation of the rest of the list.
[100, 0, 101, 1, 102, 2, 103, 3, 104, 4, 105, 5, 106, 6, 107, 7,
108,
8, 109, 9, 110, 10, 111, 11, 112,
more? (return to continue, q to quit, a to abort, g to go
non-stop, b to break)
rex > lai_pairs(from(0), from(0));Professor Di Agnol observes that this is very bad. The pair [1, 0], for example, will never ever appear on this list, no matter how long we wait! Her idea is to write a function called pairs(L1, L2) which will build all pairs from L1 and L2 in such a way that eventually any pair that you're looking for will appear on this list. Her clever insight is that the output could look like this:
[ [0, 0], [0, 1], [0, 2], [0, 3], [0, 4], [0, 5],
[0, 6], [0, 7], [0, 8], [0, 9], [0, 10], [0, 11],
[0, 12], [0, 13], [0, 14], [0, 15], [0, 16],
[0, 17], [0, 18], [0, 19], [0, 20], [0, 21],
[0, 22], [0, 23], [0, 24],
more? (return to continue, q to quit, a to abort, g to go
non-stop, b to break)
rex > pairs(from(0), from(0));Take a close look at the pattern of the output. Notice that the first pair contains the 0th element of the first list and the 0th element of the second list. The next two pairs are those in which sums of the indices are exactly 1 (that is, the pair comprising the 0th element in the first list and the 1st element of the second list and then the pair comprising the 1st element of the first list and the 0th element of the second list). The next few pairs are those in which the sums of the indices are exactly 2, etc. In this way, if we are waiting for any given element to show up on the list, it will appear eventually. Your task is to write this pairs function using delayed evaluation. You may need to write several helper functions to do this. Again, your function should output some finite number of pairs and should then delay the evaluation of the rest of the list.
[[0, 0], [0, 1], [1, 0], [0, 2], [1, 1], [2, 0],
[0, 3], [1, 2], [2, 1], [3, 0],
[0, 4], [1, 3], [2, 2], [3, 1], [4, 0],
[0, 5], [1, 4], [2, 3], [3, 2], [4, 1], [5, 0],
[0, 6], [1, 5], [2, 4], [3, 3],
more? (return to continue, q to quit, a to abort, g to go
non-stop, b to break)
| ?- occurs(spam, [oh, spam, spam, we, love, spam], X).When writing this predicate, be careful that it "computes" exactly the correct number of occurences (an easy pitfall is to write a version of this function that returns all values of X less than or equal to the number of occurences). Also, your occurs predicate should be able to generate the terms that occur a particular number of times, e.g.,
X = 3 ;
no
| ?- occurs(T, [oh, spam, spam, we, love, spam], 3).
T = spam ;
no
| ?- find([1, 2], [1, 2, 1, 2, 1], 0).Notice that pattern [1, 2] occurs in target [1, 2, 1, 2, 1] beginning at position 0 of the target (that is, the very beginning of the target list).
yes
[1, 2, 1, 2, 1]It also occurs again at position 2 of the target.
^
|
The pattern [1, 2] appears beginning right here at location 0.
I'm looking for a 1 followed immediately by a 2 and I find it
beginning here!
[1, 2, 1, 2, 1]Thus, here's another Prolog query and response:
^
|
The pattern [1, 2] appears beginning right here at location
2.
| ?- find([1, 2], [1, 2, 1, 2, 1], 2).In fact, these are the only two occurences as indicated by the following Prolog query and response:
yes
| ?- find([1, 2], [1, 2, 1, 2, 1], X).find(P,T,I) should also work when both P and I are unbound variables. Write the rules for find.
X = 0 ;
X = 2 ;
no
| ?- remove(1, [2, 1, 3], [2, 3]).
yes
| ?- remove(1, [2, 1, 3], X).
X = [2,3] ;
no
| ?- remove(1, [2, 3, 4], X).
no
| ?- remove(X, [1, 2, 3], [2, 3]).
X = 1 ;
no
| ?- remove(X, [1, 2, 3], Y).
X = 1,
Y = [2,3] ;
X = 2,
Y = [1,3] ;
X = 3,
Y = [1,2] ;
no
Your remove rule must be able to work when either the first or last argument, or both, are variables, as demonstrated above. You don't need to worry about the case that the second argument is a variable.
Submit all your list code in a file named part3.pl.
Recall that in rex we wrote a function called powerset which took as input a set S (a list of distinct items) and returned the powerset of S: The set of all subsets S. In rex, we had to come up with a clever algorithm (based on "weirdo analysis") and then implement it.
Now, we will do something even better in prolog! We'll write a rule called subset(List1, List2) which takes two lists List1 and List2 as input and infers whether List1 is a subset of List2. (Notice that since we're using lists to represent sets, we're implicitly assuming that any given element appears at most once in a list. Also, you should not assume anything about the order in which the elements are given in the lists.) No weirdo analysis here! We're simply teaching prolog how to infer that one set is a subset of another!
You may wish to use one or more helper rules. Your subset rule must work when it is given two actual lists and it must also work when the first argument is a variable and the second argument is an actual list. It need not work in the case that the second argument is a variable (although it's not hard to take care of that case either). For example:
| ?- subset([1, 2], [2, 1, 3]).
yes
| ?- subset([1, 2], [1]).
no
| ?- subset(X, [1, 2]).
X = [] ;
X = [1] ;
X = [1,2] ;
X = [2] ;
X = [2,1] ;
Notice in the last example, the same subset appeared more than once (as [1, 2] and [2, 1]). This is fine, as long as your rule eventually stops and all correct answers are produced at least once. Moreover, the order in which the subsets are found and the order of the actual elements in the lists is unimportant. Submit your code in a file called part4.pl.
Place the code for this part of the assignment in a file called bonus.pl .
You've been hired by the International Cottage of Pancakes (ICOP) to develop some software for their pancake chefs. A chef is presented with a stack of pancakes, each of different size. This stack is represented by a list. For example, the list [20, 10, 30] means that pancake with diameter 20 units is on the griddle, the pancake with diameter 10 units is on top of that pancake, the pancake with diameter 30 units is on the very top of the stack. (ICOP reinforces their pancakes with special ingredients to ensure that pancakes can be stacked with small pancakes below big ones!).
ICOP wishes to serve their pancake stacks in sorted order from largest at the bottom to smallest at the top.
A pancake chef can insert a flipper in any position in the stack and then flip the pancakes above the flipper (thus reversing their order) onto the stack of pancakes below the flipper. For example, by placing the flipper at position 1 in the stack [20, 10, 30], we would insert the flipper immediately above pancake 1, that is above the pancake with diameter 20. When we now flip, the pancakes above the flipper get reversed, resulting in the list [20, 30, 10]. If we now stick the flipper at position 0 in the stack [20, 30, 10], that is under the bottommost pancake, we would now flip and get [10, 30, 20]. Now, we can stick the flipper at possition 1 again (immediately above the pancake with diameter 10) and the flip results in the stack [10, 20, 30]. This stack is sorted and the chef is happy!
Your job is to write a rule called pancakes(Stack, Number, Moves) which takes as input a list of pancakes called "Stack", an integer number "Number" indicating the number of flips to be performed, and a list "Moves" which contains exactly "Number" moves. pancakes(Stack, Number, Moves) is true if and only if the list of "Moves" contains exactly "Number" moves and these result in going from "Stack" to a sorted stack of the pancakes.
Using the example above, we could type
| ?- pancakes([20, 10, 30], 3, [1, 0, 1]).and prolog would say "yes".
Now, make sure that your pancakes rule works EVEN when the third argument, the list of Moves, is a variable. This will be the only argument that might ever be used as a variable and it allows the chef to determine a sequence of flips to sort the pancakes. For example,
| ?- pancakes([20, 10, 30], 3, X).
X = [0,1,0] ;
X = [1,0,1] ;
no
Notice that prolog found TWO different ways to sort the pancakes in 3 moves. (Check to make sure that you agree that both solutions are valid!)
Notice also that the "Stack" may be arbitrarily large, but will never contain two pancakes of the same size.
Your job is to write "pancakes" in prolog! It may be helpful
to
use the built-in "length" and "append" rules. It may also be helpful
to you to use the "reverse" rule from above, and the "sorted" rule from lecture. Here is sorted (reverse is up to you):
sorted([]).
sorted([_]).
sorted([X, Y | Rest]) :- X < Y, sorted([Y | Rest]).