Exercises with invariants

For these exercises, remember that your purpose statement, including its invariant, is at least as important as your function definition.

When you are called on, please copy your solution into one of the following pages:

• solutions-1
• solutions-2

1. Consider the following constructor template for binary trees:

   A Bintree is one of
   -- (make-leaf-node Number)
   -- (make-tree-node Number Bintree Bintree)
   

   First, complete the data definition for Bintree by writing the struct definitions and the observer template.

   Then, design a function called tree-with-sums-in-leaves which, given a Bintree, returns a Bintree like the original, except that each leaf node is replaced by the sum of all the numbers on the path from the root to the leaf.

   Example:
   #(struct:tree-node 3
      #(struct:tree-node 4
         #(struct:leaf-node 5)
         #(struct:leaf-node 10))
      #(struct:leaf-node 2))
   
   =>
   
   #(struct:tree-node 3
      #(struct:tree-node 4
         #(struct:leaf-node 12)   ; 3 + 4 + 5 = 12
         #(struct:leaf-node 17))  ; 3 + 4 + 10 = 17
      #(struct:leaf-node 5))      ; 3 + 2 = 5
     

   You'll need a help function. Make sure you give a suitable contract, purpose statement, and invariants both for tree-with-sums-in-leaves and for your help function.

2. Do the same thing, except for the data type defined by the constructor template

   A Tree is a
   -- (make-tree Number ListOfTree)   
   
   A ListOfTree is one of
   -- empty
   -- (cons Tree ListOfTree)
   

   For these trees, we define a leaf to be a tree with an empty list of daughters.
3. You are writing code for a navigation program. You are to write a function called distances-so-far which, given a list of point-to-point distances, produces a list of distances to be displayed as "distance travelled so far"

   EXAMPLE: Say there are 4 points on the route, called A, B, C, and D.
   D is the destination.  The distance from A to B is 10, from B to C is
   2, and from C to D is 5.  For this route, the input to your function
   is the list
   (10 2 5)
   and your function should return the list
   (0 10 12 17)
   

   As before, make sure you give a suitable contract, purpose statement, and invariants both for distances-so-far and for your help function.

4. You are writing the code for sending data back from the Pluto rover. The data consists of a list of integers, but the data contains many runs of identical values. So rather than sending a list with 365 consecutive zeros, you'd like to send a single message saying "insert 365 zeros here". Here's a more detailed specification:

   ;; A Count is a Positive Integer
   
   (define-struct rep (value count))
   ;; A Rep is a (make-rep Integer Count)
   ;; (rep v c) represents the list (v v v v v ..)  c copies of v
   
   ;; compress : ListOfInteger -> ListOfRep
   ;; Compresses the given input by replacing each run of consecutive v's
   ;; by (rep v k)
   
   ;; EXAMPLES:
   ;; () => ()
   ;; (30 30 20 20 20 20 50 30 30) =>
   ;;  (list (make-rep 30 2) (make-rep 20 4) (make-rep 50 1) (make-rep 30 2))
   

   You'll need a help function. Make sure you give a suitable contract, purpose statement, and invariants for your help function.