Lab 8 Games of Chance

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.
Mappings
Download the file mimic.rkt (with right-click > "Save As"...) and at the top of your file put the line (require "mimic.rkt"). Be sure to save it in the same directory as your lab program.
Consider the following data definitions and functions (do not copy the functions into your code, or comment them out if you do, 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 : {X, Y} [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 : {X, Y} [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)))
Counters
Starter Code: Below is a data definition and example of a Counter.
; A [Counter X] is a [Mapping X PosInt]
; and represents a multiset (a set of elements where an element can appear more than once)
 
(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 (Reviewed) 1 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?
Exercise (Reviewed) 2 Design the function total-size, which grabs the total count of elements in a counter (there are 7 in MARBLE-BAG). Use foldr.
Exercise 3 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 4 Define expected-counts, which given a counter and a natural number n, outputs a list of numbers representing how many times we would expect to see each element of the counter if we randomly selected from the counter n times (with replacement for you probability whizzes). The provided tests should clarify this exercise.
Use map. 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.
Have a staff member look over your answers before you continue by visiting them in their group call.
; expected-counts : {X, Y} [Counter X] Nat -> [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, that will take a [List-of X] and an X and determine how often it appears in the list. Use filter and length. The signature, purpose, and tests, have been provided for you below. Note you will have to use equal? here, as we don’t know what X is ahead of time.
; count : {X} [List-of X] X -> Nat
; How many times does x appear in the list?
(check-expect (count '() "b") 0)
(check-expect (count (list "a" "b" "a") "a") 2)
Exercise 6 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. The signature, purpose, and tests have been provided for you below.
; count-grabs : {X} [Counter X] [List-of X] -> [List-of Number]
; See how many times the elements from this counter are in this list
(check-expect (count-grabs '() '()) '())
(check-expect (count-grabs MARBLE-BAG (list "red" "green" "red" "red")) (list 1 3))
Starter Code: Below is the function grab-random, which randomly grabs an element from the counter in accordance with its distribution. For example, (grab-random MARBLE-BAG) should have a 2/7 chance of returning "green" and a 5/7 chance of returning "red". See if you can understand the code, but don’t worry if you can’t; what matters is understanding the signature and purpose statement.
; grab-random : {X} [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 7 Define grab-n, which given a counter and a natural number n builds up a list in which we randomly grab from the counter n many times. Use build-list. 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 _.
; grab-n : {X} [Counter X] Nat -> [List-of X]
; Grab from the counter n times
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)
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.
The Fun Part
Starter Code: Below is a data definition for a WritingStyle.
; 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]
For example, the following sentences:
(list (list "how" "are" "you") (list "how" "am" "i") (list "i" "am" "great"))
Should be represented by the following WritingStyle:
(define STYLE-EXAMPLE
  (list (list "great" (list (list "." 1)))
    (list "am" (list (list "great" 1) (list "i" 1)))
    (list "i" (list (list "am" 1) (list "." 1)))
    (list "" (list (list "i" 1) (list "how" 2)))
    (list "how" (list (list "am" 1) (list "are" 1)))
    (list "you" (list (list "." 1)))
    (list "are" (list (list "you" 1)))))
Make sure you understand this example before continuing with the lab.
Exercise 8 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 9 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. Note that if the list is less than two words long, nothing should change. 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 10 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. Use foldr.
Exercise 11 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!