# Background

# 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

- Questions about Assignment 2
- 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
[(odd? n) (add1 odds)]
[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
['() '()]
[(cons head tail) (cons (f head)
(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
['() '()]
[(list head tail ...) (cons (f head)
(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.