Assignment 8 "Ultralite": Tail Recursion and Infinite Lists!
Due Friday, March 11 by 11:59 PM (HI!)

Please note the special time and due date for this assignment. No CS 60 dollars may be used on this assignment.

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".

Part 1: Tail Recursion (20 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.
  
  
• The function combine is similar to append: combine takes two lists as input and produces a new list which has all of the elements of the first list and all of the elements of the second list, but in some funky unspecified order. That is, combine can produce the new list and the order of the elements is not important. Here is an example:

    rex> combine([1, 2, 3], [4, 5]);
    [5, 4, 3, 2, 1]  <-- The order is reversed, but who cares!?
    

  Write a tail-recursive implementation of combine.

Part 2: Infinite Lists [30 Points]

This part of the assignment should be submitted in a file called part2.rex.

In class we wrote (or will write, depending on when you are reading this!) 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 == 0 ? F : get(N-1, R);

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

Now you could use these functions as follows:

rex > get(2, from(10));
12

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

1. 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.
   
   
2. 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. Again, your function should output some finite number of pairs and should then delay the evaluation of the rest of the list.