Assignment 5: Much Ado About Lists

Assigned: Thursday, 6 October
Due: Friday, 14 October, 11:59 p.m. (This is later than usual; there isn’t an assignment going out next week)

Introduction

This assignment draws on some basic ideas about analyzing text. For some of these problems, we will tell you whether to use the built-in list operations (like map and filter) or an explicit recursive function (written with cases) like those we’ve designed in class this week.

Guidelines

  • Do not change the name of the file or the functions.

  • Remember to test your functions thoroughly and to write your code clearly. Your work will be graded on clarity and thorough testing, as well as on whether it works correctly.

  • Remember your resources:

Set up: A literary endeavor

Task: Copy and paste this code into your file:

include shared-gdrive("dcic-2021",
  "1wyQZj_L0qqV9Ekgr9au6RX2iqt2Ga8Ep")

include shared-gdrive("shakespeare-text.arr",
  "1-XGIpbC13ItjxCh7WY14cCjfygk5wz5x")

book-text

This provides you with book-text, a long text string, which you may recognize as Act I of William Shakespeare’s Much Ado About Nothing.

Task: Split book-text into a list of words, using Pyret’s string-split-all function. Name the resulting list of words split-text.

Part 1: Identifying characters

Let’s find the names of all the characters in the play. Following the usual style for a script, the names of characters are in ALL CAPS. To find which of the words in split-text are characters’ names, we want a function that takes a list of Strings representing a play and returns a list of every String that is a name of a character in the play, without duplicates.

Task: Write the function

fun find-characters(words :: List<String>) -> List<String>:
  ...
end

to find the unique character names in an input list, using only built-in list operators (no explicit recursion).

Notes:

  • The order of the characters in the list you return doesn’t matter.
  • You may wish to exclude words like "A", "I", and "O", which are ALL CAPS, but aren’t actually names.

Part 2: Tallying lines per character

Let’s find out how much each character has to say! The ALL-CAPS names mark the beginning of each character’s spoken lines in the text, so finding how often a character’s name occurs in all caps tell us (approximately) how often they speak.

Because this involves a separate count for each character, this is best represented using a table. The table can have two columns, "name" and "count", and a row for each character. For instance, two entries would be:

name count
BEATRICE 17
LEONATO 15

Task: Design a function

fun characters-table(char-names :: List<String>,
    play-text :: List<String>) -> Table:
  ...
end

that returns a table like above, where the rows for each character are in the same order that the names occur in the first input.

Do not use the built-in Table function count; the point of this exercise is to have you write that code for yourself.

There are two key tasks here:

  1. turning a list into a single-column table, and
  2. adding a column to a table from a list.

The starter code you included at the top provides functions for each of these tasks:

  • create-table-with-col(colname :: String, colvals :: List) -> Table

    This function creates a Table with one column.

  • add-col(t :: Table, name :: String, colvals :: List) -> Table

    This function adds a column to an existing table. The number of values in the colvals input must equal the number of rows in the Table t, and they will be added in order.

For example, this is how you could build a table of room seating capacity:

new-table = create-table-with-col("room", [list: "SC 006", "SP 309"])
add-col(new-table, "seats", [list: 20, 27])

While build-column can also add a column to a table, here we want you to practice programming with lists, so use add-col instead. You may use any combination of built-in operators and recursion to create the lists of column values.

You can solve this part however you like – using recursion, built-in operations, or both!

Part 3: Average word length

We now want to compute the average length of words in a list. While we could do this with a built-in mean function, it’s instructive to think about writing this out explicitly (because it’s a function you understand, but it illustrates a key point).

Task: Consider taking the average of the numbers in the list [list: 4, 5, 9]. Try to write out the sequence of where examples that reduce the list one element at a time. In a couple of sentences (in a comment), explain why this is harder than with other functions we’ve done this with in lecture.

When a function over lists doesn’t lend itself to developing such a sequence of examples, you have to break it into separate tasks, each of which can be done with a built-in list operator or expressed as such a sequence.

Task: Propose a list of tasks to compute the average length within a list of words. Write your list in a comment.

Now, using your task list as guidance:

Task: Write a function

fun average-word-length(list-of-words :: List<String>) -> Number:
  ...
end

that returns the average length of all words in the list, rounded to the nearest integer. (Use the built-in num-round to help with this.)

Raise an error if the list of words is empty.

You can implement the tasks however you like – using recursion, built-in operations, or both!

Part 4: Where art thou, Waldo?

Alarmingly, someone has defaced the text of Much Ado About Nothing, hiding the word "Waldo" somewhere in it.

Task: Write a function

fun find-waldo(text-string :: String) -> String:
  ...
end

that returns the word that occurs immediately after the first "Waldo" in that text. Solve this problem using a recursive helper function.

For example, if the string is

"the evening breeze rustled the Waldo leaves on the balcony",

then your function should return "leaves".

You may assume that "Waldo" will appear in the text and will not be the last word; you can choose the behavior of your function if either of these is not the case.

OPTIONAL Part 4

Now that we’ve seen recursion, we don’t need to rely on built-in functions like map or filter to work with lists. Try revisiting find-characters recursively:

Task: Write the function

fun find-characters-rec(words :: List<String>) -> List<String>:
  ...
end

to accomplish the same thing using explicit recursion. (You can still use distinct.)

If you haven’t yet seen how to write a recursive function that returns a list, read Section 10.4.

Submitting the assignment

  1. Hit Run then paste this check block into the Interactions Pane. All the tests should pass. If they don’t, that means you have a problem with one of the required functions. 
    check "Function name and input checks":
  t = table: name :: String, count :: Number end
  check-list = [list: ]
  find-characters(check-list)
  characters-table(check-list, check-list) is t
  average-word-length([list: "abcd", "ab"]) is 3
  find-waldo("Waldo hi") is "hi"
end

  2. Download your file (File → Download) and ensure it’s named asmt05.arr.

  3. Upload your assignment on Gradescope.

Note: You can submit as many times as you want before the deadline. Only your latest submission will be graded.

Acknowledgments

This assignment contains material adapted from

  • William Shakespeare
  • Kathi Fisler and colleagues at Brown University