Comp 210 Lab 2: Simple data Structures

Index: Cases, Structured data, Design recipe, Exercises

In class, we've now seen two ways of structuring data, but have not gone through all steps of the design recipe for them. Let's do so.

Consider tax brackets as an example of a kind of data where a value fits into one of a few cases. This week, we stated that we should always write a "data analysis" of our data. Let's see how these two fit together in this example:

     ; A taxable-wage is one of
     ; - a number from 0 inclusive to 50 exclusive,
     ; - a number from 50 inclusive to 150 exclusive, or
     ; - a number equal or greater than 150.

This "x, y, or z" structure is very common, and we will take advantage of it in our design recipe.

In class, we've introduced the idea of structured or compound data. It uses a "x, y, and z" structure which is also very common. Let's quickly review it with another example.

How would you represent a point (in two-dimensional space)? High-school algebra and geometry tells us that a point consists of an x-coordinate and a y-coordinate in a Cartesian coordinate system, where each coordinate is a number. So, we would like to create a piece of data which is a pair of numbers. In addition to creating points, we also want to be able to look at the coordinates in a point, i.e., we need to be able to take a point apart again.

In Scheme, we can define compound data with define-struct, e.g.,

(define-struct pt_cart (x y))

Q: What functions does this define? (N.B. labbies: predicates (pt_cart?) have not been mentioned in lecture. Mention them now!) Give examples of pt_carts.

A: It defines...

• One constructor make-pt_cart that can be used like
  
  (define origin (make-pt_cart 0 0))
  
  (define apoint2 (make-pt_cart 5 7))
  
  
• A constructor constructs one of the indicated compound things, here a pt_cart, when given as many arguments as needed, here two.

Thus, the corresponding data definition is as follows:
A pt_cart is a (make-pt_cart x y), where x and y are numbers.

• Two selectors pt_cart-x and pt_cart-y that can be used like
  
  (pt_cart-x apoint2)
  (pt_cart-y origin)

  A selector selects the relevant piece of information from the compound thing, e.g., the "x" component of a pt_cart..

  Selectors are also called destructors or accessors.

• (Not mentioned in class...) One predicate pt_cart? that can be used like
  
  (pt_cart? origin)
  (pt_cart? 3)
  (pt_cart? (make-point2 3 8))

  A predicate determines whether or not its one argument is of the right form, here a pt_cart. Why would we use it? We'll see...

Q: What would be different if we had instead used the following?

(define-struct pt_cart (y x))

We will write some programs using points in just a minute.

We know our programs should take advantage of the structure of the data. Now that we know about two additional kinds of data that have more structure than arbitrary numbers:

• A "foo" is "x, y, or z".
• A "bar" is "x, y, and z".

To do: Follow the following steps for this example:

• Using pt_cart, write a function that computes the distance of a point from the origin. (Remember Pythagorus?)

And here's our newly expanded design recipe. (Note to labbies: Students haven't seen all these steps in class.)

1. Define your data.
2. Make examples of the data.
3. Write the function's contract, purpose, and header.
4. Make examples of the function's use.
5. Make a template for the function body. The template should remind you how to take advantage of the structure in the data definition.
   1. Use a cond expression with the same number of clauses as the data definition has cases. Use the appropriate predicates in tests for each case. (If the data definition has only one case, skip the cond.) In particular, consider the situation where you must differentiate between different data types.
   2. In each case, show the uses of selectors.

   Note: The template serves as a reminder to us of what the function probably looks like. We aren't obligated to use all or any of the selectors when writing a particular function.

6. Write the function body.
7. Test the function.

As in many labs, there are more exercises here than most students can do in one lab section. Do at least a representative sample of the exercises in lab and/or at home. We will continue with many other examples like these in lab, class, and homework. We recommend that you always try to do all the lab exercises, even if you run out of time during lab period.

Important for all exercises:

• Follow the design recipe.
• For each group of examples, use the same template, because the functions are on the same kind of data.
• Use DrScheme's stepper to help understand the programs.

To do:

1. Develop a program that computes the distance between two points in Cartesian coordinates.

2. Define a structure of vectors (in two-dimensional space):
   
   (define-struct vec2 ...)

   Q: A vector is also a pair of numbers, so why would we define pt_cart's and vec2's separately?

3. Develop a program that adds a point and a vector, returning a new point. Be sure to follow the design recipe.
   
   

4. Now consider a 2-D point in polar coordinates. That is, consider a point being defined by a radial distance from the origin, r, and an angle from the x-axis, theta. Write the definition of a data type called "pt_polar" that has a radius, r, and an angle, theta. Note: theta should be in radians.
   
   
5. Write a function that can take either a pt_cart or a pt_polar and return the distance of that point from the origin.
   
   
6. Write a function that can calculate the distance between two points, given any combinagtion of Cartesian or polar coordinates (i.e. one of each type or both the same type). Hint: Wouldn't it be easiest if both were in Cartesian coordinates? Ask for help if you don't remember your trigonometry.