Harvey Mudd College
Computer Science 60
Assignment 2, Due Thursday, Sep. 16, by midnight

"Functioning first-class"

This assignment is 50 points of your overall grade.

The problems in this assignment exercise high- and low-level functional programming concepts, including the use of functions as both arguments and return values from other functions.

You are asked to construct several function definitions in rex and test them. You should submit your functions in a single file named hw2.rex. As in assignment 1, commenting your functions and your file are important. The grading of this assignment is similar to assignment 1. As you write functions to solve these problems, however, it is a good idea (and very much the spirit of rex and functional programming) to try to devise programs as elegant and concise as possible. In a conflict between elegance and readbility, however, readability should win... .

For an example of a thoroughly commented function, look at the file insert.rex in the directory /cs/cs60/assignments/a2.

You will want to have read to Chapter 3 (rewrite rules are formally presented in Chapter 4, however) You may also want to experiment with functions returning functions and anonymous functions in rex.

Test cases for each of these problems appear in the directory /cs/cs60/assignments/a2 . The names of the test-case files are p?test.rex, where ? is 1, 2, 3, 4, 5, or 6.

1. Create a function named erdos which takes as input a single (numeric) value x (or whatever name you choose). The output it computes is either 3x + 1, in the case that x is odd and x/2 in the case that x is even. Thus, appropriate runs might include

       rex >  erdos(42);
       21
   
       rex >  erdos(109);
       328
       

2. Write iterate(N, F, X), taking 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 erdos function from the example above.
     //   since the first argument is 1, the desired result is erdos(3),
     //   which is 10.
     
     rex > iterate(1, erdos, 3);
     10
   
     // Hey, now I'm iterating twice and computing erdos(erdos(3))
     
     rex > iterate(2, erdos, 3);
     5
   
     // And this is finding erdos(erdos(erdos(3)))
     
     rex > iterate(3, erdos, 3);
     16
   
     // Iterating the add1 function twice is equivalent to adding 2.
   
     rex > iterate(2, add1, 9);
     11
     

3. Create a function named collapse(L) that takes a list L of integers as input and as output returns a list of the number of iterations required so that erdos(erdos(...(erdos(x))...)) equals 1, for each element x in the list L. (To be precise, collapse returns the smallest such number of iterations.)
   
   As a bit more explanation, consider collapse([3]). Looking at the previous examples from the iterate specification, we see that

     erdos(erdos(erdos(3))) = 16.
     

   Continuing in this way,

     erdos(erdos(erdos(erdos(erdos(erdos(erdos(3))))))) = 1
     

   with erdos iterated 7 times. Thus, collapse([3]) == [7]. Further examples of collapse in action include

     rex >  collapse([3, 10, 5, 16]);
     [7, 6, 5, 4]
   
     rex >  collapse([129, 55, 85]);
     [121, 112, 9]
     

   Will every positive integer collapse to 1? No one knows, though many mathematicians have worked on it. The mathematician Paul Erdos actually felt that "mathematics is not yet ready for such problems" as this, known as the "3x+1" problem. Check out the site http://www.paulerdos.com/0.html for more on Paul Erdos.
   
   
4. In assignment 1's scrabble problem, a standard database of scores for each letter was used. Other point-assignment systems might be useful in various contexts, however. The file /cs/cs60/assignments/a2/letterScoring.rex contains the scrabble database from the game, as well as four other databases named letterOrder, numerology, telephone, and jotto. (That file offers explanations.) Each database consists of a list of 26 [ letter, score ] pairs.
   
   Write a function createScorer(db) that takes one such database as input and returns a function as output. The output function should be a word-scoring function, that is, should take a string as input and output a score for that string based on the database provided to createScorer. The score is the sum of the scores of the letters. For example,

       // Include the file with the scoring tables
   
       rex >  sys(in,"/cs/cs60/assignments/a2/letterScoring.rex");
   
       // Let scrabbleScorer be bound to the function created by
       //   createScorer in this case.
   
       rex >  scrabbleScorer = createScorer(scrabble);
       1
   
       rex >  scrabbleScorer("rex");
       10
   
       // In this case the function output by createScorer is used immediately.
       rex >  createScorer(letterOrder)("ronaldwilsonreagan");
       202
       

5. Write a function envelope(F,G) that 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). (It should return F(X) if they're equal, since in that case F(X) == 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 we 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
       

6. The file insert.rex in the directory /cs/cs60/assignments/a2 defines an insert function which adds nodes to binary search trees in such a way that an inorder listing of the tree returns a sorted list of data. That file also explains that our representation for a binary search tree is that it's either empty (the empty list) or consists of a list with three elements: [ rootValue, leftSubtree, rightSubtree ]. The rootValue will always be an integer, and the left and right subtrees are binary search trees. Write the function delete(X, T) that 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. For example, the list

   [10, [3, [], []], [42, [20, [], []], [60, [], []] ] ]

   represents the tree
   
   You should use the algorithm described in class for removing an item from a binary search tree. For example here is some input and output:

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