Lab 1

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

1 Design Recipes

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

• Design Recipe for Data Definition

• Design Recipe for Funcions

• 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.

2 Loops and Accumulators

In our scientific meaasurement 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 reson 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.