Comp 210 Lab 3: let, structures

(Computers Can be Slow)

A Note on Formatting

Some particular points:

... (cond [(null? argument)  (some-function other-argument)]
          [(complicated-expression (car argument)) (complicated-function argument other-argument)]
          [else (another-complicated-function (cdr argument))])

... (cond [(null? argument)
           (some-function other-argument)]
          [(complicated-expression (car argument))
           (complicated-function argument other-argument)]
          [else
           (another-complicated-function (cdr argument))])

Hand-Evaluating a Complex Function

Starting in class last Friday, we saw some functions that return not just a simple argument (a number), but instead calculated a complex value (e.g., a list). While this might seem different, it's really not hard at all: we just use cons to build our return value:

(define between
  (lambda (low high)
    (if (> low high)
        null
        (cons low (between (+ low 1) high)))))

Censoring Your Code

;; (strongest-coalition-1  popularities)
;; popularities is a list of numbers: popularity ratings of politicians
;; Return the strength of the most popular coalition,
;;  where a coalition's strength is as follows:
;;   Think of people joining a group, one by one.
;;      If they're more popular than
;;      any existing coalition, they found their own new coalition.
;;      Otherwise they join the existing most popular coalition, adding
;;      their popularity.
;;
(define strongest-coalition-1
  (lambda (popularities)
    (cond [(null? popularities) 0]
          [else (if (>= (car popularities)
                        (strongest-coalition-1 (cdr popularities)))
                    (car popularities)
                    (+ (car popularities)
                       (strongest-coalition-1 (cdr popularities))))])))


;; save myself some typing!
;;
(define sc1 strongest-coalition-1)

Now evaluate (sc1 short1) and (sc1 short2). Are these the results you expected?

Let's test our function on a couple of medium-sized lists, m1 m2. Look at what these lists are, then pass them to strongest-coalition. What happened?

You can use the function (bad-list n) to make a list with n items that will cause sc1 some difficulty. Exactly how long a list do you need to before you have to wait too long for an answer?

Note that our code contained some repeated code: in order to compute (strongest-coalition popularities), we may compute the value of (strongest-coalition (cdr popularities)) two times. How can we avoid re-computing an answer?

The answer is let, a new Scheme statement (covered in Chapter 5 (postscript)). The let statement allows you to create new, temporary placeholders, and give them a value. The value of those new placeholders can then be used repeatedly. Here's a simple example:

     (let ([G 6.670e-11]      ;; gravitation constant, in N m^2/kg^2
           [M1 1.989e30]      ;; mass of sun in kg
           [M2 5.965e24]      ;; mass of earth in kg
           [r  1.496e10])     ;; mean earth-sun dist in m
       (/ (* G M1 M2 ) (* r r)))  ;; gravitational force earth/sun, in newtons

In general, the syntax of the let statement is:

        (let  ([ph1 exp1]
               [ph2 exp2]
               ...      
               [phn expn])
             resultExp)

In writing your own lets, notice how one set of parentheses is around each placeholder/expression pair, and another set of parentheses is around the list of these pairs. (I use square-parentheses to help distinguish them, but square and round parentheses are equivalent to Dr. Scheme.) Also, be aware that the expression exp2 can not use the placeholder ph1! Of course, resultExpcan itself be a let statement (evil grin).

A more interesting use of let is to reduce redundant computation. Let's try "censoring" our code for strongest-coalition-1, and only compute once the intermediate value (strongest-coalition (cdr popularities)). We'll store this value inside a let using a local placeholder mob-pop.

(define strongest-coalition-2
  (lambda (popularities)
    (cond [(null? popularities) 0]
          [else (let ([mob-pop (strongest-coalition-2 (cdr popularities))])
                     (if (>= (car popularities) mob-pop)
                         (car popularities)
                         (+ (car popularities) mob-pop)))])))

(define sc2 strongest-coalition-2)

Self-test on let:
Write the function solve-quadratic, which takes three numbers a,b,c and returns a list of the real roots of ax^2+bx+c=0 (that is, what are all the real values of x that make this statement true?). You can do it as you like, though my let statement happened to use three placeholders: discriminant, denominator, and negB. If you want to get fancy, make sure your function works for degenerate cases like a=0, etc.

Structures

Raising the Language Level

Structures for Family Trees

(define-structure (branch mom name dad))

An example would help, about now. Try typing in the following.

(define a-tree      (make-branch 'unknown 'gabi 'unknown))
(branch-name a-tree)
(branch-dad a-tree)
(branch? a-tree)

Exercise: What does a template look like now, for Family Trees?
Using these new structures, write the function snobby which takes a Family Tree, and returns #t if 'Lady-Pfefferplump occurs in the tree, and #f otherwise.

You can also browse an application of Complex Web Pages using Structures.

Sharing Data

         Gabi    Helmut
          |         |
          +---------+
              |
          +----------+
          |          |
Hunko  Chantelle   Pierre  Lady-Pfefferplump
|        |           |        |
+--------+           +--------+
   |                      |
 Bambam                Pebbles
   |                      |
   +----------------------+
             |
          Godzillette

(define gabi      (make-branch 'unknown 'gabi 'unknown))
(define helmut    (make-branch 'unknown 'helmut 'unknown))
(define pierre    (make-branch gabi 'pierre helmut))
(define chantelle (make-branch gabi 'chantelle helmut))
(define pebbles   (make-branch
                       (make-branch 'unknown 'Lady-Pfefferplump 'unknown)
                       'pebbles
                       pierre))
(define bambam    (make-branch chantelle 
                       'bambam
                       (make-branch 'unknown 'Hunko 'unknown)))
(define godzillette  (make-branch pebbles 'godzillette bambam))

The UNIX corner