Lab 9: Lists (& Lists (& Lists))
Implement this lab with the Beginning Student Language.
Make sure you follow The Style we use for the {B,I,A}SL{,+} languages in this class.
Choose the initial Head and Hands, and get started!
A List of Strings
Ex 1: Create a recursive data definition ListOfStrings that can hold an arbitrarily many Strings. You may use a built-in data structure in BSL or define your own to implement your data definition.
Ex 2: Define four example ListOfStringss (los0-los3), including an empty ListOfStrings, a one-element ListOfStrings that contains the String "foo", a two-element ListOfStrings that contains both "Hello" and "world", and another, longer example of your choice.
Hint: If you’re having trouble creating these example ListOfStrings, ask one of your TAs to look over your data definition. The data definition should be written as the answer the question "What is a ListOfStrings?"
Ex 3: Create the template los-template : ListOfStrings -> ??? for all functions that operate on a ListOfStrings.
Ex 4: How many cases does your template include? In which case is a recursive call to the template made?
Working with Many Strings
Ex 5: Design a function fake-news that, given a ListOfStrings, returns a new ListOfStrings where each String in the original is replaced with the string "Fake News!".
Hint: Follow your template! The function fake-news should look almost identical to a correct los-template. If you have any trouble implementing fake-news, talk to a TA to see if your template is correct.
(check-expect (fake-news los0) (make-empty-los)) (check-expect (fake-news los1) (make-los "Fake News!" (make-empty-los))) (check-expect (fake-news los2) (make-los "Fake News!" (make-los "Fake News!" (make-empty-los))))
Note: You will probably need to modify the make-* function calls in above examples based on your implementation of ListOfStrings. The expected values are an empty ListOfStrings, a single-element ListOfStrings containing "Fake News!", and a two-element ListOfStrings containing two "Fake News!"s.
Ex 6: If you give fake-news a ListOfStrings of length N, what will be the length of the resulting ListOfStrings?
Ex 7: Design a function los-more-exciting that, given a ListOfStrings, returns a new ListOfStrings where each String has had "!" appended to its end.
(check-expect (more-exciting los0) (make-empty-los)) (check-expect (more-exciting los1) (make-los "foo!" (make-empty-los))) (check-expect (more-exciting los2) (make-los "Hello!" (make-los "world!" (make-empty-los))))
Ex 8: Design a function los-first-letter that, given a ListOfStrings, returns a new ListOfStrings where each String has been replaced with the first letter in that string.
(check-expect (los-first-letter los0) (make-empty-los)) (check-expect (los-first-letter los1) (make-los "f" (make-empty-los))) (check-expect (los-first-letter los2) (make-los "H" (make-los "w" (make-empty-los))))
Strings -> Other Things
Swap Head and Hands!
Ex 9: Design a function los-length that, given a ListOfStrings, returns the number of Strings in the list.
Ex 10: Design a function los-all-empty? that returns #true only when all Strings in the ListOfStrings are the empty string "". Make sure you test the function on inputs that return #true as well as inputs that return #false.
Note: The function los-all-empty? should still follow your template (i.e. have the same number of top-level cond cases) though it may use another cond expression inside one of those cases.
Hint: What should los-all-empty? return for an empty ListOfStrings? If you’re unsure, try answer these questions: How many Strings are there in an empty ListOfStrings? Are there any Strings that are not the empty String inside an empty ListOfStrings?
Ex 11: Design a function los-any-empty? that returns #true if any of the Strings in the ListOfStrings is the empty string "".
Hint: What should los-any-empty? return for an empty ListOfStrings? If you’re unsure, try answer these questions: How many Strings are there in an empty ListOfStrings? Are there any empty Strings inside an empty ListOfStrings?
Ex 12: Design a function los-all-non-empty? that returns #true only when all Strings in the ListOfStrings are non-empty.
Hint: What should los-all-non-empty? return for an empty ListOfStrings? If it returns the same answer as los-all-empty?, why? If not, why not?
Ex 13: Design a function count-chars that returns the sum of the number of characters in all Strings inside the given ListOfStrings.
Working with Many Numbers
Swap Head and Hands!
Ex 14: Create a recursive data definition ListOfNats that can hold an arbitrarily many Naturals (non-negative integers). You may use a built-in data structure in BSL or define your own to implement your data definition.
Ex 15: Define four example ListOfNatss (lon0-lon3), including an empty ListOfNats, a one-element ListOfNats that contains 4, a two-element ListOfNats that contains 0 and 10 and another, longer example of your choice.
Ex 16: Create the template lon-template : ListOfNats -> ??? for all functions that operate on a ListOfNats. How does it differ from lon-template. In what ways is it the same?
Ex 17: Design a function lon-count that returns the number of numbers inside the given ListOfNats. How does this function differ from los-count?
Ex 18: Design a function lon-sum that returns the sum of all numbers inside the given ListOfNats.
Hint: What should the result be for the sum of all numbers inside the empty ListOfNats?
Ex 19: Design a function lon-product that returns the product of all numbers inside the given ListOfNats.
Hint: What should the result be for the product of all numbers inside the empty ListOfNats?
Ex 20: Design a function lon-all-odd? that returns #true only when all numbers in the ListOfNats are odd. Make sure you test the function on inputs that return #true as well as inputs that return #false.
Note: The function lon-all-odd? should still follow your template (i.e. have the same number of top-level cond cases) though it may use another cond expression inside one of those cases.
Hint: What should lon-all-odd? return for an empty ListOfNats? How is this related to your answer for los-all-empty?’s base case?
Ex 21: Design a function lon-any-even? that returns #true if any of the numbers inside the given ListOfNats is even.
Ex 22: Design a function all-greater-than-n? that, given a ListOfNats and a Number n, returns #true only if all numbers inside the ListOfNats are greater than the given n.
Strings -> Numbers -> Strings
Swap Head and Hands!
Ex 21: Design a function strings->counts that, given a ListOfStrings, returns a ListOfNats containing the string-length of each String inside the original ListOfStrings.
Ex 22: Design a function count-chars/v2 that, given a ListOfStrings, returns the sum of the numbers of characters of each String in the list. Rather than following the template as in the original count-chars, use the functions strings->counts and lon-sum to achieve the same goal.
Ex 23: Design a function n-many-xs that, given a ListOfNats and a String x, returns a ListOfStrings where each number n in the given list has been replaced with a String with n-many repetitions of the given string x.
Hint: You may want to use replicate in your solution.
(check-expect (n-many-xs lon0 "131a rocks!") (make-empty-los)) (check-expect (n-many-xs lon1 "baz") (make-los "bazbazbazbaz" (make-empty-los))) (check-expect (n-many-xs lon2 "z") (make-los "" (make-los "zzzzzzzzzz" (make-empty-los))))
Ex 24: Design two functions redact and redact/v2 that, given a ListOfStrings, returns a ListOfStrings with each string replaced by a string of the same length, but all characters in the original Strings are replaced with "█". The first version should follow the los-template; the second version should instead be defined using the functions strings->counts and n-many-xs.