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

Scheme Lab Activities: Sixth Set

1. Many of you won't have finished Lab 5. That's fine; everyone should finish up Lab 5 before working on this one.


2. In class on Wednesday we talked about three functions--map, filter, and reduce (which is called foldr in DrScheme). There's a fourth function that goes with these, called for-each. Here is a summary


1. (map F L), where F is a function and L is a list, applies the function F to each item in L and returns a list of all those results.


1. (map odd? '(1 2 3 4 5)) returns (#t #f #t #f #t); odd? is a built-in function that returns true if its argument is an odd number.


2. (map Rrant-name RL), where RL is a list of restaurant objects, returns a list of the names of all the restaurants in RL.


2. (filter P? L), where P? is a predicate function (that returns true or false) and L is a list, returns a list of all the items in L for which P? returns true.


1. (filter odd? '(1 2 3 4 5)) returns (1 3 5).


2. (filter cheap? RL), where cheap? is the function we defined in class and RL is a list of restaurant objects, returns a list containing just those restaurant objects in RL that are cheap (i.e., have a price field less than 10).


3. (foldr OP INIT L), where OP is a function that takes two arguments, INIT is an initial value, and L is a list, returns the single value obtained by applying OP in succession to all the values in L (using INIT as an initial or default value).


1. (foldr + 0 '(1 2 3 4 5)) returns 15, which is 1+2+3+4+5.


2. (foldr + 0 '()) returns 0


3. (foldr * 1 '(L W H)) returns the volume of a rectangular solid represented by length L, width W, and height H (by multiplying those three values together). This is just meant as an illustration; it's no better than (* L W H).


4. (foldr cons '(TheEnd) '(Huey Dewey Louie)) returns the list (Huey Dewey Louie TheEnd) (by consing the individual values together).


4. (for-each F L), where F is a function and L is a list, applies the function F to each item in L. We only use for-each in cases where F displays something or draws something in a graphics window; we don't use for-each to get the value it returns (for that purpose, we have map).


5. Those who are curious might experiment with the function foldl--that's "fold" plus "L". How are its results different from those of foldr? (Hint: Try the four examples above.)


3. Using foldr, map, and filter, you can define many powerful operations very compactly, without explicit recursion. For example, suppose we have a list of restaurant (Rrant) structures as we've used in class; call that list RL. To produce a list of the names of the cheap Thai restaurants in RL, we only need to say
   (map rrant-name (filter cheap? (filter Thai? RL))).
   To calculate the average price of the cheap Thai restaurants, we can say
   (let ((cheap-thai-restaurant-prices
          (map Rrant-price (filter cheap? (filter Thai? RL)))))
      (/ (accumulate + 0 cheap-thai-restaurant-prices)
        (length cheap-thai-restaurant-prices))).
   (In the above example, note that using the let expression saves us from computing the list of prices two separate times.) If you have trouble figuring out how these expressions work, first make sure you understand map, filter, and accumulate individually (look at the examples above) and then look at what each part of the expression returns, starting from the inside out.


1. Write the function convert-to-1 that takes one argument (of any type) and returns the number 1, no matter what the argument is. Next, use map and convert-to-1 to define the function list-of-ones that takes a list of items and returns a list of 1s that's the same length as its argument. Finally, use foldr and list-of-ones to rewrite the last line of the average-price code above without using length.


2. What is the result of evaluating each of these expressions? The point is not just to get the answer but to work them out in your head to test your understanding. Don't copy them into DrScheme and run them until you're ready to check your work. (The second one uses an "anonymous lambda," which we saw at the very end of Wednesday's class. Remember that a lambda expression is just an expression whose value is a function--a machine that takes some inputs and produces some outputs. We can pass that machine around for other functions to use, just like lending a power tool to your neighbor.)
      * (foldr + 0 '(1 2 3 4 5))
      * (foldr (lambda (a b) (+ b (if (even? a) a 0))) 0 '(1 2 3 4 5))
      * (foldr cons '() '(Huey Dewey Louie))
      * (foldr max -1 '(1953 1956 1949 1991 1964))


3. Assume you have a function (interval a b) that returns a list of all the integers between a and b, inclusive (so that (interval 5 10) would return (5 6 7 8 9 10)). (Re-)write the function factorial using accumulate (and interval), without any explicit recursion.


4. Now, think back to the restaurant database program and assume we have a standard Lisp list (called RL) of the restaurant objects as described there. For each of the following expressions, describe in one English sentence what value it returns. Don't just say, "It does a accumulate of zero and plus to a map of ... ;" give a description of what the expression means, something you could put in a software catalog so that a prospective buyer could find what he or she wanted.
      * (foldr + 0 (map (lambda (R) 1) RL))
      * (filter (lambda (R) (equal? 'Ethiopian (Rrant-cuisine R))) RL)
      * (/ (foldr + 0 (map (lambda (R) (Rrant-price R)) RL))
        (foldr + 0 (map (lambda (R) 1) RL)))
      * (let ((PRL (filter (lambda (R) (equal? 'pizza (Rrant-dish R)))
            RL)))
        (/ (foldr + 0
     (map (lambda (R) (Rrant-price R)) PRL))
     (foldr + 0 (map (lambda (R) 1) PRL))))


5. Using map, filter, and foldr, write an expression to return each of the following values without using explicit recursion:
      * a list of all the French and Italian restaurants in RL
      * a list of all the names of the French and Italian restaurants in RL
      * a list of all the restaurants in RL whose best dish costs between $10.00 and $20.00 (inclusive).
      * the name of the lowest-priced French restaurant in RL
      * (this one's tough) a list of all the restaurants in RL, where every French restaurant whose best dish's price is less than the average (price of best dishes at French restaurants) has its price changed to that average price.


4. If you're familiar with some other programming language, ask yourself how much code it would take in that language to perform the same tasks as the examples above.


5. Modify the restaurants program to read the collection from a file at the beginning and to write it to a file at the end. (More precisely, it should give the user a choice at the beginning: Start a new database or read an existing one.) The easiest way to do this is to write the whole collection (the list of restaurant structures) as a single Scheme expression and to read it back in the same way, using (read) and (write); there are a few other details, so read the rest of this before starting.


1. File I/O isn't particularly hard, but it involves many system-dependent details (not just in Scheme but in any language). Below we supply some sample code that you can adapt for use in the restaurants program. (Sometimes the web browser doesn't display code with proper indentation. If you paste it into DrScheme, though, and choose "Reindent All" from the Scheme menu, you'll see it formatted properly.)
   
   (define copy-file
    ; Prompts the user for a file to copy (using the standard system dialog);
    ; then copies that file's contents to another file selected by the user.
    ; The file must contain a single Scheme expression.
    ; Call with (copy-file).
    (lambda ()
     (let* ((data (read
     (open-input-file
     (get-file "Please select file to copy" #f #f #f #f '()))))
     (dest-file (open-output-file
     (put-file "Please select file for result" #f #f #f #f '())
     'replace)))
     (write data dest-file)
     (close-output-port dest-file)
     (display "Thank you."))))
   
   I/O in Scheme makes a distinction between a port, the actual object that supplies the input or receives the output (e.g., a file or the screen), and a file name or path (a string that gives the name of the object that's visible to the user). The function open-input-file takes a file name (a string) and returns a port; the function read takes a port and returns the Scheme expression it reads from that port. The output functions work similarly; much more detail is available in the DrScheme Help Desk. The functions included here are standard Scheme except for get-file and put-file, which are system-dependent details unique to the DrScheme/MrEd environment.


2. In the PrettyBig version of DrScheme, we have to make one more transformation so that we can write and read the actual contents of structures (rather than just "#<struct:rrant>"); we have to turn each Rrant structure into a vector before we write it (and when we read the vector back, we have to convert it back into a Rrant structure). Here are some details:


1. When you define the structure, you need to add (make-inspector) like this:
   (define-struct rrant (name cuisine phone dish price) (make-inspector))


2. Apply the predefined function struct->vector to each Rrant on the list before you write the list. (One of the functions from earlier in this lab will do this in one expression.)


3. After you read back in the list of restaurants (which are now in vector form), you need to make a structure from each one using a function like this:
   (define RV->struct
     (lambda (RV)
     (make-Rrant (vector-ref RV 1) (vector-ref RV 2) (vector-ref RV 3)
     (vector-ref RV 4) (vector-ref RV 5))))


3. You will want to do this with a partner; there are tons of small details here, for which two heads will work much better than one.


4. This part is completely optional. Modify the restaurants program to write its output file in a more human-readable form (and to read files in the same form). This will require you to make some decisions about what format to use, and to look up a variety of file-reading and string-handling functions in the DrScheme Help Desk As programming environments and libraries become more complex and powerful, more and more of a programmer's task will be navigating documentation sources to look for the appropriate tool, rather than building the tool from scratch him- or herself. As a start, the file copyfile.ss contains a variant of the file I/O above that reads and writes files, one line at a time.

COSMOS Cluster 5 Home * COSMOS UCI Home

Thursday, July 22, 2004 -- 1:47 PM