Before the Lab
- Complete the Parsing using
match
exercise
Background
Review and Questions
- Time
- 20 minutes
- Activity
- Group Discussion
- Review of Parsing with Match
- Questions about Assignment 2
- Time permitting, sample solution to Assignment 1.
Hash tables
- Time
- 20 minutes
- Activity
- Individual
Although we've mainly focussed on lists, racket supports many other data structures. One very useful data structure is the hash table These support fast key based retrieval (and updating) of information.
- The function
hash
creates an immutable hash table. Values can be retrieved withhash-ref
#lang racket
(define ht (hash "apple" 'red "banana" 'yellow))
(module+ test
(require rackunit)
(check-equal? (hash-ref ht "apple") 'red))
- Immutable hash tables can be "updated" in the same way as lists, by
returning a new, updated data structure. These updates are "constant
time", which means they are pretty fast. In the following, hash-set
is acting like
cons
, adding new data toht
and returning the result. Note thatht
is not modified here, as the tests show.
(define ht2 (hash-set ht "coconut" 'brown))
(module+ test
(check-equal? (hash-ref ht2 "coconut") 'brown)
(check-exn exn:fail? (lambda () (hash-ref ht "coconut"))))
- In the following example, a hash set is used to count the times a given element occurs in a list. Fill in update to the accumulator in the following code so that the tests pass.
(define (census . lst)
(define (helper lst acc-hash)
(cond
[(empty? lst) (hash->list acc-hash)]
[else
(let* ([key (first lst)]
[current (hash-ref acc-hash key 0)])
(helper (rest lst) ))]))
(helper lst (hash)))
(module+ test
(check-equal?
(sort (census 1 2 3 1 2) #:key car <) '((1 . 2) (2 . 2) (3 . 1)))
(check-equal?
(sort (census "aardvark" "dingo" "buffalo" "buffalo" "bear") #:key car string<?)
'(("aardvark" . 1) ("bear" . 1) ("buffalo" . 2) ("dingo" . 1))))
- We are using
pairs,
which are related to lists, but not exactly the same.
car
is likefirst
, but works for both pairs and lists.
Explorer
- Time
- 10 minutes
- Activity
- Demo
- Run the following program in DrRacket. You can navigate the data structure with the mouse,
and evaluate expressions involving
this
(e.g.(first this)
,(hash-ref "apple" this)
) in the bottom REPL window.
#lang racket
(require explorer)
(define a-list
(list 1 (list 'foo "hello")
(hash 'apple "red" 'sky "blue" 'violets "purple")))
(explore a-list)
Discussion
- Time
- 10 minutes
- Activity
- Group discussion
- What new Racket features did we see in the first half of the lab?
- How are (immutable) racket hash tables similar to Java HashTables/HashMaps
- How is using immutable hash tables different from mutable hashtables (e.g. like those in Java or Python).
JSON
- Time
- 35 minutes
- Activity
- Individual
JSON is a common data interchage format. Most modern languages have some way to parse JSON, but it typically still requires some effort to extract the desired data.
save errors.json to a file
errors.json
Start with the following code, run
(visualize-json-file "errors.json")
to visualize the structure of the example JSON file.Note that the JSON parser is using hasheq instead of
hash
. This changes the equality test fromequal?
toeq?
, but since we are only using symbols for keys, it should not matter.
(require explorer)
(require json)
(define (read-json-file file-name)
(with-input-from-file file-name read-json))
(define (visualize-json-file file-name)
(explore (read-json-file file-name)))
- use the explorer to help you write a function
collect-status
, that collects the "status" values fromerrors.json
. It should pass the following test. Probably the easiest method involves usingmap
; you will also needhash-ref
to extract values from hash tables.
(module+ test
(require rackunit)
(check-equal? (collect-status "errors.json") '("403" "422" "500")))
If you have extra time
Complete the tail recursive version of collect-status. Note the use of sort in the test case, so we don't care about the order of our list.
(define (collect-status2 filename)
(define (helper in-lst acc)
(cond
[(empty? in-lst) acc]
[else (helper (rest in-lst) )]))
(helper )
(module+ test
(check-equal? (sort (collect-status "errors.json") string<?)
(sort (collect-status2 "errors.json") string<?)))