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

Background

Before the lab


Discussion of "Before the Lab"

Time
10 minutes
Activity
Group discussion

Tail Recursion

Time
30 minutes
Activity
Individual Work
#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))
(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)))

For loops

Time
10 minutes
Activity
Group discussion/demo
(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))
(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)))

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
    (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
  (module+ test
    (require rackunit)
    (check-equal? (list-length '(1 2 3)) 3)
    (check-equal? (list-length '()) 0))
    (define (my-map2 f lst)
      (match lst
        ['() '()]
        [(list head tail ...) (cons (f head)
                                    (my-map2 f tail))]))
  (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)