Assignment 7

Harvey Mudd College
Computer Science 60
Assignment 7, Due Monday, March 8, by 11:59 pm

Graphical programming in rex!

This is a slightly shortened assignment (due to the midterm in-class on Thursday). It's due at the usual time (11:59 pm on Monday, 3/8).

The problems in this assignment exercise rex's ability to specify functions that themselves return functions. In addition, it introduces data structures more complex than lists (trees and graphs), which in rex are necessarily implemented as lists. We will use these data structures in the next assignment as the basis for two interactive applications.

Reading

This assignment covers much of the material through Chapter 4 in the text. You may also want to experiment with functions returning functions and anonymous functions in rex.

Practice Problems

If you would like a few more practice problems to try either before or after the assignment, there are several (with solutions) in /cs/cs60/assignments/assignment7/practice.probs.

Submitting your code

You should submit your rex functions in a single file named hw7.rex using

  cs60submit hw7.rex

  cs60submitall

Grading

As in the previous assignments, commenting your functions and your file are important. Be sure your comments indicate what each function does, as well as what the inputs are.

As you gain experience writing code in rex, in addition, 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/assignments/assignment7. This file also provides an illustrative example of efficient tree-handling code using rex and recursion.

The Problems

Create a function named erdos which takes as input a single positive integer x (or whatever name you choose). (You don't need to check that it's a positive integer.) The output it computes is 3x + 1, in the case that x is odd, and x/2, in the case that x is even.
Appropriate runs include
```
    rex >  erdos(42);
    21

    rex >  erdos(109);
    328
    
```
Create a function named collapse(L) that takes a list L of positive 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].) Keep in mind that collapse takes a single list as input.

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." This problem is known as the Collatz problem or "3x+1" problem -- if you're in the hallways of Pomona's math department, you'll find a poster on this problem and what's currently known about it displayed on the wall! Check out the site http://www.paulerdos.com/0.html for more on Paul Erdos.
Write a function iterate(N, F, X), taking as input a non-negative integer N and a function F (which will always be a function of one integer argument), and an integer X. The function iterate then returns the result of repeatedly applying F on the input X a total of N times, i.e., 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, among other places, in generating fractal images.) If N is 0, iterate 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),
  //   and erdos(3) equals 10.
  
  rex > iterate(1, erdos, 3);
  10

  // 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 anonymous function below two times is equivalent to adding 2.

  rex > iterate(2, (x)=>x+1, 9);
  11
  
```
This problem will borrow heavily from the last one! Write a function iterate(N, F), taking as input a non-negative integer N and a function F (which will always be a function of one integer argument). The function iterate then returns a function of one input that is equivalent to calling F on that input N times, i.e., F(F(F...(F(X)))) where the number of F's is equal to N. The only difference from the previous problem is that iterate, when it has two arguments, will return a function, instead of a resulting value. Note that rex, like Java, considers functions with the same name but different numbers of arguments (like iterate to be completely different functions). This is called overloading.
```
  // Here I'm using the erdos function from the example above.
  //   since the first argument is 1, the desired result is erdos(3),
  //   and erdos(3) equals 10.
  
  rex > iterate(1, erdos)(3);
  10

  // 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 > e3 = iterate(3, erdos);
  1

  rex > e3(3);
  16

  // Iterating the anonymous function below two times is equivalent to adding 2.

  rex > iterate(2, (x)=>x+1)(9);
  11
  
```
The above iterate function allows the following round-about means of implementing addition (which corresponds to the usual elementary-school definition of +) :
```
  rex > ADD(n) => iterate(n, (x)=>x+1);
  1
  
```
where ADD(n) now returns a function that adds n to its argument:
```
  rex > ADD(42)(100);
  142
  
```
For this problem, use iterate and ADD to define the MULT(n) function, which returns a function that multiplies its inputs by n. (You will have to add the above definition of ADD to your file in order that REX can use it.) Like ADD, MULT should be able to handle all nonnegative integers (including 0). For instance,
```
  rex >  m10 = MULT(10);
  1

  rex >  m10(42);
  420;

  rex >  MULT(19)(17);
  323
  
```
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, and returns the larger of F(X) and G(X). To be precise, here greater means further toward positive infinity (not "greater in magnitude," which would work differently for negative numbers). Aldo, 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
    
```
This problem and the following one ask you to write rex functions that operate on another data structure -- directed graphs -- in particular, graphs that are represented as a list of [parent, child] pairs. The graphs are called directed, because each edge points in only one direction: an edge from A to B does not mean there is an edge from B to A.

Create the function biggestFan(G) that takes a directed graph G (as a binary relation) as input and outputs the node of G that has the biggest fan-in. The fan-in of a node is simply the number of parents of that node, so biggestFan returns the node with the most parents. You may assume that biggestFan will only receive input graphs that do have at least one edge.

If there is a tie for the biggest fan-in, you may return any one of the correct nodes. For example:
```
    rex >  biggestFan([ ["A","D"], ["B","D"], ["C","D"], ["A","E"], 
	                ["D","E"], ["E","F"], ["F","A"]  ]);
    D
    
    rex >  biggestFan([ ["A","B"], ["B","C"] ]);
    B
    
```
where the last answer could also have been C.
(Recall that a predicate is simply a function whose output is 0 or 1, that is, true or false.) Write a predicate reachable(a,b,G) that answers the question of whether or not you can get from "point a" to "point b" in the directed graph G. Specifically, the first two inputs to reachable are nodes in the graph G, and the graph itself is the third input. reachable returns 0 if there is no path from a to b, and it returns 1 if there is a path (possibly through other nodes) from a to b.

NOTE Your predicate will only be given ACYCLIC graphs as input. Thus, you don't have to worry about "running around in circles" searching for whether there is a path from a to b, because there will be no cycles in the graph. Also, remember the graphs are directed. For example,
```
    rex >  reachable("A", "F", [ ["A","D"], ["B","D"], ["C","D"], ["A","E"], 
	                ["D","E"], ["E","F"] ]);
    1
    
    rex >  reachable("C", "A", [ ["A","B"], ["B","C"] ]);
    0
    
    rex >  reachable("D", "D", [ ["A","B"], ["B","C"] ]);
    1
    
```
As the last example illustrates, your function should acknowledge that any node can be reached from itself. What's more the node does not even need to be in the graph! (This is because the graph does not have to be connected -- an unlisted node is one with neither outgoing nor incoming edges.)
The file insert.rex in the directory /cs/cs60/assignments/assignment7/ 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

We will go over the algorithm for removing an item from a binary search tree in detail in class. As a brief reminder, the problem is "straightforward" (not a value judgment!) if the node to be deleted has zero children or one child. If it has two children, replace the note to be deleted with the next largest node in the tree.

For example, here is an example:
```
  rex > mytree = [10, [3, [], []], [42, [20, [], []], [60, [], []] ] ];
  1

  rex > delete(10, mytree);
  [20, [3, [], []], [42, [], [60, [], []]]]
  
```
Hint: you will need to write a function that finds the minimum element in a binary search tree. (Code for findMin will be written in class.)

For optional bonus credit of 5%, write a function sublists(L) that takes as input a list L and produces as output a list of all sublists of L. You may assume that L contains only distinct elements, so that you don't need to worry about repeating sublists. Your sublists (which need to be collected into a single big list for output) may appear in any order and do not have to be sorted. They just all need to be there!

Note that a variant on tHis function would allow a more efficient solution to the bestThree problem 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!)

For instance,

      rex >  sublists([1]); 
      [ [], [1] ]

      rex >  sublists([42,100]);
      [ [], [100], [42], [42,100] ]

For an alternative (or additional) optional bonus credit of 5%, write a function readInteger(x) that takes in a positive integer x and outputs the number formed when the input is "read" digit-by-digit. This is the principle behind the sequence 1, 11, 21, 1211, 111221, ... . You can use readInteger to determine when the digit '4' first appears in the above sequence. For this problem you may want to use the rex built-in function make_string that converts integer inputs to equivalent string outputs.