Notes: Friday 13 February 2004

Schedule

• Monday, 16 Feburary: Problem Set 4
• Monday, 23 February: Exam 1 (will be handed out on Friday, 20 February)
• Before 10 March: Read rest of GEB part I (Chapters 2-4 and 6-9, in addition to Chapters 1 and 5 you have already read).

On Grounds Sorting: Barista Assista

Note: This is a long problem. Don't worry if you can't finish it all in class today, but get as far as you can. We will discuss parts of it in class Monday.

The baristas at Starbucks are sick and tired of CS200 students coming in and demanding the most caffeinated coffee on the menu. They have asked you to write a program that will answer this question automatically.

The program will take today's coffee menu and evaluate to the coffee with the highest caffeine rating. We will describe coffees as a pair where the first part is the name and the second part is a pair of the price and caffeine rating:

(define (make-coffee name price caffeine)
   (cons name (cons price caffeine)))

A menu is a list of coffees. For example:

(define todays-menu
 (list
  (make-coffee "AARDVARK: Alyssa's Really Dark Very Aromatic Roasty Kup" 3.82 85)
  (make-coffee "BEN'S Expresso Noir Supreme" 17.23 92)
  (make-coffee "CyDFect Yusually Doesn't Find Expresso Consumption Tohisliking" 0.85 12)
  (make-coffee "EvaLuAtor's Venti American Light Ubiquitous Always Tasty Oven Roasted Supremo" 
	       2.73 15)
  (make-coffee "Gerry's Not The Java Guy, Guy Is Scheming Mocha Boca Grande" 2.00 57)))

Define the procedures for extracting the name, price and caffeine rating from a coffee. For example,
    (coffee-price (make-coffee "White Chocolate Mocha" 2.53 92))
should evaluate to 2.53 and (coffee-name (find-most-caffienated todays-menu)) should evaluate to "BEN'S Expresso Noir Supreme".

(define (coffee-name coffee)

       
        )

(define (coffee-price coffee)

       
        )

(define (coffee-caffeine-rating coffee)

       
        )

Define a procedure, find-most-caffeinated that takes a list of coffees and evaluates to the coffee with the highest caffeine rating. You may find the insertl procedure useful:

(define (insertl lst f stopval)
  (if (null? lst) 
      stopval
      (f (car lst) (insertl (cdr lst) f stopval))))

(define (find-most-caffeinated menu)







       









  )

Define a more general find-most procedure so we can define find-most-caffeinated as:

(define (find-most-caffeinated menu)
   (find-most 
    (lambda (coffee best-so-far)
      (> (coffee-caffeine-rating coffee) (coffee-caffeine-rating best-so-far)))
    menu 
    (make-coffee "No Caffeine Today" 0.00 0))) ;; inital best-so-far

(define (find-most cf menu start)










  )

Since some customers are revolting at paying $17.23 for BEN'S Expresso Noir Supreme, the baristas have decided that they don't want a procedure that evaluates to just the most caffeinated beverage. Instead, they want to produce a menu sorted by caffiene rating:

> (sort-menu todays-menu)

(("BEN'S Expresso Noir Supreme" . (17.23 . 92))
 ("AARDVARK: Alyssa's Really Dark Very Aromatic Roasty Kup" . (3.82 . 85))
 ("Gerry's Not The Java Guy, Guy Is Scheming Mocha Boca Grande" . (2.00 . 57))
 ("EvaLuAtor's Venti American Light Ubiquitous Always Tasty Oven Roasted Supremo" . (2.73 . 15))
 ("CyDFect Yusually Doesn't Find Expresso Consumption Tohisliking" . (0.85 . 12)))

Define the sort-menu procedure. (This is hard, and I don't expect you to finish today.)

First think how you would do this yourself. There are lots of ways. If you get stuck, read on for hints of one possible way of doing it.

Start by defining sort-menu in terms of a more general sort procedure that takes a function and a list and evaluates to the list reordered by the function (so that if you apply the function to any two adjacent elements in the list, it always evaluates to true).

Then, you need to define sort. First, you may find it useful to first define the delete procedure:

(define (delete el lst)
  (if (null? lst)
      (error "No matching element!") ; Didn't find el in the list
      (if (eq? el (car lst)) ; The first element in the list matches
	  (cdr lst)          ; Drop it --- the result is the rest of the list
          ; else branch left for you to define
	  

Next, define the sort procedure:

(define (sort cf lst)
   (if 

Finally, define sort-menu:

(define (sort-menu lst)
   (sort (lambda (c1 c2) 













	   )
	 lst))

A mathematician is a device for turning coffee into theorems.
Paul Erdös