Cluster 5 * Summer 2004
Computer Science Through Games and Scheme Programming
David G. Kay, Dan Frost, Kevin Papke

Scheme Lab Activities: Fourth Set

1. We talked in class about multiple-valued data: Homogeneous (all-one-type), which we build in Scheme with lists, and heterogeneous (a collection of possibly different types of data), which we build in Scheme with structures. You've seen these both in the restaurant program, but now let's look in more detail at how they work.


2. In the restaurant program, we use a structure to store the information about a restaurant. (Those familiar with object-oriented programming can think of a structure as a light-weight class.) We define a structure--we give the blueprint for building restaurant objects--with define-struct (you can find this line in the restaurants program):
      (define-struct Rrant (name cuisine phone dish price))
   This says, "To build a restaurant object, you need five fields (five compartments for holding five different data items). We'll use the name Rrant to refer to the category or class of restaurant objects; we'll use the words name, cuisine, phone, dish, and price to refer to the five fields."
   The structure definition above doesn't say what the five fields represent, but we need to be clear about it: In order, they're the name of the restaurant (a string), the restaurant's cuisine (the kind of food they serve, a string), their phone number (a string, since it might have parentheses and a hyphen in it), the name of the best dish they serve (a string), and the price of that dish (a number).


1. When we enter that definition, Scheme automatically creates for us:


1. A constructor, make-Rrant, for building new restaurant objects:
   (make-Rrant "McDonalds" "burgers" "343-4344" "French Fries" "1.95")


2. Accessor/selector functions for each of the five fields:
   (define R1 (make-Rrant "Pascal" "French" "343-4343" "Escargots" "9.95"))
   (Rrant-name R1), which returns Pascal
   (Rrant-cuisine R1), which returns French, and so on.


3. And a couple of other functions that we don't need to worry about now.


2. Because structures can take so many different forms, there's no automatic way that would effectively print out every structure. So it's useful for us to write a function that prints out our structure's contents clearly:
   (define Rrant-print
     (lambda (r)
     (display "Name: ") (display (Rrant-name r)) (newline)
     (display "Cuisine: ") (display (Rrant-cuisine r)) (newline)
     (display "Phone: ") (display (Rrant-phone r)) (newline)
     (display "Best dish: ") (display (Rrant-dish r)) (newline)
     (display "Price: ") (display (Rrant-price r)) (newline)))
   To save some space above, we have combined two displays and a newline on each line.


3. Write a definition for the function Rrant-cheap? that takes a restaurant (i.e., an Rrant structure) as its input and returns true if the restaurant's (best dish's) price is less than $10.00 and false otherwise. Test your function well (which should involve defining a few restaurants and using them as arguments to Rrant-cheap?).


4. The $10.00 figure above is an arbitrary constant. We'd have a more flexible function if we could specify the threshold as an input (argument, parameter) to the function. So write the function Rrant-cheap2? that takes two arguments, a restaurant and a number, and returns true if the restaurant's price is less than the specified number (and false otherwise).


5. Write a function called Rrant-increase-price that takes a restaurant and a number as its input and returns a restaurant that's identical to the input restaurant except that its price is increased by the number. (Do this functionally, by creating a new restaurant structure with the field values from the old structure, except for the changed price.)


6. Write a function called Rrant-change-price that takes a restaurant and a number and returns a restaurant with its price field increased or decreased by the number (positive or negative). Before you start coding, think about the functions you have already defined. Can you do this simply by changing a name?


7. Write a function called Rrant-same-cuisine? that takes two restaurants and returns true if their cuisine fields are the same (use the function equal? to compare the strings) and false otherwise.


3. Now let's look at lists.


1. Scheme gives us these two constructors for lists:


1. list, which takes its arguments and combines them into a list
   (list 3 4 5) returns (3 4 5)


2. cons, which takes an item and a list and creates a new list by inserting the item at the front of the original list
   (cons 3 (list 5 7)) returns (3 5 7)
   (cons 3 empty) returns (3)
   (cons (list 1 2) (list 3 4)) returns ((1 2) 3 4)
   Take a minute to make sure you get that one.


2. Scheme gives us these two accessors for lists:


1. first, which takes a list and returns its first item


2. rest, which takes a list and returns the list with its first item removed (but note that it doesn't actually change its input; it just returns a new, different copy)


3. Scheme gives us these two other useful functions for lists:


1. empty?, which takes a list and returns true if it's empty and false otherwise (also called null?)


2. length, which takes a list and returns the number of elements in the list.


4. One way of describing a list is like this: A list is either:
   -- empty, or
   -- (cons item list)
   So empty is a list, because it's right there as one part of our definition. ("Hi") is a list because it's the same as (cons "Hi" empty); this follows from the second line of our definition because we already know empty is a list. ("Oh" "Hi") is a list because it's the same as (cons "Oh" (cons "Hi" empty)), and we already know (cons "Hi" empty) is a list. And so on. This pattern helps us write functions that process lists.


5. How do we write a function that processes all the items on a list? Suppose we want to write a function called double-a-list that takes a list of numbers as its input and returns a list containing each number from the original list, doubled.
   We already know how to take a single number and double it:
   (define double
      (lambda (n)
        (* 2 n)))
   We can use the pattern above to apply this function to each item on the list, in turn:
   ; double-a-list: list of numbers -> list of numbers
   ; Take a list of numbers and return a list with each number doubled
   (define double-a-list
    (lambda (L)
     (cond
     ((empty? L) empty)
     (else (cons (double (first L)) (double-a-list (rest L)))))))
   ; Examples
   (double-a-list empty) "Should return" empty
   (double-a-list (list 3 4 5)) "should return" (list 6 8 10)
   Let's take this a line or two at a time.


1. The first two lines (starting with semicolons) are comments--English annotations to the human reader that don't have any effect on the computer's actions.


1. We call the first line the "contract": It gives the name of the function, the type of data each argument will be, and the type of value that it will return.


2. The second line describes the purpose or semantics of the function.


2. The define, lambda, and cond lines should be familiar.


3. The two cond clauses match the two lines of our pattern.


1. The ((empty? L) empty) line says that if the list we're looking at is empty, there's nothing to double--the result we should return (if we're trying to double all the elements on an empty list) is just the empty list itself.


2. The else line says that if the list isn't empty, then we know it's made up of an item and a list, just as the pattern says. What we need to do for our new list is double the first item (double (first L)), and then do this process all over again on the rest of the list (double-a-list (rest L)).
   Does it bug you that we call the function double-a-list from within its own definition? Doesn't it seem as if that kind of circular definition could get us in trouble? It could, but in this case it doesn't, because the definition isn't truly circular. It's more of a spiral, because each time we repeatedly call double-a-list, it's with the rest of the current list--that is, we keep calling with smaller and smaller lists, and eventually we'll call it with empty. When that happens, we'll do the first line of the cond and we'll stop repeating.
   This process is called recursion, and it's an extremely powerful idea that we'll see again and again.


4. The two example lines have been cleverly constructed so that if you run them, they serve as tests of the function's operation. Go ahead; copy the whole definition into DrScheme and click Execute.


6. Write the function exponentiate that takes two arguments, a list of numbers and a single number, and returns a list with the original numbers all raised to the power of the single number.
   (exponentiate (list)) "should return" empty
   (exponentiate (list 4 3 2 1) 2) "should return" (16 9 4 1)
   (exponentiate (list -2 0 3) 3) "should return" (-8 0 27)


7. Suppose we have a list of restaurant objects as defined above. For processing purposes, that's no different than a list of numbers. The structure of the list is the same; it's just each item that's a little bigger. If we know how to process an item, we know how to process a list of them.
   Write the function change-prices that takes a list of restaurant objects as its input and returns a list of the same restaurants, but with each restaurant's price increased by $2.00.

COSMOS Cluster 5 Home * COSMOS UCI Home

Tuesday, July 13, 2004 -- 1:08 PM