UNB/ CS/ David Bremner/ teaching/ cs2613/ labs/ Lab 5

# Part 1: Tail Recursion

Time
30 minutes
Activity
Small groups / individuals
• make a directory `~/fcshome/cs2613/labs/L05` to store files from this lab.

• Background for this part is Racket Guide on Tail Recursion

• Run the following code in the debugger, and observe how deep the stack gets.

```    #lang racket
(module+ test
(require rackunit))

(define (odds-evens lst)
(cond
[(empty? lst) (list 0 0)]
[(odd? (first lst)) (map + '(1 0) (odds-evens (rest lst)))]
[(even? (first lst)) (map + '(0 1) (odds-evens (rest lst)))]))

(module+ test
(check-equal? (odds-evens (list 3 2 1 1 2 3 4 5 5 6)) (list 6 4)))
```
• Our initial version of `odds-evens` is not tail recursive because the result(s) of the recursive calls are processed further before returning (i.e. here passed to `map`).

• Complete the following tail recursive function to count the number of odd and even numbers in a list. The general idea is that the recursive call to `helper`

• reduces the size of the list argument by one, and
• increments exactly one of the arguments `odd` and `even`. This is a very common pattern in Racket, where recursion replaces mutation (i.e. replaces `odds=odds+1`)
```    (define (odds-evens2 lst)
(define (helper lst odds evens)
(cond
[(empty? lst) (list odds evens)]
[(odd? (first lst)) (helper                             )]
[(even? (first lst)) (helper                             )]))
(helper lst 0 0))

(module+ test
(define random-list (build-list 100 (lambda (x) (random 1 100))))
(check-equal? (odds-evens2 (list 3 2 1 1 2 3 4 5 5 6)) (list 6 4))
(check-equal? (odds-evens random-list) (odds-evens2 random-list)))
```
• Use the racket debugger to test the stack usage of your function.

• save the results of this section in `~/fcshome/cs2613/labs/L05/odds-evens.rkt`, and commit this file.

# Part 2: for loops

Time
15 minutes
Activity
Group discussion/demo
• Although some Racket programmers like a minimalist style using pure tail recursion, many prefer to use for loops

• To accumulate values, one Racket library form is `for/fold`

```(define (odds-evens3 lst)
(for/fold
([accumulator (list 0 0)])
([n lst])
(cond
[(odd? n) (list (add1 (first accumulator))  (second accumulator))]
[(even? n) (list (first accumulator)  (add1 (second accumulator)))])))

(module+ test
(check-equal? (odds-evens3 (list 3 2 1 1 2 3 4 5 5 6)) (list 6 4))
(check-equal? (odds-evens random-list) (odds-evens3 random-list)))
```
• Let's finish off by comparing the speed of our three implimentations
```(define big-list (range 1000000))
(for* ([fun (list odds-evens odds-evens2 odds-evens3)]
[rep '(1 2 3)])
(printf "~a ~a\n" fun rep)
(time (fun big-list)))
```
• add the results of this section to `~/fcshome/cs2613/labs/L05/odds-evens.rkt`, and commit your changes.

# Part 3: Racket review

Time
10 minutes
Activity
Group discussion

What's new in the first half of today's lab?

• built in functions / forms?
• concepts?
• which of these can you map to other programming languages that you know?

# Part 4 Numerical Integration examples

Time
35 minutes
Activity
Small groups / individuals (you may need your files for next lab)

In this section we'll play a bit with some crude numerical derivative and integral calculation. Don't worry about the calculus too much, this is mainly a chance to reinforce

• tail recursion
• for loops
• higher order functions

We'll also think about about testing numerical functions.

```    #lang racket
(require racket/math)

(module+ test
(require rackunit)
(define epsilon .001))

(define dx 0.001)
(define -2pi (* -2 pi))
(define 2pi (* 2 pi))

;; compute the derivative of `f' at the given point `x'
(define (deriv f x)
(/ (- (f (+ x dx)) (f x)) dx))

;; Integrate a function from 0 to x (using tail recursion)
(define (integrate f x)
(define (loop y acc)
(if (> y x)
(* acc dx)
(loop (+ y dx) (+ acc (f y)))))
(loop 0 0))
```
• In general it's a bad idea to test floating point numbers for exact equality. `rackunit` provides `check-=` exactly for this situation. Choose different values of `epsilon` and `dx` to make the following test succeed and fail:
```    (module+ test
(check-= (integrate cos (/ pi 4)) (sin (/ pi 4)) epsilon))
```
• it's a bit (extremely?) boring to test numerical functions if we have to write down all of the input values. The following sets up a bunch of random numbers between 0 and 2pi, and also defines some test functions. Fill in the body of the loop to do many tests.
```    (module+ test
(define test-points (build-list 20 (lambda (x) (* 2 pi (random)))))
(define (sin2 x) (integrate cos x))
(define (cos2 x) (deriv sin x))
(for ([x test-points])

))
```
• The following translation of `integrate` to use `for/fold` is almost correct, but missing the kindof sneaky step in the base case of `integrate`. Look at the actual numbers in the failing test case, and fix this version to match the output of the previous one.
```    (define (integrate2 f x)
(for/fold
([acc 0])
([y (in-range 0 x dx)])
(+ acc (f y))))

(module+ test
(for ([x test-points])
(check-= (integrate cos x) (integrate2 cos x) epsilon)))
```
• save the results of this section in `~/fcshome/cs2613/labs/L05/calculus.rkt`, and commit this file.

• push any new commits from this lab.