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:
Design Recipe for Data Definition
Design Recipe for Functions
Design Recipe for Abstractions
Review them by working out these simple problems:
Design a data representation for the following problem.
You are working your way through a maze. At each step through the maze you have to answer a question. The answer to the question is either yes or no. Each answer leads you to the next step —
with another question. Finally, each such path through the maze ends with a reward. The reward is represented as a message. Design the function for your maze that finds the length of the longest path from the start of the maze to some reward.
Design the function that produces the list of questions and the final reward you will encounter, if you answer every question with a yes.
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:
From A to B the distance is #i+9e23
From B to C the distance is #i+8e23
From C to D the distance is #i-1e23
From D to E the distance is #i+6e23
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:
the maximum distance the vehicle can travel on one tank of fuel
whether it can travel a given distance
whether it can travel farther than some other vehicle
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:
A car may or may not pull a trailer.
A bus can carry some number of passengers (capacity) and has some number of passengers on board.
A truck has some specified maximum load and some current load.
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:
A car without a trailer pays $0.25 per mile
A car towing a trailer pays $0.35 per mile.
A bus pays $0.35 per mile and additional $0.20 for each passenger.
A truck pays $0.40 per mile and in addition $0.05 for each 1000 lb of load it currently carries.