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

# Before the lab

• Read the description of A2, making notes of any unclear concepts. Most should be covered in today's lab, but if not, ask.

• Complete the Scribble Demo from the previous lab.

# Discussion of "Before the Lab"

Time
10 minutes
Activity
Group discussion
• Discussion / Questions on Scribble
• Discussion of T1

# Tail Recursion

Time
30 minutes
Activity
Individual Work
• 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 (count-odds lst)
(cond
[(empty? lst) 0]
[(odd? (first lst)) (add1 (count-odds (rest lst)))]
[else (count-odds (rest lst))]))

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

• 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
• maybe increments `odds` This is a very common pattern in Racket, where recursion replaces mutation (i.e. replaces `odds=odds+1`)
```(define (count-odds2 lst)
(define (helper lst odds)
(cond
[(empty? lst) odds]
[(odd? (first lst)) (helper                       )]
[else (helper                )]))
(helper lst 0))

(module+ test
(check-equal? (count-odds2 (list 3 2 1 1 2 3 4 5 5 6)) 6)
(define random-list (build-list 100 (lambda (x) (random 1 100))))
(check-equal? (count-odds random-list) (count-odds2 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/count-odds.rkt`, and commit this file.

# For loops

Time
10 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 (count-odds3 lst)
(for/fold
([odds 0])
([n lst])
(cond
[else odds])))

(module+ test
(check-equal? (count-odds3 (list 3 2 1 1 2 3 4 5 5 6)) 6)
(check-equal? (count-odds random-list) (count-odds3 random-list))
(check-equal? (count-odds3 (list 3 2 1 1 2 3 4 5 5 6)) 6))
```
• Let's finish off by comparing the speed of our three implementations
```(define big-list (range 50000000))
(for* ([fun (list count-odds count-odds2 count-odds3)]
[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/count-odds.rkt`, and commit your changes.

# Pattern Matching

One very useful feature of racket is pattern matching. This is used in `syntax-case` to define macros, but also in more familiar function definitions using match.

Roughly speaking, you can think about `match` as fancy `cond`, where instead of specifying a test for each case, you specify a pattern to match against the data.

## `map` using `match`

Time
10 min
Activity
Demo
• Start a new file `~fcshome/cs2613/labs/L05/match.rkt`

• Compare the following implementation of `my-map` with the definition in L03.

```    (define (my-map f lst)
(match lst
['() '()]
(my-map f tail))]))

(module+ test
(require rackunit)
(check-equal? (my-map sub1 '(1 2 3)) '(0 1 2)))
```

## `list-length` using `match`

Time
20 min
Activity
Demo + individual work
• Use `match` to implement a `list-length` function that passes the following tests
```  (module+ test
(require rackunit)
(check-equal? (list-length '(1 2 3)) 3)
(check-equal? (list-length '()) 0))
```
• A common racket idiom is to use the `...` "collector pattern" instead of `cons`. This is also useful in `syntax-case` in macros.
```    (define (my-map2 f lst)
(match lst
['() '()]
(my-map2 f tail))]))
```
• Use `match` and a collector pattern to implement a `list-length2` function that passes the following tests
```  (module+ test
(require rackunit)
(check-equal? (list-length2 '(1 2 3)) 3)
(check-equal? (list-length2 '()) 0))
```

## Parsing with match

Time
20 min
Activity
Individual work

In this part of the lab we'll implement a somewhat silly four function calculator. Start with the following function, which understands only addition.

```(define (calc expr)
(match expr
[(? number? n) n]
[`(plus ,l ,r) (+ (calc l) (calc r))]
[_ (error 'calc "syntax error")]))

(module+ test
(require rackunit)
(check-equal? (calc '(plus 1 2)) 3)
(check-equal? (calc '(plus (plus 1 2) 3)) 6))
```

Referring to the discussion about `quasiquote` at the end of match, add `times`, `div`, and `sub` to the calculator. Here are 3 more tests to pass.

```  (check-equal? (calc '(times (plus 1 2) 3)) 9)
(check-equal? (calc '(div (times (plus 1 2) 3) 3)) 3)
(check-equal? (calc '(sub (div (times (plus 1 2) 3) 3) 3)) 0)
```
• bonus question: how would you allow any number of arguments to your operations instead of just 2?

• push any new commits from this lab.