9 Using Abstractions to Mimic

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, Reloaded

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, as they are provided by "mimic.rkt").

; A {X Y} [Pair X Y] is a (list X Y)

(define pair? list?)

(define pair-x first)

(define pair-y second)

(define make-pair list)

; A {X Y} [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 2: Count Another Day

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)))

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.

; expected-counts : {X} [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 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.

; 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 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.

; 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))

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 _.

; 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)

The Fun Part

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!

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.