Purpose: The purpose of this lab is to practice the use of existing list-processing functions and local.
Textbook References: Chapter 16.1: Existing Abstractions
Note: only use existing abstractions in this lab when the lab tells you to.
Consider the following data definitions and functions (do not copy the functions into your code, or comment them out, as they are provided by "mimic.rkt".
; A [Pair X Y] is a (list X Y) (define pair? list?) (define pair-x first) (define pair-y second) (define make-pair list) ; A [Mapping X Y] is a [List-of [Pair X Y]] ; and associates data of type X with data of type Y
Mappings are everywhere in computer science, and most "real" programming languages will come with them baked-in, along with functions that let you work with them. For this lab, the following two functions will suffice (also provided by "mimic.rkt"):
; get : [Mapping X Y] X -> Y ; Get the value in the mapping associated with x-value (check-error (get (list (make-pair 3 "three")) 4) "not found") (check-expect (get (list (make-pair 3 "three") (make-pair 4 "four")) 4) "four") ; update-mapping : [Mapping X Y] X [Y -> Y] Y -> [Mapping X Y] ; Update the data associated with the x-value in the mapping using the updater function ; If the x-value is not in m, associate it with backup y-value (check-expect (update-mapping '() 3 add1 0) (list (make-pair 3 0))) (check-expect (update-mapping (list (make-pair "cat" 3.14) (make-pair "dog" 5)) "dog" sub1 2.5) (list (make-pair "cat" 3.14) (make-pair "dog" 4)))
Sample Problem Design the function add-to-counter, which given a [Counter X] and an X will add 1 to the previously associated count. If that element was not present, its count will be 1. Hint: do any of the functions provided by "mimic.rkt" seem helpful?
; add-to-counter : [Counter X] X -> [Counter X] ; Add 1 to x in c (define (add-to-counter c x) (update-mapping c x add1 1)) (check-expect (add-to-counter MARBLE-BAG "green") (list (make-pair "green" 3) (make-pair "red" 5))) (check-expect (add-to-counter MARBLE-BAG "brown") (list (make-pair "green" 2) (make-pair "red" 5) (make-pair "brown" 1)))
Sample Problem Design the function total-size, which grabs the total count of elements in a counter (there are 7 in MARBLE-BAG).
; total-size : [Counter X] -> Number ; The total size of c (define (total-size c) (foldr (λ (p so-far) (+ (pair-y p) so-far)) 0 c)) (check-expect (total-size MARBLE-BAG) 7)
Exercise 1 Design the function initiate-counter, which given an X creates a counter with one copy of that element. Be sure to follow the data definition.
Exercise 2 Define expected-counts, which given a counter and a natural number n, outputs a list of numbers representing the amount of times we would expect to see the elements of the counter if we randomly selected from it n times (with replacement for you probability whizzes). The provided tests should clarify this exercise.
You should also locally define some constant that will make sure you only compute the total size of the counter once.The signature, purpose, and tests have been provided for you below.
Exercise 3 Define count, that will take a [List-of X] and an X and determine how often it appears in the list. The signature, purpose, and tests, have been provided for you below.
Exercise 4 Define count-grabs, which given a [Counter X] and a [List-of X], sees how many times the elements from that counter appear in the list. The signature, purpose, and tests have been provided for you below.
; grab-random : [Counter X] -> X ; Randomly grab from this counter (define (grab-random c) (local (; grab : Nat [Counter X] -> X ; Grab the first element in c if its count is larger than n, ; otherwise reduce n by the count and recur (define (grab n c) (cond [(< n (pair-y (first c))) (pair-x (first c))] [else (grab (- n (pair-y (first c))) (rest c))]))) (grab (random (total-size c)) c)))
Note that we cannot write tests for this function directly since it randomly grabs an element of the counter. However, we can use the function we write in the next exercise along with our previous functions to test it.
Exercise 5 Define grab-n, which given a counter and a natural number n builds up a list in which we randomly grab (with replacement) from the counter n many times. The signature and purpose statement for the function have been provided below. Remember by convention, if a function ignores its input, we name that argument _.
Starter Code: The following check-expect should pass (most of the time) if all of your functions were well defined. What does this test mean in English? Try saying it out loud.
(check-within (count-grabs MARBLE-BAG (grab-n MARBLE-BAG 10000)) (expected-counts MARBLE-BAG 10000) 100)
The quote symbol is a special syntax which lets one write large lists quickly and easily. For example, '(1 2 #f ("a" ("b" ()))) is shorthand for (list 1 2 #f (list "a" (list "b" (list)))). You have already seen this many times when writing the empty list, '(). Experiment with it for a bit in the interactions window if desired, but as long as you can read the examples below you’re all set to continue.
; A WritingStyle is a [Mapping String [Counter String]] ; and represents how often some words follow another, ; along with what words start and end a sentence. ; The empty string is associated with words that start a sentence, ; and how many times a word ends a sentence can be ; determined by the count of "." in its associated Counter. ; A Sentence is a [List-of String]
'(("how" "are" "you") ("how" "am" "i") ("i" "am" "great"))
(define STYLE-EXAMPLE '(("great" (("." 1))) ("am" (("great" 1) ("i" 1))) ("i" (("am" 1) ("." 1))) ("" (("i" 1) ("how" 2))) ("how" (("am" 1) ("are" 1))) ("you" (("." 1))) ("are" (("you" 1)))))
Make sure you understand this example before continuing with the lab.
Exercise 6 Design the function add-to-ws, which given a WritingStyle ws and two Strings, first-word and second-word, updates ws to indicate that first-word was followed by second-word once more than indicated in ws. Look at the data definition for WritingStyle and use the previously defined and provided functions!
Exercise 7 Design the function update-ws, which given a Sentence and a WritingStyle, updates the writing style to indicate that the consecutive pairs of words in the list follow each other. Don’t worry if your function does not produce the same ordering as in STYLE-EXAMPLE; there are several ways to approach this problem.
Exercise 8 Design the function style, which given a [List-of Sentence] generates the writing style given by those sentences. Don’t forget to put "" at the beginning and "." at the end of each sentence.
Exercise 9 Design the function imitate, which given a WritingStyle, outputs a Sentence that could have been written in that style. To accomplish this, locally define a function next-word, which takes in a String current-word and outputs a Sentence. If current-word is equal to ".", next-word outputs the empty list. Otherwise, next-word will cons current-word onto the result of next-word called with a randomly selected String that follows current-word according to the writing style. Look at the data definition for WritingStyle and use the previously defined functions!
Initially, call next-word with "" to indicate the start of a sentence. Take the rest of the result to discard the empty string.
You have access to the following constants, given as a [List-of Sentence]:
THE-RAVEN, The Raven by Edgar Allan Poe
AMERICAN-PIE, American Pie by Don McLean
SCARLET-LETTER, the fifth chapter of The Scarlet Letter by Nathaniel Hawthorne
TEN-PLAGUES, the chapters in The Bible related to the ten plagues of Egypt
MATTHIAS, the Wikipedia entry on Matthias Felleisen
EPILOGUE, the epilogue of HTDP/2e
Starter Code: Here is a function you can use to imitate each writing style (if you have defined all your functions correctly):
; imitate-style : [List-of Sentence] -> Sentence ; Given many of someone's sentences, output one like it (define imitate-style (compose imitate style))
If you want to know more about compose, look in the documentation. Happy mimicking!
If you had trouble finishing any of the exercises in the lab or homework, or just feel like you’re struggling with any of the class material, please feel free to come to office hours and talk to a TA or tutor for additional assistance.