Homework Five
Mutual Recursion, Two-argument Functions

1. (5pts) Mutually Recursive Data Definitions An electrical engineer often needs to find the total resistance of a part of an electrical circuit. In general, circuits can contain resistors, capacitors, inductors, etc. This example will only consider segments of a circuit that contain combinations of resistors. (Note: don't conflate resistors with resistances. The former is a particular type of circuit segment; the latter is a property of all circuit segments.)

   Here is the informal description of the inputs that your programs will process.

   A circuit segment can be either a resistor, a serial segment, or a parallel segment.

   A (simple) resistor has only one interesting property: a resistance, which is a real number greater or equal to 0.0, or the symbol 'infinity.

   A serial segment consists of an arbitrary number of segments connected in a row: (see postscript for picture).
   The total resistance of a serial segment is the sum of the individual resistances. In other words, the entire segment behaves like a single resistor with that total a total resistance of
   R_seg = Sum_i=1ⁿ (R_i)
   If one of the segments in the series has infinite resistance, then
   R_seg = 'infinity

   A parallel segment consists of an arbitrary number of segments that are connected to a common starting and ending point (see postscript for picture).
   The total resistance of a parallel segment is the inverted sum of the inverted resistances of the segments:
   R_seg = 1 / Sum_i=1ⁿ (1/R_i)
   If one of the segments has no resistance, then the total resistance is just 0; if one of the segments has infinite resistance, that segment contributes nothing to the sum of inverses. If all of the segments have infinite resistance, i.e., the sum above is 0, then the whole parallel segment has inifinite resistance.

   1. Write up a rigorous data description for resistances and for circuit segments¹.
      Use define-struct to have the appropriate predicates, selectors and constructors created for your new data type.
      Define templates for segment-processing and resistance-processing functions.

   2. Derive the functions plus, times, and inverse, which accept resistance(s) and compute the following results:
      • plus computes the sum of two resistances. If one is 'infinity, the sum is 'infinity, too.
      • times computes the product of two resistances. If one is 'infinity, the product is 'infinity, too.
      • inverse computes the inverse of a resistance. If the resistance is 0, the result is 'infinity; if it is 'infinity, the result is 0; and otherwise, it is the inverse of the number.
      (What is the contract, in each case?)
      Evaluate the expression (inverse (plus (inverse 'infinity) 10)) by hand (showing the calls to functions you've defined -- four lines total).

   3. Derive the program resistance, which accepts a cicuit segment and computes the total resistance of the segment. Hints: (1) The program consists of many functions. (2) Some functions need to compute arithmetic expressions involving resistances. Use the functions plus, times, and inverse instead of +, *, and /. (3) As possible, test every function individually before you test the complete program.

2. (5pts) Functions with Two Complex Inputs We will develop the program mergesort, one way of sorting a list of numbers. Except as indicated, you don't need to write the data definition for list-of-Blah, however you do need to provide examples of the data, contracts for each function, and show testing of each function (two to three tests per function, including trivial inputs). Test each function individually, as you complete it.
   1. Write a function which takes a list of numbers, and returns a list of one-element lists:
      the input (list 2 5 8 3 9 7 1) yields output (list (list 2) (list 5) (list 8) (list 3) (list 9) (list 7) (list 1)) .
   2. The heart of mergesort is the function merge, which takes two already-sorted lists of numbers and returns a single sorted list.
      Example: (merge (list 2 3 5 5 8) (list 1 7 9)) = (list 1 2 3 5 5 7 8 9).
      After Friday's lecture, First write the template for a function which takes two lists. Then write the function. Hint: take advantage of the fact that both your input lists are each sorted. What piece of the template is guaranteed to be the first element of the result? (Develop the program from the two-argument template; using a different template leads to a different method of sorting. We'll discuss the differences in lab one day...)
   3. Write a function which takes a list-of-list-of-numbers, and repeatedly calls merge on successive pairs, returning a list-of-list-of-numbers. For example, the input (list (list 2 5) (list 3 8) (list 7 9) (list 1)) yields output (list (list 2 3 5 8) (list 1 7 9)). Similarly, (list (list 2 5) (list 3 8) (list 7 9)) yields output (list (list 2 3 5 8) (list 7 9)). (You'll write some other even easier example test cases, of course.)
   4. Write a function which calls the previous function repeatedly, until the list-of-lists contains only one (or fewer) items.
   5. Finally, write the function mergesort which takes a list of numbers, and returns a sorted list of numbers.

Myself, I prefer the arbitrary-number-of-segments phrasing, since it better reflects how I think about the problem: I actually do think about circuits with three segments in parallel -- i don't want to bend my thinking to conform to a program which only knows nested arrangements of bi-parallel segments.
(back)