Homework Five
Mutual Recursion, Two-argument functions, Accumulators

1. 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 resistance:
   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 circuit segments and resistances using the syntax used in class.
      Create appropriate predicates, selectors and constructors for your new data types using define-struct.
      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. We will develop the program mergesort, a way of sorting a list of numbers which is quite different than insertsort seen in class. Except as indicated, you don't need to write the data definition for list-of-Blah, however you do need to provide the contract and comments for each function, as well as additional test cases. 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: (mergesort (list 2 3 5 8) (list 1 7 9)) = (list 1 2 3 5 7 8 9).
      First write the template, then write the function. (Develop the program from the template; do not use the function insert from lecture.)
   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)).
   4. Write a function which repeatedly calls the previous function, until the list-of-lists contains only one item.
   5. Finally, write the function mergesort which takes a list of numbers, and returns a sorted list of numbers.

3. In the olympics, race times are often given in a relative form: an athlete's time isn't given directly, but as the difference from the preceding athlete. Write a function which takes a list of relative times, and returns a list of absolute times: For example the input (list 8.7 +0.2 +0.5 +13.4) yields the output (list 8.7 8.9 9.4 22.7).
   Use a helper function with an accumulator.