Comp 210 Lab 2: Data Structures

Index: Structured data, Lists, Design recipe, Exercises

In class, we've introduced the idea of structured or compound data. 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, 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 point2 (x y))

• One constructor make-point2 that can be used like

       (define origin (make-point2 0 0))
       (define apoint2 (make-point2 5 7))
       

  A constructor constructs one of the indicated compound things, here a point2, when given as many arguments as needed, here two.

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

• Two selectors point2-x and point2-y that can be used like

       (point2-x apoint2)
       (point2-y origin)
       

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

  Selectors are also called destructors.

• One predicate point2? that can be used like

       (point2? origin)
       (point2? 3)
       (point2? (make-point2 3 8))
       

  A predicate determines whether or not its one argument is of the right form, here a point2.

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

     (define-struct point2 (y x))

Q: How would you define a point in three-dimensional space?

We will write some programs using points after reviewing the design recipe.

A list is a common data structure for keeping track of an arbitrary amount of information. Lists use both of the two basic building blocks we've seen:

• compound data, as for plane brand descriptions or points, and
• recursion, as for natural numbers.

     ; a list-of-symbols is one of
     ;   - empty
     ;   - (make-lst f r), where f is a symbol, and r is a list-of-symbols
     (define-struct lst (first rest))

• the constructor make-lst,
• the selectors lst-first and lst-rest, and
• the predicates empty? and lst?.

(Note: We sometimes intentionally misspell words like lst to avoid redefining built-in Scheme functions.)

Using lists is so common that Scheme has these functions built in, except using some different names. Instead, write

     ; a list-of-symbols is one of
     ;   - empty
     ;   - (cons f r), where f is a symbol, and r is a list-of-symbols

• the constructor cons,
• the selectors first and rest, and
• the predicates empty? and cons?.

We know our programs should take advantage of the structure of the data. Now that we know about compound (or structured) data, let's use that knowledge in our methodology.

1. Formulate a data definition.
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.)
   2. In each case, show the uses of selectors.
   3. In each case, show the uses of natural recursion.

   For example, the template for a function on list-of-symbols is

        (define (los-fun a-los)
           (cond
              [(empty? a-los) ...]
              [(cons? a-los)  ...(first a-los)...(los-fun (rest a-los))...]))
        

   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 or recursion 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 some of the exercises from each group during lab, and the rest on your own. We will continue with many other examples like these in lab, class, and homework.

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.

Points

To do:

1. Develop a program that computes the distance from a point to the origin.

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 point2s and vec2s separately?

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

Lists of numbers

To do:

1. Make the data definition for lists of numbers.
2. Develop a program which takes a list of numbers and returns the length of the list, i.e., a count of the items in the list. Consider: How many numbers are in (cons 3 (cons 1 empty)), for example?
3. Develop a program which takes a list of numbers and returns the sum of all the numbers.
4. Develop a program which takes a list of numbers and returns the product of all the numbers.

Database

Let's build an example using lists of more interesting data.

To do: First, copy the following into a file db.ss.

     ; Some basic constants: 
     (define MAX-SALARY 1000000)
     (define MIN-SALARY   20000)

     (define MIN-AGE 18)
     (define MAX-AGE 65)

     ; A database record is
     ;   (make-record name age salary
     ; where name is a symbol)
     ;       age is an integer between MIN-AGE and MAX-AGE (inclusive)
     ;       salary is an integer between MIN-SALARY and MAX-SALARY (inclusive)
     (define-struct record (name age salary))

     ; A database is a list of database records, i.e., one of
     ;   - empty
     ;   - (cons f r)
     ;     where f is a database record, r is a database

1. Create an example database.
2. Develop db-count, which takes a database and returns a count of those employees who are older than 22 and earn more than 100000.
3. For the curious... Develop db-search, which takes a database and returns a list of those same employees (in the order they appear in the database).