CS-2510 Lab 1

Purpose:

The purpose of this lab is to review Racket a bit more (warm up your minds a bit... since you've probably noticed that the weather won't do that for you yet), and to explore inexact numbers and accumulators.

---

Part 1: Inexact Numbers

Remember last semester whne we dealt with a wierd kind of number in DrRacket? You may not remember them explicitly, but the numbers returned by trig functions (like cos) and sometimes sqrt are different than typical numbers like 5.

     > (cos pi)
     #i-1.0

     > (tan pi)
     #i-1.2246063538223773e-16

     > (sqrt 2)
     #i1.4142135623730951
        

Why the new #i notation? DrRacket differentiates between numbers that represent exact quantities (which might require an infinite amount of memory), and those that are inexact, but require only a fixed amount of memory (fixed is the important part, since not even Bill Gates has infinite memory... yet).

The main difference between the two types is when numbers get really big, or really small. Here's a simple example:

     ;; A list of innocent looking inexact numbers
     (define SOME-NUMS
       (list #i+9e22
             #i+8e22
             #i-1e22
             #i+6e22))
        

In order to sum them quickly, we have two easy options:

     (define (sum-right alist) 
       (foldr + 0 alist))

     (define (sum-left alist)
       (foldl + 0 alist))
        

Unfortunately, these functions do not produce the same results on our list... don't believe me? Try them out:

     (sum-left SOME-NUMS)
     (sum-right SOME-NUMS)
        

Can you figure out why? Maybe reviewing the definitions of foldl and foldr will help:

     ;; foldr : [X Y  ->  Y] Y [Listof X]  ->  Y
     ;; (foldr f base (list x1 ... xn)) = (f x1 ... (f xn base)) 
     (define (foldr f base alox) ...)

     ;; foldl : [X Y  ->  Y] Y [Listof X]  ->  Y
     ;; (foldl f base (list x1 ... xn)) = (f xn ... (f x1 base))
     (define (foldl f base alox) ...)
        

For example, the (exact) numbers in the list (list 3 5 8 2) can be added (at least) two ways:

     (+ 3 (+ 5 (+ 8 (+ 2 0))))

     (+ (+ (+ (+ 0 3) 5) 8) 2)

        

Notice the difference? If you're confused, try stepping them in DrRacket. Then complete the following problems.

1. Design the function sum-reg using the standard Design Recipe (structural recursion) and explain in what order are the numbers added.
2. Convert the function into one that uses an accumulator, call it sum-acc. What is the order of the additions now?
3. Match the two functions with sum-left and sum-right from before (that use foldl and foldr)... Which is which?

---

Part 2: Breaking Down Accumulators

When do we need an accumulator? When some information within a function gets lost in (structural) recursive calls. What does the accumulator mean? The accumulator value is usually the same class of data as the result of the function. What should the function produce when there is nothing to remember? This value becomes the initial accumulator. We call this the base-value.

Once we understand what the accumulator is/does, it is important to document the invariant that the accumulator maintains. Usually this is a sentence like: "The accumulator represents the Wizwoz of the FooBars seen so far".

We can actaully write a template for an accumulator function over lists:

     ;; rec-fcn: [Listof X] -> Y
     ;; Produce a Y from the given list of X
     (define (rec-fcn lox) 
       (local [
               ;; rec-fcn-acc: [Listof X] Y -> Y
               ;; Recursive function with an accumulator
               (define (rec-fcn-acc lox acc)
                 (cond
                   ;; * At the end produce the accumulated value
                   [(empty? lox) acc]
                   ;; * Else recur with updated accumulator on the rest of the list
                   [(cons? lox)  (rec-fcn-acc (rest lox)
                                              (update (first lox) acc))]))]
         ;; * Start with the whole list and the base-value
         (rec-fcn-acc lox base-acc-value)))
        

Exercise 1:

Remember the function factorial? It computes the product of the numbers from 1 to n.

1. Write a standard (recursive) definition, call it fact-rec.
2. Rewrite the function using an accumulator, call it fact-acc.
3. There are two important questions: (a) What does the accumulator represent? and (b) How/where is it updated? Write a comment that answers these two questions, after your purpose statement.

Exercise 2:

Consider the following function definition:

     ;; total-x-coord: [Listof Posn] -> Number

     ;; Compute the total X movement of the Posns
     (define (total-x-coord alop)
       (foldl + 0 (map posn-x alop)))
          

The function, total-x-coord, is very clear, but possibly not as efficient as it could be: we first produce a list of x coordinates, then we loop over the list to compute the total. If we were doing this in our head, we would simply add each x to a running total.

1. Write tests for total-x-coord.
2. Define total-x-coord-acc function that uses an accumulator to keep track of the total so far. Do not use any Racket loop functions. Run the same tests to make sure it works.
3. Design the function average-x-coord that computes the average x coordinate from a list of Posns (remember length?) using good-old structural recursion. Do not use any Racket loop functions.
4. Refactor (redesign) your function into function average-x-coord-acc that only walks over the list once. Hint: There are several ways to do this... choose one. If you have time, try it several different ways.

If you finish early, take a look at the HW Assignment, or try visualizing a listof Posns (using an accumulator, of course), and displaying the results of your functions (from above) on the resulting Scene. E.g., click to add Posns, display the Posns and the Stats.