Lab 8: 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.

NEW PARTNERS: Starting with this lab, you have a new partner assignment. Check Piazza for your new partner. Introduce yourself, exchange contact information, and get to work. You will be working together in lab and starting with the current assignment (going out tonight).

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.