Lab 7 Using Abstractions to Mimic
Purpose: The purpose of this lab is to practice the use of existing list-processing functions.
Textbook References: Chapter 16.1: Existing Abstractions
Note: only use existing abstractions in this lab when the lab tells you to.
Mappings
; 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:
Sample Problem Design the function get, which given a [Mapping X Y] m and an X x, will return the first data associated with x. If it is not in the mapping, throw an error.
; get : [Mapping X Y] X -> Y ; Get the value in m associated with x (define (get m x) (cond [(empty? m) (error "not found")] [else (if (equal? x (pair-x (first m))) (pair-y (first m)) (get (rest m) x))])) (check-error (get '((3 three)) 4) "not found") (check-expect (get '((3 three) (4 four)) 4) 'four)
Sample Problem Design the function update-mapping, which given a [Mapping X Y] m, an X x, a [Y -> Y] updater, and a Y backup, will update the data associated with x in m by using updater. If x is not in m, it will now be associated with backup.
; update-mapping : [Mapping X Y] X [Y -> Y] Y -> [Mapping X Y] ; Update the data associated with x in m using updater ; If x is not in m, associate it with backup (define (update-mapping m x updater backup) (cond [(empty? m) (list (make-pair x backup))] [else (if (equal? x (pair-x (first m))) (cons (make-pair x (updater (pair-y (first m)))) (rest m)) (cons (first m) (update-mapping (rest m) x updater backup)))])) (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)))
Counters
; A [Counter X] is a [Mapping X PosInt] ; and represents a multiset (define MARBLE-BAG (list (make-pair 'green 2) (make-pair 'red 5))) ; MARBLE-BAG represents a bag with 2 'green marbles and 5 'red ones
Exercise 1 Design the function add-to-counter, which given a Counter and an X will add 1 to the previously associated count. If that X was not present, its count will be 1.
Hint: Use your previously defined functions.
Exercise 2 Design the function total-size, which grabs the total count of elements in a counter (there are 7 in MARBLE-BAG). Use foldr. What helper function will you have to locally define?
Exercise 3 Define count, that will take a [List-of X] and an X and determine how often it appears in the list. Use filter and length. What function will you have to locally define? The signature, purpose, and tests, have been provided for you below.
; count : [List-of X] X -> N ; How many times does x appear in the list? (check-expect (count '() 'b) 0) (check-expect (count '(a b a) 'a) 2)
Exercise 4 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.
Use map. What function will you have to locally define? 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.
; expected-counts : [Counter X] N -> [List-of Number] ; Expected counts of elements when grabbing from the counter n times (check-expect (expected-counts '() 100) '()) (check-expect (expected-counts MARBLE-BAG 1000) (list (* 2/7 1000) (* 5/7 1000)))
Exercise 5 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. Use map. What function will you have to locally define? The signature, purpose, and tests have been provided for you below.
; count-grabs : [Counter X] [List-of X] -> [List-of N] ; See how many times the elements from this counter are in this list (check-expect (count-grabs '() '()) '()) (check-expect (count-grabs MARBLE-BAG '(red green red red)) '(1 3))
; grab-random : [Counter X] -> X ; Randomly grab from this counter (define (grab-random c) (local (; grab : N [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 6 Define grab-n, which given a counter and a natural number builds up a list in which we randomly grab from the counter that many times. Use build-list. What function will you have to locally define? The signature and purpose statement for the function have been provided below.
Note: By convention, if a function ignores its input, we name that argument _.
; grab-n : [Counter X] N -> [List-of X] ; Grab from the counter n times
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 Fun Part
; 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 7 Design the function add-to-ws, which given a WritingStyle ws and two Strings, first-word and second-word, updates the writing style 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 your previously defined functions!
Exercise 8 Design the function update-ws, which given a WritingStyle and a Sentence, updates the WritingStyle to indicate that the consecutive pairs of words in the list follow each other. Note that if the list is less than two words long, nothing should change.
Exercise 9 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 (Hint: append). Use foldr.
Exercise 10 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 the string ".", 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 your 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.
Download the file corpus.rkt (with right-click > "Save As"...) and at the top of your file put the line (require "corpus.rkt"). Be sure to save it in the same directory as your lab program.
You now have access to the following constants, given as [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
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.
Before you go...
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.