1 Logistics
2 Design Recipes
3 Loops and Accumulators
4 Design Recipe Review
Version: 5.2.1

Lab 1

Goals: Review the design recipes, work with inexact numbers, review the design of loops using the accumulator style.

1 Logistics

For the homework submission and grading we will use the WebCAT homework submission and grading system. You will access it using your CCIS username and password.

If you do not have a CCIS username and password, fill out an application and bring it to the CCIS Systems drop-off box on the third floor of WVH.

If you have a CCIS username, add your name and CCIS email to the TAs master list at some point during the lab.

We will explain how to use the WebCAT during the lab next week.

2 Design Recipes

You have seen three different design recipes in the first course:

Review them by working out these simple problems:

Note: We will review the Design Recipe for Abstractions at a later time.

3 Loops and Accumulators

In our scientific measurement we came across a strange problem. We are given a list of points and the distances between them, and need to compute the total distance when traversing them in the given order:

To compute the distance traveled we can use one of the following two functions:

(define (sum-right alist)

  (foldr + 0 alist))


(define (sum-left alist)

  (foldl + 0 alist))


;; one way to add all numbers

(sum-right NUM-LIST)


;; another way to add all numbers

(sum-left NUM-LIST)

Run this and observe the results. Actually, both results are inaccurate! Try the following, and reason about the numbers yourself, to see what the correct result should be.

;; adding the large numbers first

(+ (+ #i+9e23  #i+8e23) #i+6e23)


;; then subtracting the small one => correct result

(+ (+ (+ #i+9e23  #i+8e23) #i+6e23) #i-1e23)

We have two problems here. The inaccuracies in compound computations with inexact numbers are inevitable and we will not solve this problem here - we just want to make sure you are aware of it when writing your own programs.

The second problem can be illustrated as follows. Work out the steps the computer goes through when doing the following computations:

;; one way to add all numbers

(sum-right (list 4 5 6))


;; another way to add all numbers

(sum-left (list 4 5 6))

Notice the difference. The definition of foldr and foldl shows how the computation proceeds:

;; foldr: [X Y -> Y] Y [Listof X] -> Y

;; (foldr f base (list x1 x2 ... xn)) = (f x1 (f x2 ... (f xn base)...))

(define (foldr f base alox ...)


;; foldl: [X Y -> Y Y [Listof X] -> Y

;; (foldl f base (list x1 x2 ... xn)) = (f xn ... (f x2 (f x1 base))...)

(define (foldl f base alox) ...)

Define two functions sum-recipe and sum-accumulator that add the numbers in the given list - once from left to right, once from right to left. For the first method follow the design recipe. For the second one use an accumulator. Which one is which?

Now use the stepper to run the methods you designed on the following examples:

;; one way to add all numbers

(sum-recipe (list 4 5 6))


;; another way to add all numbers

(sum-accumulator (list 4 5 6) 0)

Sometimes you cannot solve the problem, unless you use some accumulator. The accumulator represents some information you need to remember from having seen the earlier steps of your program.

Suppose we ask you to compute the distance along some route, but give you just the locations of the points on the way. (Assume you travel between any two points in a straight line.)

We know that the distance between two posns is define as

;; compute the distance between the two given points

;; dist: Posn Posn -> Number

(define (dist p1 p2)

  (sqrt (+ (sqr (- (posn-x p1) (posn-x p2)))

           (sqr (- (posn-y p1) (posn-y p2))))))


;; examples

(check-expect (dist (make-posn 2 3) (make-posn 5 3)) 3)

(check-expect (dist (make-posn 1 1) (make-posn 4 5)) 5)

Define the function total-distance that consumes a list of Posns that represent a route to travel and produces the total distance for the travel along this route.

Hint: What information do you need to remember as you traverse over the list of points?

Make sure you use helper functions as needed.

Make sure you describe in the purpose statement the meaning of the accumulator(s) that you need.

4 Design Recipe Review

Problem 1

Develop a data definition needed to represent a Vehicle. A vehicle can be a Car, a Truck, or a Bus. For all vehicles we need to record the size of the fuel tank in gallons, and the estimated fuel consumption given in miles per gallon.

For each kind of vehicle we can compute:

Design the functions that compute these values.

Hint: Does it matter for these functions what kind of vehicle we have?

Problem 2

Different kinds of vehicles need to represent additional information as follows:

Modify your data definitions to represent this additional information.

What will happen to your functions defined in the previous problem?

Develop the function computeToll, that computes the toll for each vehicle according to the following rules: