Assignment 2

Harvey Mudd College
Computer Science 60
Assignment 2, Due Thursday, Feb. 3, by midnight

First-class functioning and Unicalc! (part 1)

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. The last problem is an introduction to the Unicalc unit calculator application of Rex. It will be finished in Assignment 3.

Submitting your code

You are asked to construct several function definitions in rex and test them. You should submit your rex functions in a single file named hw2.rex. When you use the cs60submit program, be sure to indicate that your rex submission is assignment number 2.

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.

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

Reading

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.

Testing your code

Test cases for each of these problems appear in the directory /cs/cs60/as/a2 . The names of the test-case files are Test#.in, where # is 1 - 10. To test a particular function that has been written in the file hw2.rex, the following command will work:

% rex hw2.rex < /cs/cs60/as/a2/Test1.in

where Test1.in can be replaced wih any of the test files.

The Problems

Create the function fahrToCel(L) that takes a list of temperatures in Fahrenheit and returns a list of equivalent temperatures in Celsius. For example,
```
     rex >  fahrToCel([212,32,-40]);
     [100,0,-40]
     
```
The conversion of individual temperatures is C = (F-32)*(5/9.0). In principle, this function is not different than add42List. In this case, however, use an anonymous function as a first argument to map.
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
    
```

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

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. Thus, collapse([1]) is [0].)

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.
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/as/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/as/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
    
```
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
    
```
The file insert.rex in the directory /cs/cs60/as/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, [], []]]]
  
```
The Unicalc Application

The last three problems are related to the "Unicalc" unit-conversion application.

The Unicalc application converts quantities expressed in one type of unit to those of another. The end result (not this week's assignment) will be able to do conversions like the following:
```
       rex >  convert( [1, ["mile"], ["hour"]], [1, ["meter"], ["second"]], db);
       multiply by 0.447032 or divide by 2.23698
```
Unicalc works on multiplicative conversions only, so it does not perform conversions such as Fahrenheit to Celsius.
Functional programming provides a natural way to implement the kernel of Unicalc. In this assignment, we walk through some of the data representations and issues, and ask you to write the first half of the code in rex. Here are the key representations used in Unicalc:
- A Quantity List is a list of three elements representing some quantity of a designated unit. For example,
```
       [1.0, ["mile"], ["hour"] ]                 represents 1 mile per hour
       [2.5, ["meter"], ["second", "second"] ]    represents 1 meter per second^2
       [60.0, [ ], ["second"] ]                   represents 60 hertz
       [3.14, [ ], [ ] ]                          represents about pi radians
       
```
  To summarize, a Quantity List is a list of three elements: the first is the quantity (floating point), the second is a list of units in the numerator, and the third is the list of units in the denominator. Note You can assume (and need to ensure) that the lists of units (numerator and denominator) are maintained in alphabetical order.
- A Conversion Database is a list of relationships between units. For example,
```
       db = 
       [
         ["foot",    [12.0,       ["inch"],   []]],
         ["mile",    [5280.0,     ["foot"],   []]],
         ["coulomb", [1.0,        ["ampere", "second"],     []]],
       ];
       
```
  Each line in the database is a list of two elements -- the first element is a string that names some unit and the second element is a Quantity List that is equivalent to that named unit.
  
  Not every unit is defined in terms of others in the database. Some are intentionally left undefined. We'll call the latter basic units. In the above example, inch, ampere, and second are basic units. A database does not need to contain conversions for everything to everything; that would tend to make it very large and maintenance would be error-prone. Instead, all conversions done by Unicalc are derived from basic ones in the database.
The representation of a quantity is said to be simplified if there is no element common to its numerator and denominator lists. A way to convert a quantity to an equivalent simplified form is to simply remove any pairs of elements common to its numerator and denominator. Write a rex definition for a function simplify of one argument (i.e., one quantity list) that yields a corresponding simplified representation. Consider using the merge example (/cs/cs60/as/a2/merge.rex) in order to take advantage of the fact that the numerator and denominator lists are sorted (though any technique that maintains the sorted order OK).

Some example uses of simplify include
```
  rex >  simplify([3, ["kg", "meter", "second", "second"], 
                      ["kg", "kg", "second"]]); 
  [3, ["meter", "second"], ["kg"]]

  rex >  simplify([3.14, ["meter", "second"], 
                         ["meter", "second", "second"]]);
  [3.14, [], ["second"]]
```

Construct rex functions multiply and divide that respectively multiply and divide two quantity lists, yielding a simplified result. For example:

  rex >  multiply([2.0, ["kg"], ["second"]], 
                  [3.0, ["meter"], ["second"]]);
  [6.0, ["kg", "meter"], ["second", "second"]]

  rex >  divide([12.5, ["meter"], ["second"]], 
                [0.5, ["meter"], []]);
  [25.0, [], ["second"]]

(Hint: don't rewrite simplify!)

As mentioned, the Unicalc database is represented as an association list, that is, a list of pairs in which each pair consists of a single unit and an equivalent quantity list for that unit. Essentially, these pairs define equations for various units, and we can refer to the elements of the pairs as the LHS (left-hand side) and RHS (right-hand side) for this reason. For example, a sample database might be defined as:
```
db = 
[
  ["foot",    [12.,       ["inch"],   []]],
  ["mile",    [5280.,     ["foot"],   []]],
  ["inch",    [0.0253995, ["meter"],  []]],
  ["hour",    [60.,       ["minute"], []]],
  ["minute",  [60.,       ["second"], []]],
  ["mph",     [1.,        ["mile"],                 ["hour"]]],
  ["coulomb", [1,         ["ampere", "second"],     []]],
  ["joule",   [1,         ["kg", "meter", "meter"], 
                          ["second", "second"]]],
  ["ohm",     [1,         ["volt"],                 ["ampere"]]],
  ["volt",    [1,         ["joule"],                ["coulomb"]]],
  ["watt",    [1,         ["joule"],                ["second"]]]
];
```
which happens to be the current contents of /cs/cs60/as/a2/unicalc_mini_db.rex (although this may change).
(The empty lists at the end of the first few lines above represent the denominators of the RHS. These can be seen as 1, or multiplicative identity, for the type of symbolic multiplication we use.)

If this were the entire database, we note that "meter" and "second" are both basic quantities, since they are not the LHS of any definition.

Write a rex function conv_unit that takes a string representing a unit and the database association list as arguments. If the unit is defined in the database, it returns that unit's equivalent quantity list, otherwise it returns a standard quantity list representing the unit: [1.0, [unitString], []]. For example, if db is the database consisting of the list of the pairs above, then:
```
  rex >  conv_unit("hour", db);
  [60, [minute], [] ]

  rex >  conv_unit("meter", db);
  [1, [meter], [] ]
```
Assignment 3 will use these functions in order to complete the unit-conversion application.
For optional bonus credit of 20%, write a function subsets(n,W) that takes as input a nonnegative integer n and a word (a string) W. It outputs a list of lists: the sublists are all the distinct subsets of the letters of W with n elements. The order of the letters inside these sublists is not important. It is important, however, that each of these sublists have a distinct set of letters from all the rest.

This function would allow a more efficient solution to problem number 11 on the previous assignment, as there are at most 140 different three-letter substrings formable from seven characters. (You do not have to redo that problem!)

Just as the order of the letters inside the sublists do not matter, neither does the order of the sublists themselves within the output. For instance,
```
      rex >  subsets(2,"abcd"); 
      [ [a, b], [a, c], [a, d], [b, c], [b, d], [c, d] ]

      rex >  subsets(2,"aacd") 
      [ [a, a], [a, c], [a, d], [c, d] ]

      rex >  subsets(2,"aaad") 
      [ [a, a], [a, d] ]

      rex >  subsets(5,"aacd") 
      [ ]
      
```