<html> <style type=“text/css”> .comment { font-style: italic; color: #c0342d; } .name, .variable, code var, pre var { color: #9e5cb1; } .name { font-weight: bold; } .variable, pre var, code var { font-style: italic; } .keyword { color: #abafb3; } .builtin, .string { color: #417fb8; } .constant { color: #e89f27; } code.pyret { color: black; } table { margin: 1em auto; } table th, table td { padding: 1pt 4pt; font-size: 13pt; } div.dw-content a { text-decoration: underline; } div.dw-content p, div.dw-content li, div.dw-content li p { font-size: 13pt; margin-bottom: 1em; max-width: 750px; } p code, li code { font-size: 11pt; } blockquote { font-size: inherit; } pre kbd, code kbd { background: inherit; color: inherit; box-shadow: none; padding: 0; font: inherit; font-weight: bold; } a.secret { color: inherit; text-decoration: none !important; } a.secret:hover { text-decoration: underline !important; } ol li div.task p:first-child {
margin: 0;
} div.task, p.task {
background-color: #f2d4d7 !important; border: 1px solid #6366a !important; padding: 1em 2.25em; margin: 2em 1.5em;
} p.task, div.task p:first-child {
text-indent: -1.5em;
}
blockquote {
border: 0; margin: 1.5rem;
} </style>
<h1 id=“assignment-5-much-ado-about-lists”>Assignment 5: Much Ado About Lists</h1> <p><strong>Assigned</strong>: Thursday, 6 October <br /> <strong>Due</strong>: <strong><em>Friday</em></strong>, 14 October, 11:59 p.m. (This is later than usual; there isn’t an assignment going out next week)</p>
<h2 id=“introduction”>Introduction</h2> <p>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.</p>
<h2 id=“guidelines”>Guidelines</h2> <ul> <li><p>Do not change the name of the file or the functions.</p></li> <li><p>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.</p></li> <li><p>Remember your resources:</p> <ul> <li><a href=“https://www.cs.vassar.edu/~cs101/3/resources/tables.html”>Table documentation</a></li> <li><a href=“https://www.pyret.org/docs/latest/lists.html”>List documentation</a></li> <li><a href=“https://www.cs.vassar.edu/~cs101/3/resources/pyret.html”>Code clarity guide</a></li> <li>Coaches</li> <li>Your instructor</li> </ul></li> </ul>
<h2 id=“set-up-a-literary-endeavor”>Set up: A literary endeavor</h2>
<div class=“task”> <p><strong>Task</strong>: Copy and paste this code into your file:</p> <pre>
<span class="keyword">include</span> shared-gdrive(<span class="string">"dcic-2021"</span>, <span class="string">"1wyQZj_L0qqV9Ekgr9au6RX2iqt2Ga8Ep"</span>) <span class="keyword">include</span> shared-gdrive(<span class="string">"shakespeare-text.arr"</span>, <span class="string">"1-XGIpbC13ItjxCh7WY14cCjfygk5wz5x"</span>) book-text
</pre> </div>
<p>This provides you with
book-text
, a long text string, which you may recognize as Act I of William Shakespeare’s <em>Much Ado About Nothing</em>.</p>
<div class=“task”> <p><strong>Task</strong>: Split
book-text
into a list of words, using Pyret’s <a href=“https://www.pyret.org/docs/latest/strings.html#%28part._strings_string-split-all%29”>
string-split-all
</a> function. Name the resulting list of words
split-text
.</p> </div>
<h2 id=“part-1-identifying-characters”>Part 1: Identifying characters</h2>
<p>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, <em>without duplicates</em>.</p>
<div class=“task”> <p><strong>Task</strong>: Write the function</p> <pre class=“pyret”><span class=“keyword”>fun</span> <span class=“name”>find-characters</span>(words :: List<String>) -> List<String>:
...
<span class=“keyword”>end</span> </pre> <p>to find the unique character names in an input list, using only <a href=“https://www.pyret.org/docs/latest/lists.html”>built-in list operators</a> (no explicit recursion).</p> </div>
<p>Notes:</p> <ul> <li>The order of the characters in the list you return doesn’t matter.</li>
<li>You may wish to exclude words like
"A"
,
"I"
, and
"O"
, which are ALL CAPS, but aren’t actually names.</li> </ul>
<h2 id=“part-2-tallying-lines-per-character”>Part 2: Tallying lines per character</h2>
<p>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.</p>
<p>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:</p>
<blockquote> <table> <thead> <tr class=“header”> <th>name</th> <th>count</th> </tr> </thead> <tbody> <tr class=“odd”> <td>BEATRICE</td> <td>17</td> </tr> <tr class=“even”> <td>LEONATO</td> <td>15</td> </tr> </tbody> </table> </blockquote>
<div class=“task”> <p><strong>Task</strong>: Design a function</p> <pre class=“pyret”><span class=“keyword”>fun</span> <span class=“name”>characters-table</span>(char-names :: List<String>,
play-text :: List<String>) -> Table: ...
<span class=“keyword”>end</span> </pre> <p>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.</p> </div>
<p>Do not use the built-in Table function
count
; the point of this exercise is to have you write that code for yourself.</p>
<p>There are two key tasks here:</p> <ol> <li>turning a list into a single-column table, and</li> <li>adding a column to a table from a list.</li> </ol> <p>The starter code you included at the top provides functions for each of these tasks:</p>
<ul> <li><p>
create-table-with-col(colname :: String, colvals :: List) -> Table
</p> <p>This function creates a Table with one column.</p></li> <li><p>
add-col(t :: Table, name :: String, colvals :: List) -> Table
</p> <p>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.</p></li> </ul>
<p>For example, this is how you could build a table of room seating capacity:</p>
<pre class=“pyret”><var>new-table</var> = create-table-with-col(<span class=“string”>"room"</span>, [<span class=“keyword”>list</span>: <span class=“string”>"SC 006"</span>, <span class=“string”>"SP 309"</span>]) add-col(new-table, <span class=“string”>"seats"</span>, [<span class=“keyword”>list</span>: 20, 27]) </pre>
<p>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.</p>
<p>You can solve this part however you like – using recursion, built-in operations, or both!</p>
<h2 id=“part-3-average-word-length”>Part 3: Average word length</h2>
<p>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).</p>
<div class=“task”> <p><strong>Task</strong>: Consider taking the average of the numbers in the list
[<span class="keyword">list</span>: 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.</p> </div>
<p>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.</p>
<div class=“task”> <p><strong>Task</strong>: Propose a list of tasks to compute the average length within a list of words. Write your list in a comment.</p> </div>
<p>Now, using your task list as guidance:</p>
<div class=“task”> <p><strong>Task</strong>: Write a function</p> <pre class=“pyret”><span class=“keyword”>fun</span> <span class=“name”>average-word-length</span>(list-of-words :: List<String>) -> Number:
...
<span class=“keyword”>end</span> </pre> <p>that returns the average length of all words in the list, rounded to the nearest integer. (Use the built-in <a href=“https://www.pyret.org/docs/latest/numbers.html#%28part._numbers_num-round%29”>
num-round
</a> to help with this.)</p> </div>
<p><a href=“https://www.pyret.org/docs/latest/_global_.html#%28part._~3cglobal~3e_raise%29”>Raise</a> an error if the list of words is empty.</p>
<p>You can implement the tasks however you like – using recursion, built-in operations, or both!</p>
<h2 id=“part-4-where-art-thou-waldo”>Part 4: Where art thou, <a href=“https://en.wikipedia.org/wiki/Where%27s_Wally%3F”>Waldo</a>?</h2>
<p>Alarmingly, someone has defaced the text of <em>Much Ado About Nothing</em>, hiding the word
"Waldo"
somewhere in it.</p>
<div class=“task”> <p><strong>Task</strong>: Write a function</p> <pre class=“pyret”><span class=“keyword”>fun</span> <span class=“name”>find-waldo</span>(text-string :: String) -> String:
...
<span class=“keyword”>end</span> </code></pre> <p>that returns the word that occurs immediately after the first
"Waldo"
in that text. Solve this problem using a recursive helper function.</p> </div>
<p>For example, if the string is</p> <blockquote> <p>
"the evening breeze rustled the Waldo leaves on the balcony"
,</p> </blockquote> <p>then your function should return
"leaves"
.</p> <p>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.</p>
<h2>OPTIONAL Part 4</h2>
<p>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:</p>
<div class=“task”> <p><strong>Task</strong>: Write the function</p> <pre class=“pyret”><span class=“keyword”>fun</span> <span class=“name”>find-characters-rec</span>(words :: List<String>) -> List<String>:
...
<span class=“keyword”>end</span> </pre> <p>to accomplish the same thing using explicit recursion. (You can still use
distinct
.)</p> </div>
<p>If you haven’t yet seen how to write a recursive function that returns a list, read <a href=“https://dcic-world.org/2022-08-28/processing-lists.html#%28part._.Structural_.Problems_that_.Transform_.Lists%29”>Section 10.4</a>.</p>
<h2 id=“submitting-the-assignment”>Submitting the assignment</h2>
<ol> <li> Hit <em>Run</em> 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.
<pre class=“pyret”> <span class=“keyword”>check</span> <span class=“string”>“Function name and input checks”</span>:
<var>t</var> = <span class="keyword">table</span>: name :: String, count :: Number <span class="keyword">end</span> <var>check-list</var> = [<span class="keyword">list</span>: ] find-characters(check-list) characters-table(check-list, check-list) <span class="keyword">is</span> t average-word-length([<span class="keyword">list</span>: <span class="string">"abcd"</span>, <span class="string">"ab"</span>]) <span class="keyword">is</span> 3 find-waldo(<span class="string">"Waldo hi"</span>) <span class="keyword">is</span> <span class="string">"hi"</span>
end </pre> </li>
<li><p>Download your file (<em>File</em> → <em>Download</em>) and ensure it’s named
asmt05.arr
.</p></li>
<li><p>Upload your assignment on <a href=“https://www.gradescope.com”>Gradescope</a>.</p></li> </ol> <p><strong>Note</strong>: You can submit as many times as you want before the deadline. Only your latest submission will be graded.</p>
<h2 id=“acknowledgments”>Acknowledgments</h2>
<p>This assignment contains material adapted from</p> <ul> <li>William Shakespeare</li> <li>Kathi Fisler and colleagues at Brown University</li> </ul> </html>