Assignment 6 Lite: Delayed Evaluation and Tail Recursion!
Due Monday, October 13 by 11:59 PM

This assignment is "liter" than usual, due to the upcoming exam on October 14. The assignment is worth 70 points (rather than the usual 100).

This assignment comprises two parts. In the first part you'll get a chance to explore rex's delayed evaluation mechanism. The second part involves writing tail-recursive functions. Throughout this assignment, you can use any built-in rex functions that you like.

As indicated below, you will need to submit two separate files: One called part1.rex and the other called part2.rex.

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 at all from those below will cause our scripts to "barf".

Part 1: Infinite Lists (45 Points)

Recall that 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)];

  get(N, [F | R]) => N == 1 ? F : get(N-1, R);

  find_index(X, [Y | L]) => X == Y ? 1 : 1 + find_index(X, L);

Now you could use these functions as follows:

rex > get(5, from(10));
14

rex > find_index(5, from(4));
2

• First, the totally gratuitous story. Professor I. Lai of the Pasadena Institute of Technology (P.I.T.) wants to write a function that takes as input two infinite lists L1 and L2 and returns an infinite list that contains all of the elements in L1 and all of the elements in L2, where the order of the elements in this new list is not important. Professor Lai's implementation works like this:

        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));
        [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) 
      

  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.
  
  
• Your next task is a bit more challenging. Now you are going to implement a pairs function for infinite lists. That is, given two infinite lists L1 and L2, pairs(L1, L2) returns an infinite list of all pairs (a pair is list with two elements) in which the first element comes from L1 and the second one comes from L2. Professor Lai's implementation, called lai_pairs has the following behavior:

      rex > lai_pairs(from(0), from(0));
      [ [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) 
      

  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:

      rex > pairs(from(0), from(0));
      [[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) 
      

  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. However, among the pair function and any of its helper functions, there should be a total of only one delayed evaluation (that is, the "$" sign should appear just once in total.). Again, your function should output some finite number of pairs and should then delay the evaluation of the rest of the list.

Part 2: Tail Recursion (25 Points)

• Write a tail recursive function called mylength(L) which takes an arbitrary list L of finite length and returns the length of L. As usual with tail recursion, mylength will call some other helper function which does the actual computation using an accumulator.
  
  
• Write a tail recursive function called myremove(X, L) which removes all occurences of X from list L. As usual, myremove will call some other tail recursive helper function which does the actual work using an accumulator. In order to qualify as tail recursive, this function can do no work after the recursive call. It can, however, call other functions before the recursive call. However, if a function is called it must be either non-recursive or tail recursive itself!