Assignment 5: All rex all the time!
Due Monday, October 6 by 11:59 PM

In this assignment you will be implementing a number of interesting rex functions to build up your rex programming muscles! You may define whatever additional functions you like in order to help implement these functions, unless explicitly stated otherwise. Also, unless explicitly stated otherwise, the ONLY built-in rex functions that you should use are append and max (max takes two numbers as input and returns the larger of the two numbers).

Please place all of your functions in a single file called hw5.rex. Please use the standard commenting convention of placing your name, file name, and date at the top of the file. For each of the fifteen problems below, include a comment (Java comment syntax works in rex) indicating which problem this is (such as "this is the code for the remove problem"). Please make sure that your solutions appear in the order that we have given the problems ("supertwiddle", then "remove", etc.). Also include a comment for each function that you define. Finally, use white space (spaces, new lines, etc.) to make your code readable. We are not enforcing any particular formating convention for your code, but do avoid writing long functions all on one line. That's ugly.

All of the functions below are worth the same number of points, with the exception of the functions get and set for 2-dimensional arrays and the delete function for binary trees, which are worth more points than the other functions.

Finally, please BE SURE TO NAME YOUR FUNCTIONS EXACTLY THE SAME AS WE'VE SPECIFIED BELOW. The grading procedure for this assignment is partially automated and functions whose spellings differ at all from those below will not be seen by the automatic testing programs.

1. supertwiddle(L) returns a list identical to L except that every pair of successive elements has been sweapped. If the list has an odd number of elements then the last element is untouched. For example here is some sample input and output:

     rex > supertwiddle([1, 2, 3, 4, 5, 6]);
     [2, 1, 4, 3, 6, 5]
   
     rex > supertwiddle([1, 2, 3, 4, 5]);
     [2, 1, 4, 3, 5]
     

2. remove(X, L) constructs a list identical to L except that every occurence of X in L has been removed. You may assume that L is a list of atomic elements. (That is, the elements of L are never lists themselves.) The order of the unremoved elements should not be changed. If X does not occur in L then, naturally, this function simply constructs a list identical to L. For example here is some sample input and output:

     rex > remove(3, [5, 4, 3, 2, 3, 1, 2]);
     [5, 4, 2, 1, 2]
     

3. pair(X, L) returns a list of all pairs (a pair is a list with exactly two elements) in which the first element is X and the second element is taken from L. For example here is some sample input and output:

     rex > pair(1, [2, 3, 4]);
     [[1, 2], [1, 3], [1, 4]]
     

4. all_pairs(L1, L2) takes two lists as arguments and returns a list whose elements are all the pairs with the first element from L1 and the second element from L2. For example here is some sample input and output:

     rex > all_pairs([1, 2, 3], [4, 5]);
     [[1, 4], [1, 5], [2, 4], [2, 5], [3, 4], [3, 5]]
     

5. at_least(X, L) is a predicate (that is, it returns 1 or 0 representing true or false, respectively). This predicate returns true if and only if there are at least X (X is an integer which may be positive or negative) elements in list L. Do not use the length function to solve this! This would be very inefficient if X was small and L was a long list! Use no extra functions to implement this - just plain old recursion! For example here is some sample input and output:

     rex > at_least(2, [42]);
     0
   
     rex > at_least(2, [42, 2001]);
     1
   
     rex > at_least(2, [42, 300, 2001]);
     1
     

6. height(T) takes a list representing a tree as input (remember from lecture that a tree is just cleverly represented as a list!) and returns the height of the tree. The height of the empty tree is defined to be 0. The height of a tree with just one node is 1. The height of a tree, in general, is the maximum number of nodes among all paths from the root of the tree to a leaf of the tree. For example here is some sample input and output:

     rex > mytree = [5, [3, [], []], []];
     1
   
     rex > height(mytree);
     2
     

7. supereverse(L) takes a list L of lists as input and returns a list whose elements are the reversals of the original lists. Your function should be just one line of rex code that uses the built-in map function and whatever other rex built-in function(s) you wish. For example here is some sample input and output.

     rex > supereverse([ [1, 2, 3], [4, 5] ]);
     [ [3, 2, 1], [5, 4] ]
     

8. dupereverse(L) takes a list L whose elements could be numbers or lists (the elements of those lists could, in turn, be numbers and/or lists). This function returns a list which is the reversal of L. If L contains a list, then that list gets recursively reversed. For example here is some sample input and output.

     rex > dupereverse([1, [2, 3], [4, [5, 6, [7, 8], 9] ] ]);
     [[[9, [8, 7], 6, 5], 4], [3, 2], 1]
     

   You may use any built-in rex functions. In particular, the reverse function and atomic predicate (take a look at how we implemented flatten) will be especially useful here.
   
   
9. get(A, i, j) returns the value stored in "row" i and "column" j of 2-dimensional array A. If nothing has been inserted into A, you should treat it as an infinitely large array of 0's. You will find it useful to represent array A as a list of lists. Each list in A corresponds to a row of elements in the array. Thus, each list (or "row") is actually a 1-dimensional array. It will be useful to use the code for 1-dimensional arrays that we developed in class. See examples in the next problem description.
   
   
10. set(A, i, j, X) constructs a new list which represents a 2-dimensional array identical to A except that the element at "row" i and "column" j of the array is now set to have value X. Again, it will be useful to use the code for setting elements in a 1-dimensional array as described in class. Here are some examples of get and set in action:

      rex > myarray = [];
      1
    
      rex > get(myarray, 3, 4);
      0
    
      rex > myarray = set(myarray, 3, 4, 42);
      1
    
      rex > myarray;
      [[], [], [], [0, 0, 0, 0, 42]]
    
      rex > get(myarray, 3, 4);
      42
    
      rex > get(myarray, 3, 3);
      0
      

11. uniquify(L) returns a list identical to L except that only the first occurence of each item of the list is saved. That is, all duplicates of an item are removed except for the first occurence. You may assume that the elements of L are atomic. For example here is some sample input and output:

      rex > uniquify([1, 2, 1, 3, 2, 4, 2]);
      [1, 2, 3, 4]
      

12. envelope(F, G) takes two functions as input. Each function is a function of one number. (That is, F and G each take one number as input.) envelope returns a function which takes as input one number, call it X (the name is irrelevant), and returns the larger of F(X) and G(X). Careful here - envelope returns a function and not a number. For example here is some sample input and output:

      // To demonstrate, I'll first define two functions called foo and goo.
      rex > foo(X) => 2*X + 1;
      foo
    
      rex > goo(X) => 3*X - 2;
      goo
    
      // Now, envelope(foo, goo) returns a function and here I will let moo
      // represent that function.
    
      rex > moo = envelope(foo, goo);
      1
    
      // Now, let's evaluate the function moo with input of 5.
    
      rex > moo(5);
      13
      

13. iterate(N, F, X) takes a non-negative integer N, a function F (which is assumed to be a function of one integer argument, and an integer X. This function then computes F(F(F...(F(X)))) where the number of F's is equal to N. (This is called an iterated function system and is used in generating fractal images.) If N is 0, the function simply returns X. For example here is some input and output:

      // Here I'm using the goo function from the example above.
      
      rex > iterate(1, goo, 5);
      13
    
      // Hey, now I'm iterating twice and computing goo(goo(5))
      
      rex > iterate(2, goo, 5);
      37
      

14. builditerate(N, F) takes a non-negative integer N and a function F (which is assumed to be a function of one integer) and returns a function of one argument (call it X) which computes iterate(N, F, X). For example here is some input and output:

      // Assuming the goo function from the previous two examples.
      // builditerate(2, goo) builds a function which we'll assign to spam.
      
      rex > spam = builditerate(2, goo);
      1
    
      // Now we'll evaluate spam(5)...
    
      rex >spam(5);
      37
      

15. delete(X, T) takes a value X and a list T representing a binary search tree and returns a binary search tree with all of the elements of T except with X removed. You can assume that X is definitely in the tree T. You should use the algorithm described in class for removing an item from a binary search tree. (Take a look at the insert function that we wrote in class. The recursion in delete will use similar ideas!) For example here is some input and output:

      rex > mytree = [10, [3, [], []], [42, [20, [], []], [60, [], []] ] ];
      1
    
      rex > delete(10, mytree);
      [20, [3, [], []], [42, [], [60, [], []]]]