Homework Four
User-Defined Data Types

1. Write a function next-floor to control an elevator. next-floor takes three arguments: the direction the car was just going (either 'up or 'down), the current floor number (an integer), and a list of requested floor numbers sorted in ascending order. next-floor returns the next floor to which the elevator should move. If the list of requested floors is empty, next-floor should simply return the current floor.

   To further test your controller, we have written an elevator simulator. To load the code for the simulator into DrScheme, use the ``Select Library'' command to load the library /home/comp210/lib/teach/elevator-lib.ss To start the elevator, simply type the command

         (run next-floor)
   

   after defining your function next-floor.

   The simulator displays a picture of the elevator. Clicking on call buttons adds floors to the request list. (The up and down buttons behave identically.) The simulator calls your function next-floor repeatedly to decide the next floor to be visited.
   Hint: You can check out the simulator immediately by writing a very simple next-floor function. For example, have next-floor always return the first floor on the request list, or use this very silly definition:

         (define next-floor
           (lambda (direction current-floor floor-requests)
             3))
   

   This allows you to get started and see what the elevator looks like.

   Be sure that your elevator controller is fair. Every requested floor should eventually be visited, regardless of the other requests in the list.
   Hint: Split the list of requested floors into two parts, those floors above the current floor and those below. Use data definition and program templates to derive appropriate helper functions for processing these two pieces.

2. In the context of family trees (from lecture), we define a leaf as a child¹ where both parents are unknown (null). Write the function count-leaves. Write a few small test cases yourself; here is a medium-sized test case.

   For a family tree with three children, what is the maximum number of leaves it might contain? The minimum number? How about a family tree with seven children?
   For a family tree with n children, what is the minimum and maximum number of leaves it can contain?
   (You can give your answers in comments, after the test-cases for count-leaves.)

3. Arithmetic expressions are one of the fundamental components of most programming languages. We can define arithmetic expressions, <ArithExp>, recursively as follows:

   <ArithExp> ::= (Real value) |
                  (Plus  arg1 arg2) |
                  (Times arg1 arg2)
   

   where value is a <number> (that is, a number) and arg1 and arg2 are <ArithExp>s.

   • Use define-structure to build constructors, selectors, and predicates for arithmetic expressions. Be sure to follow the naming conventions described in class. List the names that Scheme assigns to these constructors, selectors, and predicates.
   • Write a function eval that takes as input an arithmetic expression and returns its value as a number. As always, include your data definition, program template, completed program, and test data.
   • Write a Scheme function make-sum that takes as input a proper (i.e., non-empty) list of numbers and returns as output an arithmetic expression denoting their sum. Your function should use the constructors defined in the first part of this problem. Include your data definition, program template, test data, and completed program.

     Note: The sum should stay unevaluated. If your input list contains seven numbers, the resulting arithmetic expression should consist of six uses of the constructor for Plus applied to seven uses of the constructor for Real; it should not be just a single use of the constructor for Real.