Lecture 4: More on Lists

###
Lecture 4: More on Lists

1. Last time we made the following agreement: "A Cartesian point is represented with a list of two numbers."

   Then we defined the program `distance-to-origin,` which consumes a point and computes its distance to the origin:

             always a point _______
       		            |
       	                    v
       (define (distance-to-origin x)
         (sqrt
           (+ (square (first x))
              (square (first (rest x))))))

   And here is how we used the program and how DrScheme determined the result:

         (distance-to-origin (cons 3 (cons 4 empty)))
       = (sqrt
           (+ (square (first (cons 3 (cons 4 empty))))
              (square (first (rest (cons 3 (cons 4 empty)))))))
       = (sqrt
           (+ (square 3)
              (square (first (rest (cons 3 (cons 4 empty)))))))
       = (sqrt
           (+ (square 3)
              (square 4)))
       = (sqrt
           (+ 9 16))
       = 5

2. This program is difficult to read. -- When we think about bundles of a fixed number of pieces of data, we need to introduce little helper functions that construct the bundles and extract data from such a piece of information.

       ;; A point is a list of two numbers:
       ;;   (cons number (cons number empty))

       (define (make-point x y)
         (cons x (cons y empty)))

       (define (point-x x)
         (first x))

       (define (point-y x)
         (first (rest x)))

   How do these things interact:

       (point-x (make-point 3 4)) = 3
       (point-y (make-point 3 4)) = 4
       ...

3. Now we can rewrite `distance-to-origin` and reuse these simple programs:

       (define (distance-to-origin x)
         (sqrt
           (+ (square (point-x x))
              (square (point-y x)))))

   Even computing with these is simpler:

         (distance-to-origin (make-point 3 4))
       = (sqrt
           (+ (square (point-x (make-point 3 4)))
              (square (point-y (make-point 3 4)))))
       = (sqrt
           (+ (square 3)
              (square 4)))
       = (sqrt
           (+ 9 16))
       = (sqrt 25)
       = 5

   We will practice more with such bundles in lab. We will also introduce a short-hand that creates all those helper functions in a single line.

4. Suppose you're running a store and you keep track of the value of all the items in a store. You may have a list like the following:

         1.20
         9.80
         7.30
       220.30

   or an even longer one ...

   Suppose we want a program that consumes a list like this, we first need to describe what kind of data flows in.

   How do we describe such a list rigorously?

   A list of prices is either empty or (cons number l) where l is a list of prices.

   Now that we have a description of the kind of data, let's make up examples. Translate the examples e.g.

        empty

        (cons 1.20
          (cons 9.80
            (cons 7.30
              (cons 220.30
                 empty))))

        ... and more ..

   What should be the result of

       (sum
        empty)
       = ???

       (sum
        (cons 1.20
          (cons 9.80
            (cons 7.30
              (cons 220.30
                 empty)))))
       = ???

   And how could we do this?

                     ___________ will always be a list of numbers
                    |
                    v
       (define (sum x)
         (cond
           ( ... empty ... )
           (else
             ...)))

        empty? : X -> bol

       (define (sum x)
         (cond
           ((empty? x) ...)
           (else
             (first x) <--- is a number
             (rest x)  <--- is a list of numbers
             )))

       (define (sum x)
         (cond
           ((empty? x) ...)
           (else
             (first x) <--- is a number
             (rest x)  <--- is a list of numbers
             )))

   Use sum to process the rest, add the pieces:

       (define (sum x)
         (cond
           ((empty? x) 0)
           (else
             (+
       	(first x)
       	(sum (rest x))))))
               ^^^^^^^^^^^^^^ <--- computes the sum of all the numbers in (rest x)
                   How can we compute the sum of all the numbers in x
                   Which one have we not considered so far

   Let's watch it in action:

         (sum empty)
       = (cond
           ((empty? empty) 0)
           (else
             (+
       	(first empty)
       	(sum (rest empty)))))
       = (cond
           (#t 0)
           (else ...))
       = 0

   More of this:

         (sum (cons 12 empty))
       = (cond
           ((empty? (cons 12 empty)) 0)
           (else
             (+
       	(first (cons 12 empty))
       	(sum (rest (cons 12 empty))))))
       = (cond
           (#f 0)
           (else
             (+
       	(first (cons 12 empty))
       	(sum (rest (cons 12 empty))))))
       = (+
           (first (cons 12 empty))
           (sum (rest (cons 12 empty))))
       = (+
           12
           (sum empty))
       = (+ 12 0)
       = 12

Matthias Felleisen | This page was generated on Fri Mar 5 09:04:41 CST 1999.