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 toadd1
).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. replacesodds=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 alist-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 ofcons
. This is also useful insyntax-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 alist-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.