Class 20: Writing HTML from Scheme

Held Wednesday, September 27, 2000

Summary

Today we revisit the issue of searching lists.

Notes

• Are there any final questions on exam 1?
  • Do not use display or read on the exam.
  • If you email me questions, please title the email QUESTION on 151 Exam.
  • If you haven't started already, start soon.
  • We'll do parts of number 6 of the association list lab today.
  • Come visit me in my office this afternoon and tomorrow (just not during convocation).
• We'll probably continue with the CGI scripting application into next week.
• How have people felt about this week's "lecture, group programming, casual lab assignment" schedule?

Overview

• Exam questions
• Project discussion
• Searching

Picking a Database Application

• For our short-term class project e have the opportunity to build a simple database application of our choosing.
  • This will eventually be a Web application.
• Approximate development pattern:
  • Pick representation in Scheme (today)
  • Turn one entry into nice text (today)
  • Turn one entry into HTML (today)
  • Develop simple retrieval algorithms (next week; example today)
  • Develop textual user interface for retrieval (next week)
  • Develop Web-based user interface for retrieval (next week)
  • Read data from file (far in the future)
  • Make it easier to add data (far in the future)
• In past years, people have written a simple directory application that lets you look up phone numbers and such.
• Other options
  • A (simplified) dating service
  • A course recommendation system
  • ...
• We'll pick an application as a class.
• Once we've picked our basic application, we should decide how to represent data within Scheme.
  • For example, suppose I wanted to have a database of descriptions of Olympic events. For each event, I might store a list of adjectives and the name of the event.
  • We'll design ours tomorrow.

Searching

• Let's revisit Exercise 6.c from the lab on association lists

  c. Define and test a procedure that takes two arguments, the first an atom and the second an association list whose keys are all lists of atoms. The procedure should return a list of all the values whose keys contain the atom.

• Here's an example of the data, using a list of adjectives as the key and an olympic event as the data.

  (define olympic-events
    (list
      (cons (list 'individual 'exciting 'dangerous 'water) "High Dive")
      (cons (list 'dangerous 'new 'gymnastics 'individual) "Trampoline")
      (cons (list 'team 'popular) "Volleyball")
      (cons (list 'water 'team) "Water Polo")))
  

• Our function will take the form
  (search-by-adjective adj list)
• This is probably an exercise in recursion
• Base case: The list of events is empty.
  • Return the empty list.
• Successful case: The adjective describes the first thing.
  • Use the name of the first event
  • Repeat for the rest of the list.
• Unsuccessful case: The adjective does not describe the first thing.
  • Repeat for the rest of the list.
• We're ready to start turning this into Scheme code.
• Here's the start of the definition

  (define search-by-adjective
    (lambda (adj stuff)
      ...))
  

• Since there are three cases, we'll use a cond

      (cond
        ; Base case: The list of things is empty so return the empty list
        ((...) ...)
        ; Successful case: The adjective describes the first value
        ;   so return the first value plus other matching values.
        ((...) ...)
        ; Default case: Unsuccessful match.  Try the rest.
        (else ...))
  

• How do we know if the list of things is empty?
  (null? stuff)
• How do we return the empty list?
  null
• How do we tell if the adjective describes the first value? We need to check whether the adjective is in the list of adjectives.
  • The adjective is adj
  • The list of adjectives is (caar stuff)
  • You should know how to write "Is in this list?".
• How do we use the first value and any remaining values?
  (cons (cdaar stuff) (search-by-adjective adj (cdr stuff)))
• Putting it all together

  (define search-by-adjective
    (lambda (adj stuff)
      (cond
        ; Base case: The list of things is empty so return the empty list
        ((null? stuff) null)
        ; Successful case: The adjective describes the first value
        ;   so return the first value plus other matching values.
        ((member? adj (caar stuff)) 
          (cons (cdar stuff) (search-by-adjective adj (cdr stuff))))
        ; Default case: Unsuccessful match.  Try the rest.
        (else (search-by-adjective adj (cdr stuff))))))
  
  (define member?
    (lambda (val lst)
      (cond
        ; You can't be a member of the empty list.
        ((null? lst) #f)
        ; If you're the first thing in a list, then you're a member
        ; of that list.
        ((equal? val (car lst)) #t)
        ; Otherwise, check the remainder of the list.
        (else (member? val (cdr lst))))))
  

• Now let's test it out.

  > (search-by-adjective 'exciting olympic-events)
  ("High Dive")
  > (search-by-adjective 'water olympic-events)
  ("High Dive" "Water Polo")
  > (search-by-adjective 'silly olympic-events)   
  ()