COMP 210 Lab 3: Lists

This lab is mainly practice with lists. There are too many examples here to do all during lab. Instead, do some from each group during lab, and the rest on your own. We may revisit some of these examples in next week's lab, also.

Important for all examples:

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

Index: A new flavor of define, Definition and Design Recipe Review, Lots of Examples

Labby note: Just skim this section.

We saw in lecture a new way to use define. Our original usage, if you think about it, really does two separate things:

     ;; circle-area: number -> number
     (define (circle-area r)
       (* pi (* r r)))

The new way to use define actually is simpler: it simply associates a name with a value (not (necessarily) a function).

     (define speed-limit 55)
     (define international-greeting 'hello)
     (define my-favorite-number (+ 15 2))
     (define my-favorite-ppg (make-ppg 'Buttercup 'green 90 ))

All placeholders do is save us typing. Whereever in a program you see speed-limit, you could conceivably re-write the program to use 55, and the program's behavior will be the same. Thus it's a handy way to save typing of structures (like ppgs, which are tedious to type). Nothing else mysterious happens.

Note that use of placeholders is important in both

• having your program reflect how you think of the problem, and
• single point of control.

These two uses of define are certainly related -- the function version does extra work of creating a function, but after that they are identical: If you think of functions as just being another type of value (in addition to numbers, symbols, Booleans, and structures), then in either case, a placeholder is being associated (bound) to a value.

Note for the curious

We'll see later how to create a function without needing to give it a name.

Summary of define syntax

•        (define (placeholder parameters...)
            body-expression)
         

  The placeholder is the function name. The body-expression can be any expression, presumably involving the parameter.

•        (define placeholder expression)
         

• Understanding the data definition for a list-of-symbols (constructors, selectors, predicates).
• Typing in examples of a list-of-symbols, and extracting pieces therefrom.
• Writing a function processing a list-of-symbols (of any length!)
  (...using examples from more lecture notes)
• Understanding the revised Design Recipe, having now added recursive data definitions.
• Using the stepper to come to grips (intellectually and emotionally) with recursion.
• Practice.

Now, let's quickly review our latest design recipe. We know our programs should take advantage of the structure of the data; recursive data implies recursive functions.

Steps depending only on the data:

• 1. Data definition: How, exactly, do you represent the problem in terms of Scheme data?
• 2. Data examples.
• 3. Template: The part of the function which reflects the structure of the data.
  1. Case analysis: If your data has various cases, include a cond -- one branch per case of data. (Note: Write all the cond questions first, to distinguish the data. We fill in the particular answers only when we have a particular function (step 6).)
  2. Data extraction: If your data is a structure, your code will be using the various selectors for that structure, like a good craftsperson or artisan inspecting what tools are available to complete the task with, before launching in blindly.
  3. new Natural recursion: For each of the pieces from the previous step, ask yourself what type of data it is, and call an appropriate funciton. If the sub-datum's type is the same as the input of the entire function, this suggests a recursive function.

Steps depending on the function:

• 4. Function contract, purpose, header.
• 5. Function test cases: Use your previously-written data examples.
• 6. Function body: Copy the template. Since there is one template per data-definition, you often have many functions based on the same template.
• 7. Function testing: Use your previously-written test cases.

There are many more examples here than you can do in lab. Labbies can pick and choose what to present. Students should look over the rest on their own.

Lists of numbers

Databases

We've seen lists of symbols and lists of numbers; you can of course have a list with elements of any given type ... including other structures like villains. This just uses ideas you've already learned, but in new contexts. Stick to the design recipe, to avoid confusion!