<div class="xblock xblock-public_view xblock-public_view-vertical" data-has-score="False" data-runtime-class="LmsRuntime" data-graded="True" data-request-token="3f7f1aefe9a311efbd7412d4917dea95" data-runtime-version="1" data-block-type="vertical" data-course-id="course-v1:MITx+6.005.2x+1T2017" data-init="VerticalStudentView" data-usage-id="block-v1:MITx+6.005.2x+1T2017+type@vertical+block@vertical-recursive-data-types">
<h2 class="hd hd-2 unit-title">Reading 2 Objectives</h2>
<div class="vert-mod">
<div class="vert vert-0" data-id="block-v1:MITx+6.005.2x+1T2017+type@html+block@html_94a61630be46">
<div class="xblock xblock-public_view xblock-public_view-html xmodule_display xmodule_HtmlBlock" data-has-score="False" data-runtime-class="LmsRuntime" data-graded="True" data-request-token="3f7f1aefe9a311efbd7412d4917dea95" data-runtime-version="1" data-block-type="html" data-course-id="course-v1:MITx+6.005.2x+1T2017" data-init="XBlockToXModuleShim" data-usage-id="block-v1:MITx+6.005.2x+1T2017+type@html+block@html_94a61630be46">
<script type="json/xblock-args" class="xblock-json-init-args">
{"xmodule-type": "HTMLModule"}
</script>
<link href="/assets/courseware/v1/b2188f0a95a7a9062748278f7d5a584f/asset-v1:MITx+6.005.2x+1T2017+type@asset+block/syntax-highlighting.css" rel="stylesheet" type="text/css" />
<h4>Software in 6.005</h4>
<table class="table table-striped no-markdown">
<tbody>
<tr>
<th width="33%">Safe from bugs</th>
<th>Easy to understand</th>
<th>Ready for change</th>
</tr>
<tr>
<td>
Correct today and correct in the unknown future.
</td>
<td>
Communicating clearly with future programmers, including future you.
</td>
<td>
Designed to accommodate change without rewriting.
</td>
</tr>
</tbody>
</table>
<h4>Objectives</h4>
<ul>
<li>Understand recursive datatypes</li>
<li>Read and write datatype definitions</li>
<li>Understand and implement functions over recursive datatypes</li>
<li>Understand immutable lists and know the standard operations on immutable lists</li>
<li>Know and follow a recipe for writing programs with ADTs</li>
</ul>
</div>
</div>
</div>
</div>
<div class="xblock xblock-public_view xblock-public_view-vertical" data-has-score="False" data-runtime-class="LmsRuntime" data-graded="True" data-request-token="3f7f1aefe9a311efbd7412d4917dea95" data-runtime-version="1" data-block-type="vertical" data-course-id="course-v1:MITx+6.005.2x+1T2017" data-init="VerticalStudentView" data-usage-id="block-v1:MITx+6.005.2x+1T2017+type@vertical+block@Immutable_lists">
<h2 class="hd hd-2 unit-title">Immutable lists</h2>
<div class="vert-mod">
<div class="vert vert-0" data-id="block-v1:MITx+6.005.2x+1T2017+type@html+block@html_e5065823f1b3">
<div class="xblock xblock-public_view xblock-public_view-html xmodule_display xmodule_HtmlBlock" data-has-score="False" data-runtime-class="LmsRuntime" data-graded="True" data-request-token="3f7f1aefe9a311efbd7412d4917dea95" data-runtime-version="1" data-block-type="html" data-course-id="course-v1:MITx+6.005.2x+1T2017" data-init="XBlockToXModuleShim" data-usage-id="block-v1:MITx+6.005.2x+1T2017+type@html+block@html_e5065823f1b3">
<script type="json/xblock-args" class="xblock-json-init-args">
{"xmodule-type": "HTMLModule"}
</script>
<link href="/assets/courseware/v1/b2188f0a95a7a9062748278f7d5a584f/asset-v1:MITx+6.005.2x+1T2017+type@asset+block/syntax-highlighting.css" rel="stylesheet" type="text/css" />
<!--
<script src="https://ajax.googleapis.com/ajax/libs/jquery/3.1.1/jquery.min.js"></script>
<script>
$(function() {
// create a hover interaction
// will either update an attribute of a target element inside this element,
// or show only targets matching an indexed selector, as the user hovers over
// elements matching a selector
function createHoverInteraction() {
var elt = $(this);
var selector = elt.data('selector');
var target = $(elt.data('target'), elt);
var pick = elt.data('pick');
if (pick) {
var updateTarget = function() {
var filter = pick.replace(/INDEX/g, $(this).index()+1);
target.hide().filter(filter).show();
}
} else {
var attr = elt.data('attr');
var template = elt.data('template');
var updateTarget = function() {
var value = template.replace(/INDEX/g, $(this).index());
target.attr(attr, value);
}
}
var update = function() {
$(this).addClass('highlighted').siblings().removeClass('highlighted');
updateTarget.apply(this);
}
$(selector).addClass('hover-figure-select').on('click mouseenter', update);
update.apply($(selector).first());
}
// wire up interactive elements
$('.hover-figure').each(createHoverInteraction);
});
</script>
<style>
.hover-figure-select {
cursor: default;
}
.highlighted {
background: #fcf8e3;
box-shadow: 0 0 0 4px #fcf8e3;
}
</style>
-->
<h2 id="introduction">Introduction</h2>
<div data-outline="introduction">
<p>In this reading we'll look at recursively-defined types, how to specify operations on such types, and how to implement them. Our main example will be <em>immutable lists</em>.</p>
<p>Then we'll use another recursive datatype example, <em>matrix multiplications</em>, to walk through our process for programming with ADTs.</p>
</div>
<style>
/* recursive data types styles */
.table-fields table td p {
margin-bottom: 0;
}
.table-fields table td input[type=text].form-control {
width: 100% !important;
}
</style>
<h2 id="recursive_functions">Recursive functions</h2>
<div data-outline="recursive_functions">
<p>Before we introduce recursive datatypes — which have a recursive structure of both data and computation — take a minute to review <a href="/courses/course-v1:MITx+6.005.2x+1T2017/jump_to_id/vertical-recursion-reading">recursive computations</a>.</p>
<p>Just as a recursive function is defined in terms of itself, a <em>recursive datatype</em> is defined in terms of itself. We'll see the same need for <em>base</em> and <em>recursive</em> cases, which will now appear as different <em>variants</em> of the abstract type.</p>
</div>
<h2 id="immutable_lists">Immutable lists</h2>
<div data-outline="immutable_lists">
<p>We'll start with a classic recursive datatype, the <em>immutable list</em>.</p>
<p>Immutability is powerful not just because of its safety, but also because of the potential for sharing. Sharing actually produces performance benefits: less memory consumed, less time spent copying. Here we're going to look at how to represent list data structures differently than in our familiar array lists or linked lists. </p>
<p>Let's define a data type for an immutable list, <code>ImList<E></code>. The data type has four fundamental operations:</p>
<table class="table table-condensed no-markdown">
<tbody>
<tr>
<th>empty: void → ImList</th>
<td>// returns an empty list</td>
</tr>
<tr>
<th style="white-space:nowrap">cons: E × ImList → ImList </th>
<td>// returns a new list formed by adding an element to the front of another list</td>
</tr>
<tr>
<th>first: ImList → E</th>
<td>// returns the first element of a list, requires the list to be nonempty</td>
</tr>
<tr>
<th>rest: ImList → ImList</th>
<td>// returns the list of all elements of this list except for the first, requires the list to be nonempty</td>
</tr>
</tbody>
</table>
<p>These four operations have a long and distinguished pedigree. They are fundamental to the list-processing languages <a href="http://en.wikipedia.org/wiki/Lisp_(programming_language)">Lisp</a> and <a href="http://en.wikipedia.org/wiki/Scheme_(programming_language)">Scheme</a> (where for historical reasons they are called nil, <a href="http://en.wikipedia.org/wiki/Cons">cons</a>, <a href="http://en.wikipedia.org/wiki/CAR_and_CDR">car, and cdr</a>, respectively). They are widely used in functional programming, where you can often find them called head and tail instead of <em>first</em> and <em>rest</em>.</p>
<p>Before we design Java classes to implement this datatype, let's get used to the operations a bit, using lists of integers. We'll write lists with square brackets, like [ 1, 2, 3 ], and we'll write the operations as if they are mathematical functions. Once we get to Java, the syntax will look different but the operations will have the same meaning.</p>
<blockquote>
<p>empty() = [ ]</p>
<p>cons(0, empty() ) = [ 0 ]</p>
<p>cons(0, cons(1, cons(2, empty() ) ) ) = [ 0, 1, 2 ]</p>
<p>x ≡ cons(0, cons(1, cons(2, empty() ) ) ) = [ 0, 1, 2 ]</p>
<p>first(x) = 0</p>
<p>rest(x) = [ 1, 2 ]</p>
<p>first(rest(x) ) = 1</p>
<p>rest(rest(x) ) = [ 2 ]</p>
<p>first(rest(rest(x) ) = 2</p>
<p>rest(rest(rest(x) ) ) = [ ]</p>
</blockquote>
<p>The fundamental relationship between <em>first</em>, <em>rest</em>, and <em>cons</em> is:</p>
<blockquote>
<p>first(cons(elt, lst) ) = elt
<br> rest(cons(elt, lst) ) = lst</p>
</blockquote>
<p>What <em>cons</em> puts together, <em>first</em> and <em>rest</em> peel back apart.</p>
<h3 id="immutable_lists_in_java">Immutable lists in Java</h3>
<div data-outline="immutable_lists_in_java">
<p>To implement this datatype in Java, we'll use an interface:</p>
<div class="pull-left" style="min-width: 65%; margin-right: 20px;"><pre><code class="language-java hljs"><span class="hljs-keyword">public</span> <span class="hljs-class"><span class="hljs-keyword">interface</span> <span class="hljs-title">ImList</span><<span class="hljs-title">E</span>> </span>{
<span class="hljs-function"><span class="hljs-keyword">public static</span> ImList<E> <span class="hljs-title">empty</span><span class="hljs-params">()</span></span>; <span class="hljs-comment">// not quite right yet, see below</span>
<span class="hljs-function"><span class="hljs-keyword">public</span> ImList<E> <span class="hljs-title">cons</span><span class="hljs-params">(E e)</span></span>;
<span class="hljs-function"><span class="hljs-keyword">public</span> E <span class="hljs-title">first</span><span class="hljs-params">()</span></span>;
<span class="hljs-function"><span class="hljs-keyword">public</span> ImList<E> <span class="hljs-title">rest</span><span class="hljs-params">()</span></span>;
}</code></pre></div>
<div class="pull-margin">
<p>This interface declares a <em>generic type</em> <code>ImList<E></code> that can be instantiated for any type <code>E</code>: <code>ImList<Integer></code>, <code>ImList<String></code>, etc. The <code>E</code> in these declarations is a placeholder that the compiler will fill in when it checks our code for type safety.</p>
</div>
<div class="clearfix"></div>
<p>And we'll write two classes that implement this interface:</p>
<ul>
<li><code>Empty</code> represents the result of the <em>empty</em> operation (an empty list)</li>
<li><code>Cons</code> represents the result of a <em>cons</em> operation (an element glued together with another list)</li>
</ul><pre><code class="language-java hljs"><span class="hljs-keyword">public</span> <span class="hljs-class"><span class="hljs-keyword">class</span> <span class="hljs-title">Empty</span><<span class="hljs-title">E</span>> <span class="hljs-keyword">implements</span> <span class="hljs-title">ImList</span><<span class="hljs-title">E</span>> </span>{
<span class="hljs-function"><span class="hljs-keyword">public</span> <span class="hljs-title">Empty</span><span class="hljs-params">()</span> </span>{
}
<span class="hljs-function"><span class="hljs-keyword">public</span> ImList<E> <span class="hljs-title">cons</span><span class="hljs-params">(E e)</span> </span>{
<span class="hljs-keyword">return</span> <span class="hljs-keyword">new</span> Cons<>(e, <span class="hljs-keyword">this</span>);
}
<span class="hljs-function"><span class="hljs-keyword">public</span> E <span class="hljs-title">first</span><span class="hljs-params">()</span> </span>{
<span class="hljs-keyword">throw</span> <span class="hljs-keyword">new</span> UnsupportedOperationException();
}
<span class="hljs-function"><span class="hljs-keyword">public</span> ImList<E> <span class="hljs-title">rest</span><span class="hljs-params">()</span> </span>{
<span class="hljs-keyword">throw</span> <span class="hljs-keyword">new</span> UnsupportedOperationException();
}
}</code></pre><pre><code class="language-java hljs"><span class="hljs-keyword">public</span> <span class="hljs-class"><span class="hljs-keyword">class</span> <span class="hljs-title">Cons</span><<span class="hljs-title">E</span>> <span class="hljs-keyword">implements</span> <span class="hljs-title">ImList</span><<span class="hljs-title">E</span>> </span>{
<span class="hljs-keyword">private</span> <span class="hljs-keyword">final</span> E e;
<span class="hljs-keyword">private</span> <span class="hljs-keyword">final</span> ImList<E> rest;
<span class="hljs-function"><span class="hljs-keyword">public</span> <span class="hljs-title">Cons</span><span class="hljs-params">(E e, ImList<E> rest)</span> </span>{
<span class="hljs-keyword">this</span>.e = e;
<span class="hljs-keyword">this</span>.rest = rest;
}
<span class="hljs-function"><span class="hljs-keyword">public</span> ImList<E> <span class="hljs-title">cons</span><span class="hljs-params">(E e)</span> </span>{
<span class="hljs-keyword">return</span> <span class="hljs-keyword">new</span> Cons<>(e, <span class="hljs-keyword">this</span>);
}
<span class="hljs-function"><span class="hljs-keyword">public</span> E <span class="hljs-title">first</span><span class="hljs-params">()</span> </span>{
<span class="hljs-keyword">return</span> e;
}
<span class="hljs-function"><span class="hljs-keyword">public</span> ImList<E> <span class="hljs-title">rest</span><span class="hljs-params">()</span> </span>{
<span class="hljs-keyword">return</span> rest;
}
}</code></pre>
<p>So we have methods for <em>cons</em>, <em>first</em>, and <em>rest</em>, but where is the fourth operation of our datatype, <em>empty</em>?</p>
<p>One way to implement <em>empty</em> is to have clients call the <code>Empty</code> class constructor to obtain empty lists. This sacrifices representation independence — clients have to know about the <code>Empty</code> class!</p>
<p>As we saw in <a href="//courses.edx.org/courses/course-v1:MITx+6.005.1x+3T2016/jump_to_id/vertical-interfaces"><em>Interfaces</em></a>, a better way to do it is as a static factory method that takes no arguments and produces an instance of <code>Empty</code>. We can put this static method in the <code>ImList</code> interface along with the other operations. This choice was <em>not possible</em> in previous versions of Java, which is why we still write code like:</p><pre><code class="hljs javascript">List<<span class="hljs-built_in">String</span>> z = <span class="hljs-keyword">new</span> ArrayList<>();
</code></pre>
<p>Perhaps someday Java will offer a <code>List.empty()</code> method to obtain new empty <code>List</code>s, but not yet.</p>
<p>We will go ahead and update our <code>ImList</code> interface with the static <code>empty</code> method:</p>
<div class="pull-left" style="min-width: 65%; margin-right: 20px;"><pre><code class="language-java hljs"><span class="hljs-keyword">public</span> <span class="hljs-class"><span class="hljs-keyword">interface</span> <span class="hljs-title">ImList</span><<span class="hljs-title">E</span>> </span>{
<span class="hljs-keyword">public</span> <span class="hljs-keyword">static</span> <E> <span class="hljs-function">ImList<E> <span class="hljs-title">empty</span><span class="hljs-params">()</span> </span>{
<span class="hljs-keyword">return</span> <span class="hljs-keyword">new</span> Empty<>();
}
<span class="hljs-function"><span class="hljs-keyword">public</span> ImList<E> <span class="hljs-title">cons</span><span class="hljs-params">(E e)</span></span>;
<span class="hljs-function"><span class="hljs-keyword">public</span> E <span class="hljs-title">first</span><span class="hljs-params">()</span></span>;
<span class="hljs-function"><span class="hljs-keyword">public</span> ImList<E> <span class="hljs-title">rest</span><span class="hljs-params">()</span></span>;
}</code></pre></div>
<div class="pull-margin">
<p>The signature for <code>empty</code> uses a new bit of generic type syntax. The <code>E</code> in <code>ImList<E></code> is a placeholder for the type of elements in an instance of <code>ImList</code>, but <code>empty</code> is a static method: it cannot see instance variables or methods, and it also cannot see the instance type parameter. You can read the declaration of <code>empty</code> as: “for any <code>E</code>, <code>empty()</code> returns an <code>ImList<E></code>.”</p>
</div>
<div class="clearfix"></div>
<p>Now that we have all the operations, here's some actual Java code that parallels the abstract examples we wrote earlier.
</p>
<!--
Hover or tap on each row in the table to update the snapshot diagram:</p>
<div class="panel panel-figure inline-figure hover-figure no-markdown col-sm-12 col-lg-10" data-selector="#imlist-examples tbody tr" data-target="img" data-attr="src" data-template="/asset-v1:MITx+6.005.2x+1T2017+type@asset+block/02-imlistINDEX.png"><img src="/assets/courseware/v1/10f3450ec346df453e7320ca34863059/asset-v1:MITx+6.005.2x+1T2017+type@asset+block/02-imlist0.png"></div>
-->
<div id="imlist-examples">
<table class="table">
<thead>
<tr>
<th>Java syntax</th>
<th>Functional syntax</th>
<th>Result</th>
</tr>
</thead>
<tbody>
<tr class="highlighted">
<td><code>ImList<Integer> nil = ImList.empty();</code></td>
<td><em>nil = empty()</em></td>
<td>[ ]</td>
</tr>
<tr>
<td><code>nil.cons(0)</code></td>
<td><em>cons(0, nil)</em></td>
<td>[ 0 ]</td>
</tr>
<tr>
<td><code>nil.cons(2).cons(1).cons(0)</code></td>
<td><em>cons(0, cons(1, cons(2, nil)))</em></td>
<td>[ 0, 1, 2 ]</td>
</tr>
<tr>
<td><code>ImList<Integer> x = nil.cons(2).cons(1).cons(0);</code></td>
<td><em>x = cons(0, cons(1, cons(2, nil)))</em></td>
<td>[ 0, 1, 2 ]</td>
</tr>
<tr>
<td><code>x.first()</code></td>
<td><em>first(x)</em></td>
<td>0</td>
</tr>
<tr>
<td><code>x.rest()</code></td>
<td><em>rest(x)</em></td>
<td>[ 1, 2 ]</td>
</tr>
<tr>
<td><code>x.rest().first()</code></td>
<td><em>first(rest(x))</em></td>
<td>1</td>
</tr>
<tr>
<td><code>x.rest().rest()</code></td>
<td><em>rest(rest(x))</em></td>
<td>[ 2 ]</td>
</tr>
<tr>
<td><code>x.rest().rest().first()</code></td>
<td><em>first(rest(rest(x)))</em></td>
<td>2</td>
</tr>
<tr>
<td><code>x.rest().rest().rest()</code></td>
<td><em>rest(rest(rest(x)))</em></td>
<td>[ ]</td>
</tr>
<tr>
<td><code>ImList<Integer> y = x.rest().cons(4);</code></td>
<td><em>y = cons(4, rest(x))</em></td>
<td>[ 4, 1, 2 ]</td>
</tr>
</tbody>
</table>
</div>
<p>The key thing to note here is the <em>sharing of structure</em> that immutable list provides. In the last example above, <code>x</code> and <code>y</code> are sharing their representation of the sublist [ 1, 2 ].</p>
</div>
<h3 id="two_classes_implementing_one_interface">Two classes implementing one interface</h3>
<div data-outline="two_classes_implementing_one_interface">
<p>Note that this design is different from what we have seen with <code>List</code>, <code>ArrayList</code>, and <code>LinkedList</code>.
<code>List</code> is an abstract data type and <code>ArrayList</code> and <code>LinkedList</code> are two <em>alternative</em> concrete representations for that datatype.</p>
<p>For <code>ImList</code>, the two implementations <code>Empty</code> and <code>Cons</code> <em>cooperate</em> in order to implement the datatype — you need them both.</p>
</div>
</div>
</div>
</div>
</div>
<div class="xblock xblock-public_view xblock-public_view-vertical" data-has-score="False" data-runtime-class="LmsRuntime" data-graded="True" data-request-token="3f7f1aefe9a311efbd7412d4917dea95" data-runtime-version="1" data-block-type="vertical" data-course-id="course-v1:MITx+6.005.2x+1T2017" data-init="VerticalStudentView" data-usage-id="block-v1:MITx+6.005.2x+1T2017+type@vertical+block@vertical_Questions_06a647f615b5">
<h2 class="hd hd-2 unit-title">Questions</h2>
<div class="vert-mod">
<div class="vert vert-0" data-id="block-v1:MITx+6.005.2x+1T2017+type@html+block@Immutable_lists">
<div class="xblock xblock-public_view xblock-public_view-html xmodule_display xmodule_HtmlBlock" data-has-score="False" data-runtime-class="LmsRuntime" data-graded="True" data-request-token="3f7f1aefe9a311efbd7412d4917dea95" data-runtime-version="1" data-block-type="html" data-course-id="course-v1:MITx+6.005.2x+1T2017" data-init="XBlockToXModuleShim" data-usage-id="block-v1:MITx+6.005.2x+1T2017+type@html+block@Immutable_lists">
<script type="json/xblock-args" class="xblock-json-init-args">
{"xmodule-type": "HTMLModule"}
</script>
<link href="/assets/courseware/v1/b2188f0a95a7a9062748278f7d5a584f/asset-v1:MITx+6.005.2x+1T2017+type@asset+block/syntax-highlighting.css" rel="stylesheet" type="text/css" />
<script src="/assets/courseware/v1/c9cee8830885f59e75b8782f44026226/asset-v1:MITx+6.005.2x+1T2017+type@asset+block/edx-script-v1.js"></script>
</div>
</div>
<div class="vert vert-1" data-id="block-v1:MITx+6.005.2x+1T2017+type@problem+block@02-terrible">
<div class="xblock xblock-public_view xblock-public_view-problem xmodule_display xmodule_ProblemBlock" data-has-score="True" data-runtime-class="LmsRuntime" data-graded="True" data-request-token="3f7f1aefe9a311efbd7412d4917dea95" data-runtime-version="1" data-block-type="problem" data-course-id="course-v1:MITx+6.005.2x+1T2017" data-init="XBlockToXModuleShim" data-usage-id="block-v1:MITx+6.005.2x+1T2017+type@problem+block@02-terrible">
<script type="json/xblock-args" class="xblock-json-init-args">
{"xmodule-type": "Problem"}
</script>
<div id="problem_02-terrible" class="problems-wrapper" role="group"
aria-labelledby="02-terrible-problem-title"
data-problem-id="block-v1:MITx+6.005.2x+1T2017+type@problem+block@02-terrible" data-url="/courses/course-v1:MITx+6.005.2x+1T2017/xblock/block-v1:MITx+6.005.2x+1T2017+type@problem+block@02-terrible/handler/xmodule_handler"
data-problem-score="0"
data-problem-total-possible="2"
data-attempts-used="0"
data-content="
<h3 class="hd hd-3 problem-header" id="02-terrible-problem-title" aria-describedby="block-v1:MITx+6.005.2x+1T2017+type@problem+block@02-terrible-problem-progress" tabindex="-1">
Terrible
</h3>
<div class="problem-progress" id="block-v1:MITx+6.005.2x+1T2017+type@problem+block@02-terrible-problem-progress"></div>
<div class="problem">
<div>
<p>We wrote our <code>ImList</code> implementations without documenting the abstraction function and representation invariant, which makes us terrible people.</p>
<pre>
public class Empty&lt;E&gt; implements ImList&lt;E&gt; {
public Empty() {
}
public ImList&lt;E&gt; cons(E e) { return new Cons&lt;E&gt;(e, this); }
public E first() { throw new UnsupportedOperationException(); }
public ImList&lt;E&gt; rest() { throw new UnsupportedOperationException(); }
}
</pre>
<p>Select an abstraction function for <code>Empty</code>:</p>
<div class="wrapper-problem-response" tabindex="-1" aria-label="Question 1" role="group"><div class="choicegroup capa_inputtype" id="inputtype_02-terrible_2_1">
<fieldset aria-describedby="status_02-terrible_2_1">
<div class="field">
<input type="radio" name="input_02-terrible_2_1" id="input_02-terrible_2_1_choice_0" class="field-input input-radio" value="choice_0"/><label id="02-terrible_2_1-choice_0-label" for="input_02-terrible_2_1_choice_0" class="response-label field-label label-inline" aria-describedby="status_02-terrible_2_1"> represents Empty
</label>
</div>
<div class="field">
<input type="radio" name="input_02-terrible_2_1" id="input_02-terrible_2_1_choice_1" class="field-input input-radio" value="choice_1"/><label id="02-terrible_2_1-choice_1-label" for="input_02-terrible_2_1_choice_1" class="response-label field-label label-inline" aria-describedby="status_02-terrible_2_1"> represents an empty list
</label>
</div>
<div class="field">
<input type="radio" name="input_02-terrible_2_1" id="input_02-terrible_2_1_choice_2" class="field-input input-radio" value="choice_2"/><label id="02-terrible_2_1-choice_2-label" for="input_02-terrible_2_1_choice_2" class="response-label field-label label-inline" aria-describedby="status_02-terrible_2_1"> represents null
</label>
</div>
<span id="answer_02-terrible_2_1"/>
</fieldset>
<div class="indicator-container">
<span class="status unanswered" id="status_02-terrible_2_1" data-tooltip="Not yet answered.">
<span class="sr">unanswered</span><span class="status-icon" aria-hidden="true"/>
</span>
</div>
</div></div>
<p>And select lines to include in the rep invariant (let's include even the 6.005-implicit things):</p>
<div class="wrapper-problem-response" tabindex="-1" aria-label="Question 2" role="group"><div class="choicegroup capa_inputtype" id="inputtype_02-terrible_3_1">
<fieldset aria-describedby="status_02-terrible_3_1">
<div class="field">
<input type="checkbox" name="input_02-terrible_3_1[]" id="input_02-terrible_3_1_choice_0" class="field-input input-checkbox" value="choice_0"/><label id="02-terrible_3_1-choice_0-label" for="input_02-terrible_3_1_choice_0" class="response-label field-label label-inline" aria-describedby="status_02-terrible_3_1"> nothing
</label>
</div>
<div class="field">
<input type="checkbox" name="input_02-terrible_3_1[]" id="input_02-terrible_3_1_choice_1" class="field-input input-checkbox" value="choice_1"/><label id="02-terrible_3_1-choice_1-label" for="input_02-terrible_3_1_choice_1" class="response-label field-label label-inline" aria-describedby="status_02-terrible_3_1"> e != null
</label>
</div>
<div class="field">
<input type="checkbox" name="input_02-terrible_3_1[]" id="input_02-terrible_3_1_choice_2" class="field-input input-checkbox" value="choice_2"/><label id="02-terrible_3_1-choice_2-label" for="input_02-terrible_3_1_choice_2" class="response-label field-label label-inline" aria-describedby="status_02-terrible_3_1"> e may be null
</label>
</div>
<div class="field">
<input type="checkbox" name="input_02-terrible_3_1[]" id="input_02-terrible_3_1_choice_3" class="field-input input-checkbox" value="choice_3"/><label id="02-terrible_3_1-choice_3-label" for="input_02-terrible_3_1_choice_3" class="response-label field-label label-inline" aria-describedby="status_02-terrible_3_1"> e is not empty
</label>
</div>
<div class="field">
<input type="checkbox" name="input_02-terrible_3_1[]" id="input_02-terrible_3_1_choice_4" class="field-input input-checkbox" value="choice_4"/><label id="02-terrible_3_1-choice_4-label" for="input_02-terrible_3_1_choice_4" class="response-label field-label label-inline" aria-describedby="status_02-terrible_3_1"> rest != null
</label>
</div>
<div class="field">
<input type="checkbox" name="input_02-terrible_3_1[]" id="input_02-terrible_3_1_choice_5" class="field-input input-checkbox" value="choice_5"/><label id="02-terrible_3_1-choice_5-label" for="input_02-terrible_3_1_choice_5" class="response-label field-label label-inline" aria-describedby="status_02-terrible_3_1"> rest may be null
</label>
</div>
<div class="field">
<input type="checkbox" name="input_02-terrible_3_1[]" id="input_02-terrible_3_1_choice_6" class="field-input input-checkbox" value="choice_6"/><label id="02-terrible_3_1-choice_6-label" for="input_02-terrible_3_1_choice_6" class="response-label field-label label-inline" aria-describedby="status_02-terrible_3_1"> rest is not empty
</label>
</div>
<div class="field">
<input type="checkbox" name="input_02-terrible_3_1[]" id="input_02-terrible_3_1_choice_7" class="field-input input-checkbox" value="choice_7"/><label id="02-terrible_3_1-choice_7-label" for="input_02-terrible_3_1_choice_7" class="response-label field-label label-inline" aria-describedby="status_02-terrible_3_1"> this is empty
</label>
</div>
<div class="field">
<input type="checkbox" name="input_02-terrible_3_1[]" id="input_02-terrible_3_1_choice_8" class="field-input input-checkbox" value="choice_8"/><label id="02-terrible_3_1-choice_8-label" for="input_02-terrible_3_1_choice_8" class="response-label field-label label-inline" aria-describedby="status_02-terrible_3_1"> this is not empty
</label>
</div>
<span id="answer_02-terrible_3_1"/>
</fieldset>
<div class="indicator-container">
<span class="status unanswered" id="status_02-terrible_3_1" data-tooltip="Not yet answered.">
<span class="sr">unanswered</span><span class="status-icon" aria-hidden="true"/>
</span>
</div>
</div></div>
<div class="solution-span">
<span id="solution_02-terrible_solution_1"/>
</div></div>
<div class="action">
<input type="hidden" name="problem_id" value="Terrible" />
<div class="submit-attempt-container">
<button type="button" class="submit btn-brand" data-submitting="Submitting" data-value="Submit" data-should-enable-submit-button="True" aria-describedby="submission_feedback_02-terrible" >
<span class="submit-label">Submit</span>
</button>
<div class="submission-feedback" id="submission_feedback_02-terrible">
<span class="sr">Some problems have options such as save, reset, hints, or show answer. These options follow the Submit button.</span>
</div>
</div>
<div class="problem-action-buttons-wrapper">
</div>
</div>
<div class="notification warning notification-gentle-alert
is-hidden"
tabindex="-1">
<span class="icon fa fa-exclamation-circle" aria-hidden="true"></span>
<span class="notification-message" aria-describedby="02-terrible-problem-title">
</span>
<div class="notification-btn-wrapper">
<button type="button" class="btn btn-default btn-small notification-btn review-btn sr">Review</button>
</div>
</div>
<div class="notification warning notification-save
is-hidden"
tabindex="-1">
<span class="icon fa fa-save" aria-hidden="true"></span>
<span class="notification-message" aria-describedby="02-terrible-problem-title">None
</span>
<div class="notification-btn-wrapper">
<button type="button" class="btn btn-default btn-small notification-btn review-btn sr">Review</button>
</div>
</div>
<div class="notification general notification-show-answer
is-hidden"
tabindex="-1">
<span class="icon fa fa-info-circle" aria-hidden="true"></span>
<span class="notification-message" aria-describedby="02-terrible-problem-title">Answers are displayed within the problem
</span>
<div class="notification-btn-wrapper">
<button type="button" class="btn btn-default btn-small notification-btn review-btn sr">Review</button>
</div>
</div>
</div>
"
data-graded="True">
<p class="loading-spinner">
<i class="fa fa-spinner fa-pulse fa-2x fa-fw"></i>
<span class="sr">Loading…</span>
</p>
</div>
</div>
</div>
<div class="vert vert-2" data-id="block-v1:MITx+6.005.2x+1T2017+type@problem+block@02-terrible-ii">
<div class="xblock xblock-public_view xblock-public_view-problem xmodule_display xmodule_ProblemBlock" data-has-score="True" data-runtime-class="LmsRuntime" data-graded="True" data-request-token="3f7f1aefe9a311efbd7412d4917dea95" data-runtime-version="1" data-block-type="problem" data-course-id="course-v1:MITx+6.005.2x+1T2017" data-init="XBlockToXModuleShim" data-usage-id="block-v1:MITx+6.005.2x+1T2017+type@problem+block@02-terrible-ii">
<script type="json/xblock-args" class="xblock-json-init-args">
{"xmodule-type": "Problem"}
</script>
<div id="problem_02-terrible-ii" class="problems-wrapper" role="group"
aria-labelledby="02-terrible-ii-problem-title"
data-problem-id="block-v1:MITx+6.005.2x+1T2017+type@problem+block@02-terrible-ii" data-url="/courses/course-v1:MITx+6.005.2x+1T2017/xblock/block-v1:MITx+6.005.2x+1T2017+type@problem+block@02-terrible-ii/handler/xmodule_handler"
data-problem-score="0"
data-problem-total-possible="2"
data-attempts-used="0"
data-content="
<h3 class="hd hd-3 problem-header" id="02-terrible-ii-problem-title" aria-describedby="block-v1:MITx+6.005.2x+1T2017+type@problem+block@02-terrible-ii-problem-progress" tabindex="-1">
Terrible II
</h3>
<div class="problem-progress" id="block-v1:MITx+6.005.2x+1T2017+type@problem+block@02-terrible-ii-problem-progress"></div>
<div class="problem">
<div>
<pre>
public class Cons&lt;E&gt; implements ImList&lt;E&gt; {
private E e;
private ImList&lt;E&gt; rest;
public Cons(E e, ImList&lt;E&gt; rest) {
this.e = e;
this.rest = rest;
}
public ImList&lt;E&gt; cons(E e) { return new Cons&lt;E&gt; (e, this); }
public E first() { return e; }
public ImList&lt;E&gt; rest() { return rest; }
}
</pre>
<p>Select an abstraction function for <code>Cons</code>:</p>
<div class="wrapper-problem-response" tabindex="-1" aria-label="Question 1" role="group"><div class="choicegroup capa_inputtype" id="inputtype_02-terrible-ii_2_1">
<fieldset aria-describedby="status_02-terrible-ii_2_1">
<div class="field">
<input type="radio" name="input_02-terrible-ii_2_1" id="input_02-terrible-ii_2_1_choice_0" class="field-input input-radio" value="choice_0"/><label id="02-terrible-ii_2_1-choice_0-label" for="input_02-terrible-ii_2_1_choice_0" class="response-label field-label label-inline" aria-describedby="status_02-terrible-ii_2_1"> represents Cons
</label>
</div>
<div class="field">
<input type="radio" name="input_02-terrible-ii_2_1" id="input_02-terrible-ii_2_1_choice_1" class="field-input input-radio" value="choice_1"/><label id="02-terrible-ii_2_1-choice_1-label" for="input_02-terrible-ii_2_1_choice_1" class="response-label field-label label-inline" aria-describedby="status_02-terrible-ii_2_1"> represents a non-empty list
</label>
</div>
<div class="field">
<input type="radio" name="input_02-terrible-ii_2_1" id="input_02-terrible-ii_2_1_choice_2" class="field-input input-radio" value="choice_2"/><label id="02-terrible-ii_2_1-choice_2-label" for="input_02-terrible-ii_2_1_choice_2" class="response-label field-label label-inline" aria-describedby="status_02-terrible-ii_2_1"> represents a non-empty list of e and rest
</label>
</div>
<div class="field">
<input type="radio" name="input_02-terrible-ii_2_1" id="input_02-terrible-ii_2_1_choice_3" class="field-input input-radio" value="choice_3"/><label id="02-terrible-ii_2_1-choice_3-label" for="input_02-terrible-ii_2_1_choice_3" class="response-label field-label label-inline" aria-describedby="status_02-terrible-ii_2_1"> represents a two-element list where the first element is e and the second element is rest
</label>
</div>
<div class="field">
<input type="radio" name="input_02-terrible-ii_2_1" id="input_02-terrible-ii_2_1_choice_4" class="field-input input-radio" value="choice_4"/><label id="02-terrible-ii_2_1-choice_4-label" for="input_02-terrible-ii_2_1_choice_4" class="response-label field-label label-inline" aria-describedby="status_02-terrible-ii_2_1"> represents a list where the first element is e and the remaining elements are rest
</label>
</div>
<span id="answer_02-terrible-ii_2_1"/>
</fieldset>
<div class="indicator-container">
<span class="status unanswered" id="status_02-terrible-ii_2_1" data-tooltip="Not yet answered.">
<span class="sr">unanswered</span><span class="status-icon" aria-hidden="true"/>
</span>
</div>
</div></div>
<p>And select lines to include in the rep invariant (let's include even the 6.005-implicit things):</p>
<div class="wrapper-problem-response" tabindex="-1" aria-label="Question 2" role="group"><div class="choicegroup capa_inputtype" id="inputtype_02-terrible-ii_3_1">
<fieldset aria-describedby="status_02-terrible-ii_3_1">
<div class="field">
<input type="checkbox" name="input_02-terrible-ii_3_1[]" id="input_02-terrible-ii_3_1_choice_0" class="field-input input-checkbox" value="choice_0"/><label id="02-terrible-ii_3_1-choice_0-label" for="input_02-terrible-ii_3_1_choice_0" class="response-label field-label label-inline" aria-describedby="status_02-terrible-ii_3_1"> nothing
</label>
</div>
<div class="field">
<input type="checkbox" name="input_02-terrible-ii_3_1[]" id="input_02-terrible-ii_3_1_choice_1" class="field-input input-checkbox" value="choice_1"/><label id="02-terrible-ii_3_1-choice_1-label" for="input_02-terrible-ii_3_1_choice_1" class="response-label field-label label-inline" aria-describedby="status_02-terrible-ii_3_1"> e != null
</label>
</div>
<div class="field">
<input type="checkbox" name="input_02-terrible-ii_3_1[]" id="input_02-terrible-ii_3_1_choice_2" class="field-input input-checkbox" value="choice_2"/><label id="02-terrible-ii_3_1-choice_2-label" for="input_02-terrible-ii_3_1_choice_2" class="response-label field-label label-inline" aria-describedby="status_02-terrible-ii_3_1"> e may be null
</label>
</div>
<div class="field">
<input type="checkbox" name="input_02-terrible-ii_3_1[]" id="input_02-terrible-ii_3_1_choice_3" class="field-input input-checkbox" value="choice_3"/><label id="02-terrible-ii_3_1-choice_3-label" for="input_02-terrible-ii_3_1_choice_3" class="response-label field-label label-inline" aria-describedby="status_02-terrible-ii_3_1"> e is not empty
</label>
</div>
<div class="field">
<input type="checkbox" name="input_02-terrible-ii_3_1[]" id="input_02-terrible-ii_3_1_choice_4" class="field-input input-checkbox" value="choice_4"/><label id="02-terrible-ii_3_1-choice_4-label" for="input_02-terrible-ii_3_1_choice_4" class="response-label field-label label-inline" aria-describedby="status_02-terrible-ii_3_1"> rest != null
</label>
</div>
<div class="field">
<input type="checkbox" name="input_02-terrible-ii_3_1[]" id="input_02-terrible-ii_3_1_choice_5" class="field-input input-checkbox" value="choice_5"/><label id="02-terrible-ii_3_1-choice_5-label" for="input_02-terrible-ii_3_1_choice_5" class="response-label field-label label-inline" aria-describedby="status_02-terrible-ii_3_1"> rest may be null
</label>
</div>
<div class="field">
<input type="checkbox" name="input_02-terrible-ii_3_1[]" id="input_02-terrible-ii_3_1_choice_6" class="field-input input-checkbox" value="choice_6"/><label id="02-terrible-ii_3_1-choice_6-label" for="input_02-terrible-ii_3_1_choice_6" class="response-label field-label label-inline" aria-describedby="status_02-terrible-ii_3_1"> rest is not empty
</label>
</div>
<div class="field">
<input type="checkbox" name="input_02-terrible-ii_3_1[]" id="input_02-terrible-ii_3_1_choice_7" class="field-input input-checkbox" value="choice_7"/><label id="02-terrible-ii_3_1-choice_7-label" for="input_02-terrible-ii_3_1_choice_7" class="response-label field-label label-inline" aria-describedby="status_02-terrible-ii_3_1"> this is empty
</label>
</div>
<div class="field">
<input type="checkbox" name="input_02-terrible-ii_3_1[]" id="input_02-terrible-ii_3_1_choice_8" class="field-input input-checkbox" value="choice_8"/><label id="02-terrible-ii_3_1-choice_8-label" for="input_02-terrible-ii_3_1_choice_8" class="response-label field-label label-inline" aria-describedby="status_02-terrible-ii_3_1"> this is not empty
</label>
</div>
<span id="answer_02-terrible-ii_3_1"/>
</fieldset>
<div class="indicator-container">
<span class="status unanswered" id="status_02-terrible-ii_3_1" data-tooltip="Not yet answered.">
<span class="sr">unanswered</span><span class="status-icon" aria-hidden="true"/>
</span>
</div>
</div></div>
<div class="solution-span">
<span id="solution_02-terrible-ii_solution_1"/>
</div></div>
<div class="action">
<input type="hidden" name="problem_id" value="Terrible II" />
<div class="submit-attempt-container">
<button type="button" class="submit btn-brand" data-submitting="Submitting" data-value="Submit" data-should-enable-submit-button="True" aria-describedby="submission_feedback_02-terrible-ii" >
<span class="submit-label">Submit</span>
</button>
<div class="submission-feedback" id="submission_feedback_02-terrible-ii">
<span class="sr">Some problems have options such as save, reset, hints, or show answer. These options follow the Submit button.</span>
</div>
</div>
<div class="problem-action-buttons-wrapper">
</div>
</div>
<div class="notification warning notification-gentle-alert
is-hidden"
tabindex="-1">
<span class="icon fa fa-exclamation-circle" aria-hidden="true"></span>
<span class="notification-message" aria-describedby="02-terrible-ii-problem-title">
</span>
<div class="notification-btn-wrapper">
<button type="button" class="btn btn-default btn-small notification-btn review-btn sr">Review</button>
</div>
</div>
<div class="notification warning notification-save
is-hidden"
tabindex="-1">
<span class="icon fa fa-save" aria-hidden="true"></span>
<span class="notification-message" aria-describedby="02-terrible-ii-problem-title">None
</span>
<div class="notification-btn-wrapper">
<button type="button" class="btn btn-default btn-small notification-btn review-btn sr">Review</button>
</div>
</div>
<div class="notification general notification-show-answer
is-hidden"
tabindex="-1">
<span class="icon fa fa-info-circle" aria-hidden="true"></span>
<span class="notification-message" aria-describedby="02-terrible-ii-problem-title">Answers are displayed within the problem
</span>
<div class="notification-btn-wrapper">
<button type="button" class="btn btn-default btn-small notification-btn review-btn sr">Review</button>
</div>
</div>
</div>
"
data-graded="True">
<p class="loading-spinner">
<i class="fa fa-spinner fa-pulse fa-2x fa-fw"></i>
<span class="sr">Loading…</span>
</p>
</div>
</div>
</div>
<div class="vert vert-3" data-id="block-v1:MITx+6.005.2x+1T2017+type@problem+block@02-the-black-hole-at-the-center-of-my-program">
<div class="xblock xblock-public_view xblock-public_view-problem xmodule_display xmodule_ProblemBlock" data-has-score="True" data-runtime-class="LmsRuntime" data-graded="True" data-request-token="3f7f1aefe9a311efbd7412d4917dea95" data-runtime-version="1" data-block-type="problem" data-course-id="course-v1:MITx+6.005.2x+1T2017" data-init="XBlockToXModuleShim" data-usage-id="block-v1:MITx+6.005.2x+1T2017+type@problem+block@02-the-black-hole-at-the-center-of-my-program">
<script type="json/xblock-args" class="xblock-json-init-args">
{"xmodule-type": "Problem"}
</script>
<div id="problem_02-the-black-hole-at-the-center-of-my-program" class="problems-wrapper" role="group"
aria-labelledby="02-the-black-hole-at-the-center-of-my-program-problem-title"
data-problem-id="block-v1:MITx+6.005.2x+1T2017+type@problem+block@02-the-black-hole-at-the-center-of-my-program" data-url="/courses/course-v1:MITx+6.005.2x+1T2017/xblock/block-v1:MITx+6.005.2x+1T2017+type@problem+block@02-the-black-hole-at-the-center-of-my-program/handler/xmodule_handler"
data-problem-score="0"
data-problem-total-possible="1"
data-attempts-used="0"
data-content="
<h3 class="hd hd-3 problem-header" id="02-the-black-hole-at-the-center-of-my-program-problem-title" aria-describedby="block-v1:MITx+6.005.2x+1T2017+type@problem+block@02-the-black-hole-at-the-center-of-my-program-problem-progress" tabindex="-1">
The black hole at the center of my program
</h3>
<div class="problem-progress" id="block-v1:MITx+6.005.2x+1T2017+type@problem+block@02-the-black-hole-at-the-center-of-my-program-problem-progress"></div>
<div class="problem">
<div>
<p>Alice and Ben are reading about <code>ImList</code>, and Ben suggests that since sharing immutable datatypes is safe, <em>all</em> empty lists should point to the same instance of <code>Empty</code>.</p>
<p>Which of the following is true:</p>
<div class="wrapper-problem-response" tabindex="-1" aria-label="Question 1" role="group"><div class="choicegroup capa_inputtype" id="inputtype_02-the-black-hole-at-the-center-of-my-program_2_1">
<fieldset aria-describedby="status_02-the-black-hole-at-the-center-of-my-program_2_1">
<div class="field">
<input class="field-input input-checkbox" type="checkbox" name="input_02-the-black-hole-at-the-center-of-my-program_2_1[]" id="input_02-the-black-hole-at-the-center-of-my-program_2_1_choice_0" value="choice_0"/><label class="response-label field-label label-inline" for="input_02-the-black-hole-at-the-center-of-my-program_2_1_choice_0" id="02-the-black-hole-at-the-center-of-my-program_2_1-choice_0-label" aria-describedby="status_02-the-black-hole-at-the-center-of-my-program_2_1"> sharing the same instance of Empty throughout the entire program would be safe
</label>
</div>
<div class="field">
<input class="field-input input-checkbox" type="checkbox" name="input_02-the-black-hole-at-the-center-of-my-program_2_1[]" id="input_02-the-black-hole-at-the-center-of-my-program_2_1_choice_1" value="choice_1"/><label class="response-label field-label label-inline" for="input_02-the-black-hole-at-the-center-of-my-program_2_1_choice_1" id="02-the-black-hole-at-the-center-of-my-program_2_1-choice_1-label" aria-describedby="status_02-the-black-hole-at-the-center-of-my-program_2_1"> sharing the same instance of Empty throughout the entire program would not be safe
</label>
</div>
<div class="field">
<input class="field-input input-checkbox" type="checkbox" name="input_02-the-black-hole-at-the-center-of-my-program_2_1[]" id="input_02-the-black-hole-at-the-center-of-my-program_2_1_choice_2" value="choice_2"/><label class="response-label field-label label-inline" for="input_02-the-black-hole-at-the-center-of-my-program_2_1_choice_2" id="02-the-black-hole-at-the-center-of-my-program_2_1-choice_2-label" aria-describedby="status_02-the-black-hole-at-the-center-of-my-program_2_1"> we cannot implement this easily because empty() must return a new instance of Empty every time
</label>
</div>
<div class="field">
<input class="field-input input-checkbox" type="checkbox" name="input_02-the-black-hole-at-the-center-of-my-program_2_1[]" id="input_02-the-black-hole-at-the-center-of-my-program_2_1_choice_3" value="choice_3"/><label class="response-label field-label label-inline" for="input_02-the-black-hole-at-the-center-of-my-program_2_1_choice_3" id="02-the-black-hole-at-the-center-of-my-program_2_1-choice_3-label" aria-describedby="status_02-the-black-hole-at-the-center-of-my-program_2_1"> we cannot implement this easily because empty() must return instances of Empty with different element types E
</label>
</div>
<div class="field">
<input class="field-input input-checkbox" type="checkbox" name="input_02-the-black-hole-at-the-center-of-my-program_2_1[]" id="input_02-the-black-hole-at-the-center-of-my-program_2_1_choice_4" value="choice_4"/><label class="response-label field-label label-inline" for="input_02-the-black-hole-at-the-center-of-my-program_2_1_choice_4" id="02-the-black-hole-at-the-center-of-my-program_2_1-choice_4-label" aria-describedby="status_02-the-black-hole-at-the-center-of-my-program_2_1"> we cannot implement this easily because when we call a constructor (e.g. new Empty&lt;&gt;()) we must create a new object
</label>
</div>
<span id="answer_02-the-black-hole-at-the-center-of-my-program_2_1"/>
</fieldset>
<div class="indicator-container">
<span class="status unanswered" data-tooltip="Not yet answered." id="status_02-the-black-hole-at-the-center-of-my-program_2_1">
<span class="sr">unanswered</span><span class="status-icon" aria-hidden="true"/>
</span>
</div>
</div></div>
<div class="solution-span">
<span id="solution_02-the-black-hole-at-the-center-of-my-program_solution_1"/>
</div></div>
<div class="action">
<input type="hidden" name="problem_id" value="The black hole at the center of my program" />
<div class="submit-attempt-container">
<button type="button" class="submit btn-brand" data-submitting="Submitting" data-value="Submit" data-should-enable-submit-button="True" aria-describedby="submission_feedback_02-the-black-hole-at-the-center-of-my-program" >
<span class="submit-label">Submit</span>
</button>
<div class="submission-feedback" id="submission_feedback_02-the-black-hole-at-the-center-of-my-program">
<span class="sr">Some problems have options such as save, reset, hints, or show answer. These options follow the Submit button.</span>
</div>
</div>
<div class="problem-action-buttons-wrapper">
</div>
</div>
<div class="notification warning notification-gentle-alert
is-hidden"
tabindex="-1">
<span class="icon fa fa-exclamation-circle" aria-hidden="true"></span>
<span class="notification-message" aria-describedby="02-the-black-hole-at-the-center-of-my-program-problem-title">
</span>
<div class="notification-btn-wrapper">
<button type="button" class="btn btn-default btn-small notification-btn review-btn sr">Review</button>
</div>
</div>
<div class="notification warning notification-save
is-hidden"
tabindex="-1">
<span class="icon fa fa-save" aria-hidden="true"></span>
<span class="notification-message" aria-describedby="02-the-black-hole-at-the-center-of-my-program-problem-title">None
</span>
<div class="notification-btn-wrapper">
<button type="button" class="btn btn-default btn-small notification-btn review-btn sr">Review</button>
</div>
</div>
<div class="notification general notification-show-answer
is-hidden"
tabindex="-1">
<span class="icon fa fa-info-circle" aria-hidden="true"></span>
<span class="notification-message" aria-describedby="02-the-black-hole-at-the-center-of-my-program-problem-title">Answers are displayed within the problem
</span>
<div class="notification-btn-wrapper">
<button type="button" class="btn btn-default btn-small notification-btn review-btn sr">Review</button>
</div>
</div>
</div>
"
data-graded="True">
<p class="loading-spinner">
<i class="fa fa-spinner fa-pulse fa-2x fa-fw"></i>
<span class="sr">Loading…</span>
</p>
</div>
</div>
</div>
<div class="vert vert-4" data-id="block-v1:MITx+6.005.2x+1T2017+type@problem+block@02-short-layover">
<div class="xblock xblock-public_view xblock-public_view-problem xmodule_display xmodule_ProblemBlock" data-has-score="True" data-runtime-class="LmsRuntime" data-graded="True" data-request-token="3f7f1aefe9a311efbd7412d4917dea95" data-runtime-version="1" data-block-type="problem" data-course-id="course-v1:MITx+6.005.2x+1T2017" data-init="XBlockToXModuleShim" data-usage-id="block-v1:MITx+6.005.2x+1T2017+type@problem+block@02-short-layover">
<script type="json/xblock-args" class="xblock-json-init-args">
{"xmodule-type": "Problem"}
</script>
<div id="problem_02-short-layover" class="problems-wrapper" role="group"
aria-labelledby="02-short-layover-problem-title"
data-problem-id="block-v1:MITx+6.005.2x+1T2017+type@problem+block@02-short-layover" data-url="/courses/course-v1:MITx+6.005.2x+1T2017/xblock/block-v1:MITx+6.005.2x+1T2017+type@problem+block@02-short-layover/handler/xmodule_handler"
data-problem-score="0"
data-problem-total-possible="3"
data-attempts-used="0"
data-content="
<h3 class="hd hd-3 problem-header" id="02-short-layover-problem-title" aria-describedby="block-v1:MITx+6.005.2x+1T2017+type@problem+block@02-short-layover-problem-progress" tabindex="-1">
Short layover
</h3>
<div class="problem-progress" id="block-v1:MITx+6.005.2x+1T2017+type@problem+block@02-short-layover-problem-progress"></div>
<div class="problem">
<div>
<p>Given this code:</p>
<pre>
ImList&lt;String&gt; airports =
ImList.empty().cons("SFO").cons("IAD").cons("BOS");
</pre>
<p>Which of the following is true?</p>
<div class="wrapper-problem-response" tabindex="-1" aria-label="Question 1" role="group"><div class="choicegroup capa_inputtype" id="inputtype_02-short-layover_2_1">
<fieldset aria-describedby="status_02-short-layover_2_1">
<div class="field">
<input type="radio" name="input_02-short-layover_2_1" id="input_02-short-layover_2_1_choice_0" class="field-input input-radio" value="choice_0"/><label id="02-short-layover_2_1-choice_0-label" for="input_02-short-layover_2_1_choice_0" class="response-label field-label label-inline" aria-describedby="status_02-short-layover_2_1"> airports.first() is "SFO"
</label>
</div>
<div class="field">
<input type="radio" name="input_02-short-layover_2_1" id="input_02-short-layover_2_1_choice_1" class="field-input input-radio" value="choice_1"/><label id="02-short-layover_2_1-choice_1-label" for="input_02-short-layover_2_1_choice_1" class="response-label field-label label-inline" aria-describedby="status_02-short-layover_2_1"> airports.first() is "BOS"
</label>
</div>
<div class="field">
<input type="radio" name="input_02-short-layover_2_1" id="input_02-short-layover_2_1_choice_2" class="field-input input-radio" value="choice_2"/><label id="02-short-layover_2_1-choice_2-label" for="input_02-short-layover_2_1_choice_2" class="response-label field-label label-inline" aria-describedby="status_02-short-layover_2_1"> airports.first() is the list [ "SFO" ]
</label>
</div>
<div class="field">
<input type="radio" name="input_02-short-layover_2_1" id="input_02-short-layover_2_1_choice_3" class="field-input input-radio" value="choice_3"/><label id="02-short-layover_2_1-choice_3-label" for="input_02-short-layover_2_1_choice_3" class="response-label field-label label-inline" aria-describedby="status_02-short-layover_2_1"> airports.first() is the list [ "BOS" ]
</label>
</div>
<span id="answer_02-short-layover_2_1"/>
</fieldset>
<div class="indicator-container">
<span class="status unanswered" id="status_02-short-layover_2_1" data-tooltip="Not yet answered.">
<span class="sr">unanswered</span><span class="status-icon" aria-hidden="true"/>
</span>
</div>
</div></div>
<p>Which of the following is true?</p>
<div class="wrapper-problem-response" tabindex="-1" aria-label="Question 2" role="group"><div class="choicegroup capa_inputtype" id="inputtype_02-short-layover_3_1">
<fieldset aria-describedby="status_02-short-layover_3_1">
<div class="field">
<input type="radio" name="input_02-short-layover_3_1" id="input_02-short-layover_3_1_choice_0" class="field-input input-radio" value="choice_0"/><label id="02-short-layover_3_1-choice_0-label" for="input_02-short-layover_3_1_choice_0" class="response-label field-label label-inline" aria-describedby="status_02-short-layover_3_1"> airports.rest().rest() is "SFO"
</label>
</div>
<div class="field">
<input type="radio" name="input_02-short-layover_3_1" id="input_02-short-layover_3_1_choice_1" class="field-input input-radio" value="choice_1"/><label id="02-short-layover_3_1-choice_1-label" for="input_02-short-layover_3_1_choice_1" class="response-label field-label label-inline" aria-describedby="status_02-short-layover_3_1"> airports.rest().rest() is "BOS"
</label>
</div>
<div class="field">
<input type="radio" name="input_02-short-layover_3_1" id="input_02-short-layover_3_1_choice_2" class="field-input input-radio" value="choice_2"/><label id="02-short-layover_3_1-choice_2-label" for="input_02-short-layover_3_1_choice_2" class="response-label field-label label-inline" aria-describedby="status_02-short-layover_3_1"> airports.rest().rest() is the list [ "SFO" ]
</label>
</div>
<div class="field">
<input type="radio" name="input_02-short-layover_3_1" id="input_02-short-layover_3_1_choice_3" class="field-input input-radio" value="choice_3"/><label id="02-short-layover_3_1-choice_3-label" for="input_02-short-layover_3_1_choice_3" class="response-label field-label label-inline" aria-describedby="status_02-short-layover_3_1"> airports.rest().rest() is the list [ "BOS" ]
</label>
</div>
<span id="answer_02-short-layover_3_1"/>
</fieldset>
<div class="indicator-container">
<span class="status unanswered" id="status_02-short-layover_3_1" data-tooltip="Not yet answered.">
<span class="sr">unanswered</span><span class="status-icon" aria-hidden="true"/>
</span>
</div>
</div></div>
<p>True or false: <code>Empty</code> and <code>Cons</code> both implementing <code>ImList</code> are analogous to <code>ArrayList</code> and <code>LinkedList</code> both implementing <code>List</code> in the Java library.</p>
<div class="wrapper-problem-response" tabindex="-1" aria-label="Question 3" role="group"><div class="choicegroup capa_inputtype" id="inputtype_02-short-layover_4_1">
<fieldset aria-describedby="status_02-short-layover_4_1">
<div class="field">
<input type="radio" name="input_02-short-layover_4_1" id="input_02-short-layover_4_1_choice_0" class="field-input input-radio" value="choice_0"/><label id="02-short-layover_4_1-choice_0-label" for="input_02-short-layover_4_1_choice_0" class="response-label field-label label-inline" aria-describedby="status_02-short-layover_4_1"> True
</label>
</div>
<div class="field">
<input type="radio" name="input_02-short-layover_4_1" id="input_02-short-layover_4_1_choice_1" class="field-input input-radio" value="choice_1"/><label id="02-short-layover_4_1-choice_1-label" for="input_02-short-layover_4_1_choice_1" class="response-label field-label label-inline" aria-describedby="status_02-short-layover_4_1"> False
</label>
</div>
<span id="answer_02-short-layover_4_1"/>
</fieldset>
<div class="indicator-container">
<span class="status unanswered" id="status_02-short-layover_4_1" data-tooltip="Not yet answered.">
<span class="sr">unanswered</span><span class="status-icon" aria-hidden="true"/>
</span>
</div>
</div></div>
<div class="solution-span">
<span id="solution_02-short-layover_solution_1"/>
</div></div>
<div class="action">
<input type="hidden" name="problem_id" value="Short layover" />
<div class="submit-attempt-container">
<button type="button" class="submit btn-brand" data-submitting="Submitting" data-value="Submit" data-should-enable-submit-button="True" aria-describedby="submission_feedback_02-short-layover" >
<span class="submit-label">Submit</span>
</button>
<div class="submission-feedback" id="submission_feedback_02-short-layover">
<span class="sr">Some problems have options such as save, reset, hints, or show answer. These options follow the Submit button.</span>
</div>
</div>
<div class="problem-action-buttons-wrapper">
</div>
</div>
<div class="notification warning notification-gentle-alert
is-hidden"
tabindex="-1">
<span class="icon fa fa-exclamation-circle" aria-hidden="true"></span>
<span class="notification-message" aria-describedby="02-short-layover-problem-title">
</span>
<div class="notification-btn-wrapper">
<button type="button" class="btn btn-default btn-small notification-btn review-btn sr">Review</button>
</div>
</div>
<div class="notification warning notification-save
is-hidden"
tabindex="-1">
<span class="icon fa fa-save" aria-hidden="true"></span>
<span class="notification-message" aria-describedby="02-short-layover-problem-title">None
</span>
<div class="notification-btn-wrapper">
<button type="button" class="btn btn-default btn-small notification-btn review-btn sr">Review</button>
</div>
</div>
<div class="notification general notification-show-answer
is-hidden"
tabindex="-1">
<span class="icon fa fa-info-circle" aria-hidden="true"></span>
<span class="notification-message" aria-describedby="02-short-layover-problem-title">Answers are displayed within the problem
</span>
<div class="notification-btn-wrapper">
<button type="button" class="btn btn-default btn-small notification-btn review-btn sr">Review</button>
</div>
</div>
</div>
"
data-graded="True">
<p class="loading-spinner">
<i class="fa fa-spinner fa-pulse fa-2x fa-fw"></i>
<span class="sr">Loading…</span>
</p>
</div>
</div>
</div>
</div>
</div>
<div class="xblock xblock-public_view xblock-public_view-vertical" data-has-score="False" data-runtime-class="LmsRuntime" data-graded="True" data-request-token="3f7f1aefe9a311efbd7412d4917dea95" data-runtime-version="1" data-block-type="vertical" data-course-id="course-v1:MITx+6.005.2x+1T2017" data-init="VerticalStudentView" data-usage-id="block-v1:MITx+6.005.2x+1T2017+type@vertical+block@vertical-recursive_datatype_definitions">
<h2 class="hd hd-2 unit-title">Recursive datatype definitions</h2>
<div class="vert-mod">
<div class="vert vert-0" data-id="block-v1:MITx+6.005.2x+1T2017+type@html+block@html_bac56b06d1ad">
<div class="xblock xblock-public_view xblock-public_view-html xmodule_display xmodule_HtmlBlock" data-has-score="False" data-runtime-class="LmsRuntime" data-graded="True" data-request-token="3f7f1aefe9a311efbd7412d4917dea95" data-runtime-version="1" data-block-type="html" data-course-id="course-v1:MITx+6.005.2x+1T2017" data-init="XBlockToXModuleShim" data-usage-id="block-v1:MITx+6.005.2x+1T2017+type@html+block@html_bac56b06d1ad">
<script type="json/xblock-args" class="xblock-json-init-args">
{"xmodule-type": "HTMLModule"}
</script>
<link href="/assets/courseware/v1/b2188f0a95a7a9062748278f7d5a584f/asset-v1:MITx+6.005.2x+1T2017+type@asset+block/syntax-highlighting.css" rel="stylesheet" type="text/css" />
<h2 id="recursive_datatype_definitions">Recursive datatype definitions</h2>
<div data-outline="recursive_datatype_definitions">
<p>The abstract data type <code>ImList</code>, and its two concrete classes <code>Empty</code> and <code>Cons</code>, form a <em>recursive</em> data type.
<code>Cons</code> is an implementation of <code>ImList</code>, but it also uses <code>ImList</code> inside its own rep (for the <code>rest</code> field), so it recursively requires an implementation of <code>ImList</code> in order to successfully implement its contract.</p>
<p>To make this fact clearly visible, we'll write a <strong>datatype definition</strong>:</p><pre><code class="hljs xml">ImList<span class="hljs-tag"><<span class="hljs-title">E</span>></span> = Empty + Cons(first:E, rest:ImList)
</code></pre>
<p>This is a recursive definition of <code>ImList</code> as a set of values. Read it like this: the set <code>ImList</code> consists of values formed in two ways: either by the <code>Empty</code> constructor, or by applying the <code>Cons</code> constructor to an element and an <code>ImList</code>. The recursive nature of the datatype becomes far more visible when written this way.</p>
<p>We can also write <code>ImList</code> values as terms or expressions using this definition, e.g.:</p><pre><code class="hljs cpp">Cons(<span class="hljs-number">0</span>, Cons(<span class="hljs-number">1</span>, Cons(<span class="hljs-number">2</span>, Empty)))
</code></pre>
<p>Formally, a datatype definition has:</p>
<ul>
<li>an <strong>abstract datatype</strong> on the left, defined by its <strong>representation</strong> (or <strong>concrete datatype</strong>) on the right</li>
<li>the representation consists of <strong>variants</strong> of the datatype separated by <strong>+</strong> </li>
<li>each variant is a constructor with zero or more named (and typed) arguments</li>
</ul>
<p>Another example is a binary tree:</p><pre><code class="hljs xml">Tree<span class="hljs-tag"><<span class="hljs-title">E</span>></span> = Empty + Node(e:E, left:Tree<span class="hljs-tag"><<span class="hljs-title">E</span>></span>, right:Tree<span class="hljs-tag"><<span class="hljs-title">E</span>></span>)
</code></pre>
<p>We'll see more examples below.</p>
</div>
</div>
</div>
</div>
</div>
<div class="xblock xblock-public_view xblock-public_view-vertical" data-has-score="False" data-runtime-class="LmsRuntime" data-graded="True" data-request-token="3f7f1aefe9a311efbd7412d4917dea95" data-runtime-version="1" data-block-type="vertical" data-course-id="course-v1:MITx+6.005.2x+1T2017" data-init="VerticalStudentView" data-usage-id="block-v1:MITx+6.005.2x+1T2017+type@vertical+block@vertical_Questions_828397fe5523">
<h2 class="hd hd-2 unit-title">Questions</h2>
<div class="vert-mod">
<div class="vert vert-0" data-id="block-v1:MITx+6.005.2x+1T2017+type@html+block@Recursive_datatype_definitions">
<div class="xblock xblock-public_view xblock-public_view-html xmodule_display xmodule_HtmlBlock" data-has-score="False" data-runtime-class="LmsRuntime" data-graded="True" data-request-token="3f7f1aefe9a311efbd7412d4917dea95" data-runtime-version="1" data-block-type="html" data-course-id="course-v1:MITx+6.005.2x+1T2017" data-init="XBlockToXModuleShim" data-usage-id="block-v1:MITx+6.005.2x+1T2017+type@html+block@Recursive_datatype_definitions">
<script type="json/xblock-args" class="xblock-json-init-args">
{"xmodule-type": "HTMLModule"}
</script>
<link href="/assets/courseware/v1/b2188f0a95a7a9062748278f7d5a584f/asset-v1:MITx+6.005.2x+1T2017+type@asset+block/syntax-highlighting.css" rel="stylesheet" type="text/css" />
<script src="/assets/courseware/v1/c9cee8830885f59e75b8782f44026226/asset-v1:MITx+6.005.2x+1T2017+type@asset+block/edx-script-v1.js"></script>
</div>
</div>
<div class="vert vert-1" data-id="block-v1:MITx+6.005.2x+1T2017+type@problem+block@02-its-rocks-all-the-way-down">
<div class="xblock xblock-public_view xblock-public_view-problem xmodule_display xmodule_ProblemBlock" data-has-score="True" data-runtime-class="LmsRuntime" data-graded="True" data-request-token="3f7f1aefe9a311efbd7412d4917dea95" data-runtime-version="1" data-block-type="problem" data-course-id="course-v1:MITx+6.005.2x+1T2017" data-init="XBlockToXModuleShim" data-usage-id="block-v1:MITx+6.005.2x+1T2017+type@problem+block@02-its-rocks-all-the-way-down">
<script type="json/xblock-args" class="xblock-json-init-args">
{"xmodule-type": "Problem"}
</script>
<div id="problem_02-its-rocks-all-the-way-down" class="problems-wrapper" role="group"
aria-labelledby="02-its-rocks-all-the-way-down-problem-title"
data-problem-id="block-v1:MITx+6.005.2x+1T2017+type@problem+block@02-its-rocks-all-the-way-down" data-url="/courses/course-v1:MITx+6.005.2x+1T2017/xblock/block-v1:MITx+6.005.2x+1T2017+type@problem+block@02-its-rocks-all-the-way-down/handler/xmodule_handler"
data-problem-score="0"
data-problem-total-possible="1"
data-attempts-used="0"
data-content="
<h3 class="hd hd-3 problem-header" id="02-its-rocks-all-the-way-down-problem-title" aria-describedby="block-v1:MITx+6.005.2x+1T2017+type@problem+block@02-its-rocks-all-the-way-down-problem-progress" tabindex="-1">
It&#39;s rocks all the way down
</h3>
<div class="problem-progress" id="block-v1:MITx+6.005.2x+1T2017+type@problem+block@02-its-rocks-all-the-way-down-problem-progress"></div>
<div class="problem">
<div>
<p>Consider the datatype definition:</p>
<pre>
Geology = Core(a:int, b:int, c:int, d:int)
+ Planet(core:Core, a:int, b:int, c:int, d:int)
+ System(geology:Geology, a:int, b:int)
</pre>
<p>Suppose you have a reference to a <code>Geology</code> object. How many integers might it have in its representation?</p>
<div class="wrapper-problem-response" tabindex="-1" aria-label="Question 1" role="group"><div class="choicegroup capa_inputtype" id="inputtype_02-its-rocks-all-the-way-down_2_1">
<fieldset aria-describedby="status_02-its-rocks-all-the-way-down_2_1">
<div class="field">
<input type="checkbox" name="input_02-its-rocks-all-the-way-down_2_1[]" id="input_02-its-rocks-all-the-way-down_2_1_choice_0" class="field-input input-checkbox" value="choice_0"/><label id="02-its-rocks-all-the-way-down_2_1-choice_0-label" for="input_02-its-rocks-all-the-way-down_2_1_choice_0" class="response-label field-label label-inline" aria-describedby="status_02-its-rocks-all-the-way-down_2_1"> A. 1
</label>
</div>
<div class="field">
<input type="checkbox" name="input_02-its-rocks-all-the-way-down_2_1[]" id="input_02-its-rocks-all-the-way-down_2_1_choice_1" class="field-input input-checkbox" value="choice_1"/><label id="02-its-rocks-all-the-way-down_2_1-choice_1-label" for="input_02-its-rocks-all-the-way-down_2_1_choice_1" class="response-label field-label label-inline" aria-describedby="status_02-its-rocks-all-the-way-down_2_1"> B. 2
</label>
</div>
<div class="field">
<input type="checkbox" name="input_02-its-rocks-all-the-way-down_2_1[]" id="input_02-its-rocks-all-the-way-down_2_1_choice_2" class="field-input input-checkbox" value="choice_2"/><label id="02-its-rocks-all-the-way-down_2_1-choice_2-label" for="input_02-its-rocks-all-the-way-down_2_1_choice_2" class="response-label field-label label-inline" aria-describedby="status_02-its-rocks-all-the-way-down_2_1"> C. 4
</label>
</div>
<div class="field">
<input type="checkbox" name="input_02-its-rocks-all-the-way-down_2_1[]" id="input_02-its-rocks-all-the-way-down_2_1_choice_3" class="field-input input-checkbox" value="choice_3"/><label id="02-its-rocks-all-the-way-down_2_1-choice_3-label" for="input_02-its-rocks-all-the-way-down_2_1_choice_3" class="response-label field-label label-inline" aria-describedby="status_02-its-rocks-all-the-way-down_2_1"> D. 8
</label>
</div>
<div class="field">
<input type="checkbox" name="input_02-its-rocks-all-the-way-down_2_1[]" id="input_02-its-rocks-all-the-way-down_2_1_choice_4" class="field-input input-checkbox" value="choice_4"/><label id="02-its-rocks-all-the-way-down_2_1-choice_4-label" for="input_02-its-rocks-all-the-way-down_2_1_choice_4" class="response-label field-label label-inline" aria-describedby="status_02-its-rocks-all-the-way-down_2_1"> E. 10
</label>
</div>
<div class="field">
<input type="checkbox" name="input_02-its-rocks-all-the-way-down_2_1[]" id="input_02-its-rocks-all-the-way-down_2_1_choice_5" class="field-input input-checkbox" value="choice_5"/><label id="02-its-rocks-all-the-way-down_2_1-choice_5-label" for="input_02-its-rocks-all-the-way-down_2_1_choice_5" class="response-label field-label label-inline" aria-describedby="status_02-its-rocks-all-the-way-down_2_1"> F. 12
</label>
</div>
<span id="answer_02-its-rocks-all-the-way-down_2_1"/>
</fieldset>
<div class="indicator-container">
<span class="status unanswered" id="status_02-its-rocks-all-the-way-down_2_1" data-tooltip="Not yet answered.">
<span class="sr">unanswered</span><span class="status-icon" aria-hidden="true"/>
</span>
</div>
</div></div>
<div class="solution-span">
<span id="solution_02-its-rocks-all-the-way-down_solution_1"/>
</div></div>
<div class="action">
<input type="hidden" name="problem_id" value="It&#39;s rocks all the way down" />
<div class="submit-attempt-container">
<button type="button" class="submit btn-brand" data-submitting="Submitting" data-value="Submit" data-should-enable-submit-button="True" aria-describedby="submission_feedback_02-its-rocks-all-the-way-down" >
<span class="submit-label">Submit</span>
</button>
<div class="submission-feedback" id="submission_feedback_02-its-rocks-all-the-way-down">
<span class="sr">Some problems have options such as save, reset, hints, or show answer. These options follow the Submit button.</span>
</div>
</div>
<div class="problem-action-buttons-wrapper">
</div>
</div>
<div class="notification warning notification-gentle-alert
is-hidden"
tabindex="-1">
<span class="icon fa fa-exclamation-circle" aria-hidden="true"></span>
<span class="notification-message" aria-describedby="02-its-rocks-all-the-way-down-problem-title">
</span>
<div class="notification-btn-wrapper">
<button type="button" class="btn btn-default btn-small notification-btn review-btn sr">Review</button>
</div>
</div>
<div class="notification warning notification-save
is-hidden"
tabindex="-1">
<span class="icon fa fa-save" aria-hidden="true"></span>
<span class="notification-message" aria-describedby="02-its-rocks-all-the-way-down-problem-title">None
</span>
<div class="notification-btn-wrapper">
<button type="button" class="btn btn-default btn-small notification-btn review-btn sr">Review</button>
</div>
</div>
<div class="notification general notification-show-answer
is-hidden"
tabindex="-1">
<span class="icon fa fa-info-circle" aria-hidden="true"></span>
<span class="notification-message" aria-describedby="02-its-rocks-all-the-way-down-problem-title">Answers are displayed within the problem
</span>
<div class="notification-btn-wrapper">
<button type="button" class="btn btn-default btn-small notification-btn review-btn sr">Review</button>
</div>
</div>
</div>
"
data-graded="True">
<p class="loading-spinner">
<i class="fa fa-spinner fa-pulse fa-2x fa-fw"></i>
<span class="sr">Loading…</span>
</p>
</div>
</div>
</div>
<div class="vert vert-2" data-id="block-v1:MITx+6.005.2x+1T2017+type@problem+block@02-pick-your-poison">
<div class="xblock xblock-public_view xblock-public_view-problem xmodule_display xmodule_ProblemBlock" data-has-score="True" data-runtime-class="LmsRuntime" data-graded="True" data-request-token="3f7f1aefe9a311efbd7412d4917dea95" data-runtime-version="1" data-block-type="problem" data-course-id="course-v1:MITx+6.005.2x+1T2017" data-init="XBlockToXModuleShim" data-usage-id="block-v1:MITx+6.005.2x+1T2017+type@problem+block@02-pick-your-poison">
<script type="json/xblock-args" class="xblock-json-init-args">
{"xmodule-type": "Problem"}
</script>
<div id="problem_02-pick-your-poison" class="problems-wrapper" role="group"
aria-labelledby="02-pick-your-poison-problem-title"
data-problem-id="block-v1:MITx+6.005.2x+1T2017+type@problem+block@02-pick-your-poison" data-url="/courses/course-v1:MITx+6.005.2x+1T2017/xblock/block-v1:MITx+6.005.2x+1T2017+type@problem+block@02-pick-your-poison/handler/xmodule_handler"
data-problem-score="0"
data-problem-total-possible="1"
data-attempts-used="0"
data-content="
<h3 class="hd hd-3 problem-header" id="02-pick-your-poison-problem-title" aria-describedby="block-v1:MITx+6.005.2x+1T2017+type@problem+block@02-pick-your-poison-problem-progress" tabindex="-1">
Pick your poison
</h3>
<div class="problem-progress" id="block-v1:MITx+6.005.2x+1T2017+type@problem+block@02-pick-your-poison-problem-progress"></div>
<div class="problem">
<div>
<p>Given their definitions, which of the following immutable datatypes would be able to represent a pair of integers?</p>
<div class="wrapper-problem-response" tabindex="-1" aria-label="Question 1" role="group"><div class="choicegroup capa_inputtype" id="inputtype_02-pick-your-poison_2_1">
<fieldset aria-describedby="status_02-pick-your-poison_2_1">
<div class="field">
<input type="checkbox" name="input_02-pick-your-poison_2_1[]" id="input_02-pick-your-poison_2_1_choice_0" class="field-input input-checkbox" value="choice_0"/><label id="02-pick-your-poison_2_1-choice_0-label" for="input_02-pick-your-poison_2_1_choice_0" class="response-label field-label label-inline" aria-describedby="status_02-pick-your-poison_2_1"> T = A(x:int) + B(a1:A, a2:A)
</label>
</div>
<div class="field">
<input type="checkbox" name="input_02-pick-your-poison_2_1[]" id="input_02-pick-your-poison_2_1_choice_1" class="field-input input-checkbox" value="choice_1"/><label id="02-pick-your-poison_2_1-choice_1-label" for="input_02-pick-your-poison_2_1_choice_1" class="response-label field-label label-inline" aria-describedby="status_02-pick-your-poison_2_1"> U = D(x:int, y:int)
</label>
</div>
<div class="field">
<input type="checkbox" name="input_02-pick-your-poison_2_1[]" id="input_02-pick-your-poison_2_1_choice_2" class="field-input input-checkbox" value="choice_2"/><label id="02-pick-your-poison_2_1-choice_2-label" for="input_02-pick-your-poison_2_1_choice_2" class="response-label field-label label-inline" aria-describedby="status_02-pick-your-poison_2_1"> V = F(z:int, V) + G(z:int, V)
</label>
</div>
<div class="field">
<input type="checkbox" name="input_02-pick-your-poison_2_1[]" id="input_02-pick-your-poison_2_1_choice_3" class="field-input input-checkbox" value="choice_3"/><label id="02-pick-your-poison_2_1-choice_3-label" for="input_02-pick-your-poison_2_1_choice_3" class="response-label field-label label-inline" aria-describedby="status_02-pick-your-poison_2_1"> W = K(y:int) + L(z:int, W)
</label>
</div>
<div class="field">
<input type="checkbox" name="input_02-pick-your-poison_2_1[]" id="input_02-pick-your-poison_2_1_choice_4" class="field-input input-checkbox" value="choice_4"/><label id="02-pick-your-poison_2_1-choice_4-label" for="input_02-pick-your-poison_2_1_choice_4" class="response-label field-label label-inline" aria-describedby="status_02-pick-your-poison_2_1"> X = M + N(y:int, X)
</label>
</div>
<span id="answer_02-pick-your-poison_2_1"/>
</fieldset>
<div class="indicator-container">
<span class="status unanswered" id="status_02-pick-your-poison_2_1" data-tooltip="Not yet answered.">
<span class="sr">unanswered</span><span class="status-icon" aria-hidden="true"/>
</span>
</div>
</div></div>
<div class="solution-span">
<span id="solution_02-pick-your-poison_solution_1"/>
</div></div>
<div class="action">
<input type="hidden" name="problem_id" value="Pick your poison" />
<div class="submit-attempt-container">
<button type="button" class="submit btn-brand" data-submitting="Submitting" data-value="Submit" data-should-enable-submit-button="True" aria-describedby="submission_feedback_02-pick-your-poison" >
<span class="submit-label">Submit</span>
</button>
<div class="submission-feedback" id="submission_feedback_02-pick-your-poison">
<span class="sr">Some problems have options such as save, reset, hints, or show answer. These options follow the Submit button.</span>
</div>
</div>
<div class="problem-action-buttons-wrapper">
</div>
</div>
<div class="notification warning notification-gentle-alert
is-hidden"
tabindex="-1">
<span class="icon fa fa-exclamation-circle" aria-hidden="true"></span>
<span class="notification-message" aria-describedby="02-pick-your-poison-problem-title">
</span>
<div class="notification-btn-wrapper">
<button type="button" class="btn btn-default btn-small notification-btn review-btn sr">Review</button>
</div>
</div>
<div class="notification warning notification-save
is-hidden"
tabindex="-1">
<span class="icon fa fa-save" aria-hidden="true"></span>
<span class="notification-message" aria-describedby="02-pick-your-poison-problem-title">None
</span>
<div class="notification-btn-wrapper">
<button type="button" class="btn btn-default btn-small notification-btn review-btn sr">Review</button>
</div>
</div>
<div class="notification general notification-show-answer
is-hidden"
tabindex="-1">
<span class="icon fa fa-info-circle" aria-hidden="true"></span>
<span class="notification-message" aria-describedby="02-pick-your-poison-problem-title">Answers are displayed within the problem
</span>
<div class="notification-btn-wrapper">
<button type="button" class="btn btn-default btn-small notification-btn review-btn sr">Review</button>
</div>
</div>
</div>
"
data-graded="True">
<p class="loading-spinner">
<i class="fa fa-spinner fa-pulse fa-2x fa-fw"></i>
<span class="sr">Loading…</span>
</p>
</div>
</div>
</div>
<div class="vert vert-3" data-id="block-v1:MITx+6.005.2x+1T2017+type@problem+block@02-i-heard-you-like-poison-so">
<div class="xblock xblock-public_view xblock-public_view-problem xmodule_display xmodule_ProblemBlock" data-has-score="True" data-runtime-class="LmsRuntime" data-graded="True" data-request-token="3f7f1aefe9a311efbd7412d4917dea95" data-runtime-version="1" data-block-type="problem" data-course-id="course-v1:MITx+6.005.2x+1T2017" data-init="XBlockToXModuleShim" data-usage-id="block-v1:MITx+6.005.2x+1T2017+type@problem+block@02-i-heard-you-like-poison-so">
<script type="json/xblock-args" class="xblock-json-init-args">
{"xmodule-type": "Problem"}
</script>
<div id="problem_02-i-heard-you-like-poison-so" class="problems-wrapper" role="group"
aria-labelledby="02-i-heard-you-like-poison-so-problem-title"
data-problem-id="block-v1:MITx+6.005.2x+1T2017+type@problem+block@02-i-heard-you-like-poison-so" data-url="/courses/course-v1:MITx+6.005.2x+1T2017/xblock/block-v1:MITx+6.005.2x+1T2017+type@problem+block@02-i-heard-you-like-poison-so/handler/xmodule_handler"
data-problem-score="0"
data-problem-total-possible="1"
data-attempts-used="0"
data-content="
<h3 class="hd hd-3 problem-header" id="02-i-heard-you-like-poison-so-problem-title" aria-describedby="block-v1:MITx+6.005.2x+1T2017+type@problem+block@02-i-heard-you-like-poison-so-problem-progress" tabindex="-1">
I heard you like poison, so...
</h3>
<div class="problem-progress" id="block-v1:MITx+6.005.2x+1T2017+type@problem+block@02-i-heard-you-like-poison-so-problem-progress"></div>
<div class="problem">
<div>
<p>From the previous question, which datatypes are recursive?</p>
<div class="wrapper-problem-response" tabindex="-1" aria-label="Question 1" role="group"><div class="choicegroup capa_inputtype" id="inputtype_02-i-heard-you-like-poison-so_2_1">
<fieldset aria-describedby="status_02-i-heard-you-like-poison-so_2_1">
<div class="field">
<input type="checkbox" name="input_02-i-heard-you-like-poison-so_2_1[]" id="input_02-i-heard-you-like-poison-so_2_1_choice_0" class="field-input input-checkbox" value="choice_0"/><label id="02-i-heard-you-like-poison-so_2_1-choice_0-label" for="input_02-i-heard-you-like-poison-so_2_1_choice_0" class="response-label field-label label-inline" aria-describedby="status_02-i-heard-you-like-poison-so_2_1"> T
</label>
</div>
<div class="field">
<input type="checkbox" name="input_02-i-heard-you-like-poison-so_2_1[]" id="input_02-i-heard-you-like-poison-so_2_1_choice_1" class="field-input input-checkbox" value="choice_1"/><label id="02-i-heard-you-like-poison-so_2_1-choice_1-label" for="input_02-i-heard-you-like-poison-so_2_1_choice_1" class="response-label field-label label-inline" aria-describedby="status_02-i-heard-you-like-poison-so_2_1"> U
</label>
</div>
<div class="field">
<input type="checkbox" name="input_02-i-heard-you-like-poison-so_2_1[]" id="input_02-i-heard-you-like-poison-so_2_1_choice_2" class="field-input input-checkbox" value="choice_2"/><label id="02-i-heard-you-like-poison-so_2_1-choice_2-label" for="input_02-i-heard-you-like-poison-so_2_1_choice_2" class="response-label field-label label-inline" aria-describedby="status_02-i-heard-you-like-poison-so_2_1"> V
</label>
</div>
<div class="field">
<input type="checkbox" name="input_02-i-heard-you-like-poison-so_2_1[]" id="input_02-i-heard-you-like-poison-so_2_1_choice_3" class="field-input input-checkbox" value="choice_3"/><label id="02-i-heard-you-like-poison-so_2_1-choice_3-label" for="input_02-i-heard-you-like-poison-so_2_1_choice_3" class="response-label field-label label-inline" aria-describedby="status_02-i-heard-you-like-poison-so_2_1"> W
</label>
</div>
<div class="field">
<input type="checkbox" name="input_02-i-heard-you-like-poison-so_2_1[]" id="input_02-i-heard-you-like-poison-so_2_1_choice_4" class="field-input input-checkbox" value="choice_4"/><label id="02-i-heard-you-like-poison-so_2_1-choice_4-label" for="input_02-i-heard-you-like-poison-so_2_1_choice_4" class="response-label field-label label-inline" aria-describedby="status_02-i-heard-you-like-poison-so_2_1"> X
</label>
</div>
<span id="answer_02-i-heard-you-like-poison-so_2_1"/>
</fieldset>
<div class="indicator-container">
<span class="status unanswered" id="status_02-i-heard-you-like-poison-so_2_1" data-tooltip="Not yet answered.">
<span class="sr">unanswered</span><span class="status-icon" aria-hidden="true"/>
</span>
</div>
</div></div>
<div class="solution-span">
<span id="solution_02-i-heard-you-like-poison-so_solution_1"/>
</div></div>
<div class="action">
<input type="hidden" name="problem_id" value="I heard you like poison, so..." />
<div class="submit-attempt-container">
<button type="button" class="submit btn-brand" data-submitting="Submitting" data-value="Submit" data-should-enable-submit-button="True" aria-describedby="submission_feedback_02-i-heard-you-like-poison-so" >
<span class="submit-label">Submit</span>
</button>
<div class="submission-feedback" id="submission_feedback_02-i-heard-you-like-poison-so">
<span class="sr">Some problems have options such as save, reset, hints, or show answer. These options follow the Submit button.</span>
</div>
</div>
<div class="problem-action-buttons-wrapper">
</div>
</div>
<div class="notification warning notification-gentle-alert
is-hidden"
tabindex="-1">
<span class="icon fa fa-exclamation-circle" aria-hidden="true"></span>
<span class="notification-message" aria-describedby="02-i-heard-you-like-poison-so-problem-title">
</span>
<div class="notification-btn-wrapper">
<button type="button" class="btn btn-default btn-small notification-btn review-btn sr">Review</button>
</div>
</div>
<div class="notification warning notification-save
is-hidden"
tabindex="-1">
<span class="icon fa fa-save" aria-hidden="true"></span>
<span class="notification-message" aria-describedby="02-i-heard-you-like-poison-so-problem-title">None
</span>
<div class="notification-btn-wrapper">
<button type="button" class="btn btn-default btn-small notification-btn review-btn sr">Review</button>
</div>
</div>
<div class="notification general notification-show-answer
is-hidden"
tabindex="-1">
<span class="icon fa fa-info-circle" aria-hidden="true"></span>
<span class="notification-message" aria-describedby="02-i-heard-you-like-poison-so-problem-title">Answers are displayed within the problem
</span>
<div class="notification-btn-wrapper">
<button type="button" class="btn btn-default btn-small notification-btn review-btn sr">Review</button>
</div>
</div>
</div>
"
data-graded="True">
<p class="loading-spinner">
<i class="fa fa-spinner fa-pulse fa-2x fa-fw"></i>
<span class="sr">Loading…</span>
</p>
</div>
</div>
</div>
<div class="vert vert-4" data-id="block-v1:MITx+6.005.2x+1T2017+type@problem+block@02-vvvvvv">
<div class="xblock xblock-public_view xblock-public_view-problem xmodule_display xmodule_ProblemBlock" data-has-score="True" data-runtime-class="LmsRuntime" data-graded="True" data-request-token="3f7f1aefe9a311efbd7412d4917dea95" data-runtime-version="1" data-block-type="problem" data-course-id="course-v1:MITx+6.005.2x+1T2017" data-init="XBlockToXModuleShim" data-usage-id="block-v1:MITx+6.005.2x+1T2017+type@problem+block@02-vvvvvv">
<script type="json/xblock-args" class="xblock-json-init-args">
{"xmodule-type": "Problem"}
</script>
<div id="problem_02-vvvvvv" class="problems-wrapper" role="group"
aria-labelledby="02-vvvvvv-problem-title"
data-problem-id="block-v1:MITx+6.005.2x+1T2017+type@problem+block@02-vvvvvv" data-url="/courses/course-v1:MITx+6.005.2x+1T2017/xblock/block-v1:MITx+6.005.2x+1T2017+type@problem+block@02-vvvvvv/handler/xmodule_handler"
data-problem-score="0"
data-problem-total-possible="1"
data-attempts-used="0"
data-content="
<h3 class="hd hd-3 problem-header" id="02-vvvvvv-problem-title" aria-describedby="block-v1:MITx+6.005.2x+1T2017+type@problem+block@02-vvvvvv-problem-progress" tabindex="-1">
VVVVVV
</h3>
<div class="problem-progress" id="block-v1:MITx+6.005.2x+1T2017+type@problem+block@02-vvvvvv-problem-progress"></div>
<div class="problem">
<div>
<p>Also from that question, which is a problem with type <code>V</code>?</p>
<div class="wrapper-problem-response" tabindex="-1" aria-label="Question 1" role="group"><div class="choicegroup capa_inputtype" id="inputtype_02-vvvvvv_2_1">
<fieldset aria-describedby="status_02-vvvvvv_2_1">
<div class="field">
<input type="radio" name="input_02-vvvvvv_2_1" id="input_02-vvvvvv_2_1_choice_0" class="field-input input-radio" value="choice_0"/><label id="02-vvvvvv_2_1-choice_0-label" for="input_02-vvvvvv_2_1_choice_0" class="response-label field-label label-inline" aria-describedby="status_02-vvvvvv_2_1"> we cannot construct a V that holds any integers
</label>
</div>
<div class="field">
<input type="radio" name="input_02-vvvvvv_2_1" id="input_02-vvvvvv_2_1_choice_1" class="field-input input-radio" value="choice_1"/><label id="02-vvvvvv_2_1-choice_1-label" for="input_02-vvvvvv_2_1_choice_1" class="response-label field-label label-inline" aria-describedby="status_02-vvvvvv_2_1"> we cannot construct a V that holds zero integers
</label>
</div>
<div class="field">
<input type="radio" name="input_02-vvvvvv_2_1" id="input_02-vvvvvv_2_1_choice_2" class="field-input input-radio" value="choice_2"/><label id="02-vvvvvv_2_1-choice_2-label" for="input_02-vvvvvv_2_1_choice_2" class="response-label field-label label-inline" aria-describedby="status_02-vvvvvv_2_1"> we cannot construct a V that holds more than 1 integer
</label>
</div>
<div class="field">
<input type="radio" name="input_02-vvvvvv_2_1" id="input_02-vvvvvv_2_1_choice_3" class="field-input input-radio" value="choice_3"/><label id="02-vvvvvv_2_1-choice_3-label" for="input_02-vvvvvv_2_1_choice_3" class="response-label field-label label-inline" aria-describedby="status_02-vvvvvv_2_1"> we cannot construct a V that holds fewer than 3 integers
</label>
</div>
<div class="field">
<input type="radio" name="input_02-vvvvvv_2_1" id="input_02-vvvvvv_2_1_choice_4" class="field-input input-radio" value="choice_4"/><label id="02-vvvvvv_2_1-choice_4-label" for="input_02-vvvvvv_2_1_choice_4" class="response-label field-label label-inline" aria-describedby="status_02-vvvvvv_2_1"> we cannot construct any instances of V at all
</label>
</div>
<span id="answer_02-vvvvvv_2_1"/>
</fieldset>
<div class="indicator-container">
<span class="status unanswered" id="status_02-vvvvvv_2_1" data-tooltip="Not yet answered.">
<span class="sr">unanswered</span><span class="status-icon" aria-hidden="true"/>
</span>
</div>
</div></div>
<div class="solution-span">
<span id="solution_02-vvvvvv_solution_1"/>
</div></div>
<div class="action">
<input type="hidden" name="problem_id" value="VVVVVV" />
<div class="submit-attempt-container">
<button type="button" class="submit btn-brand" data-submitting="Submitting" data-value="Submit" data-should-enable-submit-button="True" aria-describedby="submission_feedback_02-vvvvvv" >
<span class="submit-label">Submit</span>
</button>
<div class="submission-feedback" id="submission_feedback_02-vvvvvv">
<span class="sr">Some problems have options such as save, reset, hints, or show answer. These options follow the Submit button.</span>
</div>
</div>
<div class="problem-action-buttons-wrapper">
</div>
</div>
<div class="notification warning notification-gentle-alert
is-hidden"
tabindex="-1">
<span class="icon fa fa-exclamation-circle" aria-hidden="true"></span>
<span class="notification-message" aria-describedby="02-vvvvvv-problem-title">
</span>
<div class="notification-btn-wrapper">
<button type="button" class="btn btn-default btn-small notification-btn review-btn sr">Review</button>
</div>
</div>
<div class="notification warning notification-save
is-hidden"
tabindex="-1">
<span class="icon fa fa-save" aria-hidden="true"></span>
<span class="notification-message" aria-describedby="02-vvvvvv-problem-title">None
</span>
<div class="notification-btn-wrapper">
<button type="button" class="btn btn-default btn-small notification-btn review-btn sr">Review</button>
</div>
</div>
<div class="notification general notification-show-answer
is-hidden"
tabindex="-1">
<span class="icon fa fa-info-circle" aria-hidden="true"></span>
<span class="notification-message" aria-describedby="02-vvvvvv-problem-title">Answers are displayed within the problem
</span>
<div class="notification-btn-wrapper">
<button type="button" class="btn btn-default btn-small notification-btn review-btn sr">Review</button>
</div>
</div>
</div>
"
data-graded="True">
<p class="loading-spinner">
<i class="fa fa-spinner fa-pulse fa-2x fa-fw"></i>
<span class="sr">Loading…</span>
</p>
</div>
</div>
</div>
<div class="vert vert-5" data-id="block-v1:MITx+6.005.2x+1T2017+type@problem+block@02-bottom-of-the-barrel">
<div class="xblock xblock-public_view xblock-public_view-problem xmodule_display xmodule_ProblemBlock" data-has-score="True" data-runtime-class="LmsRuntime" data-graded="True" data-request-token="3f7f1aefe9a311efbd7412d4917dea95" data-runtime-version="1" data-block-type="problem" data-course-id="course-v1:MITx+6.005.2x+1T2017" data-init="XBlockToXModuleShim" data-usage-id="block-v1:MITx+6.005.2x+1T2017+type@problem+block@02-bottom-of-the-barrel">
<script type="json/xblock-args" class="xblock-json-init-args">
{"xmodule-type": "Problem"}
</script>
<div id="problem_02-bottom-of-the-barrel" class="problems-wrapper" role="group"
aria-labelledby="02-bottom-of-the-barrel-problem-title"
data-problem-id="block-v1:MITx+6.005.2x+1T2017+type@problem+block@02-bottom-of-the-barrel" data-url="/courses/course-v1:MITx+6.005.2x+1T2017/xblock/block-v1:MITx+6.005.2x+1T2017+type@problem+block@02-bottom-of-the-barrel/handler/xmodule_handler"
data-problem-score="0"
data-problem-total-possible="1"
data-attempts-used="0"
data-content="
<h3 class="hd hd-3 problem-header" id="02-bottom-of-the-barrel-problem-title" aria-describedby="block-v1:MITx+6.005.2x+1T2017+type@problem+block@02-bottom-of-the-barrel-problem-progress" tabindex="-1">
Bottom of the barrel
</h3>
<div class="problem-progress" id="block-v1:MITx+6.005.2x+1T2017+type@problem+block@02-bottom-of-the-barrel-problem-progress"></div>
<div class="problem">
<div>
<p>Also from that question, we saw that type <code>X</code> is just our <code>ImList</code> in disguise (and only for integers). Which are possible problems with type <code>W</code> compared to type <code>X</code>?</p>
<div class="wrapper-problem-response" tabindex="-1" aria-label="Question 1" role="group"><div class="choicegroup capa_inputtype" id="inputtype_02-bottom-of-the-barrel_2_1">
<fieldset aria-describedby="status_02-bottom-of-the-barrel_2_1">
<div class="field">
<input type="checkbox" name="input_02-bottom-of-the-barrel_2_1[]" id="input_02-bottom-of-the-barrel_2_1_choice_0" class="field-input input-checkbox" value="choice_0"/><label id="02-bottom-of-the-barrel_2_1-choice_0-label" for="input_02-bottom-of-the-barrel_2_1_choice_0" class="response-label field-label label-inline" aria-describedby="status_02-bottom-of-the-barrel_2_1"> we cannot construct a W that holds any integers
</label>
</div>
<div class="field">
<input type="checkbox" name="input_02-bottom-of-the-barrel_2_1[]" id="input_02-bottom-of-the-barrel_2_1_choice_1" class="field-input input-checkbox" value="choice_1"/><label id="02-bottom-of-the-barrel_2_1-choice_1-label" for="input_02-bottom-of-the-barrel_2_1_choice_1" class="response-label field-label label-inline" aria-describedby="status_02-bottom-of-the-barrel_2_1"> we cannot construct a W that holds zero integers
</label>
</div>
<div class="field">
<input type="checkbox" name="input_02-bottom-of-the-barrel_2_1[]" id="input_02-bottom-of-the-barrel_2_1_choice_2" class="field-input input-checkbox" value="choice_2"/><label id="02-bottom-of-the-barrel_2_1-choice_2-label" for="input_02-bottom-of-the-barrel_2_1_choice_2" class="response-label field-label label-inline" aria-describedby="status_02-bottom-of-the-barrel_2_1"> we cannot construct a W that holds more than 1 integer
</label>
</div>
<div class="field">
<input type="checkbox" name="input_02-bottom-of-the-barrel_2_1[]" id="input_02-bottom-of-the-barrel_2_1_choice_3" class="field-input input-checkbox" value="choice_3"/><label id="02-bottom-of-the-barrel_2_1-choice_3-label" for="input_02-bottom-of-the-barrel_2_1_choice_3" class="response-label field-label label-inline" aria-describedby="status_02-bottom-of-the-barrel_2_1"> we cannot construct a W that holds fewer than 3 integers
</label>
</div>
<div class="field">
<input type="checkbox" name="input_02-bottom-of-the-barrel_2_1[]" id="input_02-bottom-of-the-barrel_2_1_choice_4" class="field-input input-checkbox" value="choice_4"/><label id="02-bottom-of-the-barrel_2_1-choice_4-label" for="input_02-bottom-of-the-barrel_2_1_choice_4" class="response-label field-label label-inline" aria-describedby="status_02-bottom-of-the-barrel_2_1"> we cannot construct any instances of W at all
</label>
</div>
<span id="answer_02-bottom-of-the-barrel_2_1"/>
</fieldset>
<div class="indicator-container">
<span class="status unanswered" id="status_02-bottom-of-the-barrel_2_1" data-tooltip="Not yet answered.">
<span class="sr">unanswered</span><span class="status-icon" aria-hidden="true"/>
</span>
</div>
</div></div>
<div class="solution-span">
<span id="solution_02-bottom-of-the-barrel_solution_1"/>
</div></div>
<div class="action">
<input type="hidden" name="problem_id" value="Bottom of the barrel" />
<div class="submit-attempt-container">
<button type="button" class="submit btn-brand" data-submitting="Submitting" data-value="Submit" data-should-enable-submit-button="True" aria-describedby="submission_feedback_02-bottom-of-the-barrel" >
<span class="submit-label">Submit</span>
</button>
<div class="submission-feedback" id="submission_feedback_02-bottom-of-the-barrel">
<span class="sr">Some problems have options such as save, reset, hints, or show answer. These options follow the Submit button.</span>
</div>
</div>
<div class="problem-action-buttons-wrapper">
</div>
</div>
<div class="notification warning notification-gentle-alert
is-hidden"
tabindex="-1">
<span class="icon fa fa-exclamation-circle" aria-hidden="true"></span>
<span class="notification-message" aria-describedby="02-bottom-of-the-barrel-problem-title">
</span>
<div class="notification-btn-wrapper">
<button type="button" class="btn btn-default btn-small notification-btn review-btn sr">Review</button>
</div>
</div>
<div class="notification warning notification-save
is-hidden"
tabindex="-1">
<span class="icon fa fa-save" aria-hidden="true"></span>
<span class="notification-message" aria-describedby="02-bottom-of-the-barrel-problem-title">None
</span>
<div class="notification-btn-wrapper">
<button type="button" class="btn btn-default btn-small notification-btn review-btn sr">Review</button>
</div>
</div>
<div class="notification general notification-show-answer
is-hidden"
tabindex="-1">
<span class="icon fa fa-info-circle" aria-hidden="true"></span>
<span class="notification-message" aria-describedby="02-bottom-of-the-barrel-problem-title">Answers are displayed within the problem
</span>
<div class="notification-btn-wrapper">
<button type="button" class="btn btn-default btn-small notification-btn review-btn sr">Review</button>
</div>
</div>
</div>
"
data-graded="True">
<p class="loading-spinner">
<i class="fa fa-spinner fa-pulse fa-2x fa-fw"></i>
<span class="sr">Loading…</span>
</p>
</div>
</div>
</div>
</div>
</div>
<div class="xblock xblock-public_view xblock-public_view-vertical" data-has-score="False" data-runtime-class="LmsRuntime" data-graded="True" data-request-token="3f7f1aefe9a311efbd7412d4917dea95" data-runtime-version="1" data-block-type="vertical" data-course-id="course-v1:MITx+6.005.2x+1T2017" data-init="VerticalStudentView" data-usage-id="block-v1:MITx+6.005.2x+1T2017+type@vertical+block@vertical-functions-over-recursive-datatypes">
<h2 class="hd hd-2 unit-title">Functions over recursive datatypes</h2>
<div class="vert-mod">
<div class="vert vert-0" data-id="block-v1:MITx+6.005.2x+1T2017+type@html+block@html_343e252527da">
<div class="xblock xblock-public_view xblock-public_view-html xmodule_display xmodule_HtmlBlock" data-has-score="False" data-runtime-class="LmsRuntime" data-graded="True" data-request-token="3f7f1aefe9a311efbd7412d4917dea95" data-runtime-version="1" data-block-type="html" data-course-id="course-v1:MITx+6.005.2x+1T2017" data-init="XBlockToXModuleShim" data-usage-id="block-v1:MITx+6.005.2x+1T2017+type@html+block@html_343e252527da">
<script type="json/xblock-args" class="xblock-json-init-args">
{"xmodule-type": "HTMLModule"}
</script>
<link href="/assets/courseware/v1/b2188f0a95a7a9062748278f7d5a584f/asset-v1:MITx+6.005.2x+1T2017+type@asset+block/syntax-highlighting.css" rel="stylesheet" type="text/css" />
<h2 id="functions_over_recursive_datatypes">Functions over recursive datatypes</h2>
<div data-outline="functions_over_recursive_datatypes">
<p>This way of thinking about datatypes — as a recursive definition of an abstract datatype with concrete variants — is appealing not only because it can handle recursive and unbounded structures like lists and trees, but also because it provides a convenient way to describe operations over the datatype, as functions with one case per variant.</p>
<p>For example, consider the size of the list, which is certainly an operation we'll want in <code>ImList</code>. We can define it like this:</p>
<p><strong>size : ImList → int</strong> // returns the size of the list</p>
<p>and then fully specify its meaning by defining <em>size</em> for each variant of <code>ImList</code>: </p>
<blockquote>
<p>size(Empty) = 0
<br> size(Cons(first: E, rest: ImList)) = 1 + size(rest)</p>
</blockquote>
<p>This function is recursive. We can think about the execution of <em>size</em> on a particular list as a series of reduction steps:</p>
<blockquote>
<p>size(Cons (0, Cons (1, Empty)))
<br> = 1 + size(Cons (1, Empty))
<br> = 1 + (1 + size(Empty))
<br> = 1 + (1 + 0)
<br> = 1 + 1
<br> = 2</p>
</blockquote>
<p>And the cases from the definition can be translated directly into Java as methods in <code>ImList</code>, <code>Empty</code>, and <code>Cons</code>:</p><pre><code class="language-java hljs"><span class="hljs-keyword">public</span> <span class="hljs-class"><span class="hljs-keyword">interface</span> <span class="hljs-title">ImList</span><<span class="hljs-title">E</span>> </span>{
<span class="hljs-comment">// ...</span>
<span class="hljs-function"><span class="hljs-keyword">public</span> <span class="hljs-keyword">int</span> <span class="hljs-title">size</span><span class="hljs-params">()</span></span>;
}
<span class="hljs-keyword">public</span> <span class="hljs-class"><span class="hljs-keyword">class</span> <span class="hljs-title">Empty</span><<span class="hljs-title">E</span>> <span class="hljs-keyword">implements</span> <span class="hljs-title">ImList</span><<span class="hljs-title">E</span>> </span>{
<span class="hljs-comment">// ...</span>
<span class="hljs-function"><span class="hljs-keyword">public</span> <span class="hljs-keyword">int</span> <span class="hljs-title">size</span><span class="hljs-params">()</span> </span>{ <span class="hljs-keyword">return</span> <span class="hljs-number">0</span>; }
}
<span class="hljs-keyword">public</span> <span class="hljs-class"><span class="hljs-keyword">class</span> <span class="hljs-title">Cons</span><<span class="hljs-title">E</span>> <span class="hljs-keyword">implements</span> <span class="hljs-title">ImList</span><<span class="hljs-title">E</span>> </span>{
<span class="hljs-comment">// ...</span>
<span class="hljs-function"><span class="hljs-keyword">public</span> <span class="hljs-keyword">int</span> <span class="hljs-title">size</span><span class="hljs-params">()</span> </span>{ <span class="hljs-keyword">return</span> <span class="hljs-number">1</span> + rest.size(); }
}</code></pre>
<p>This pattern of implementing an operation over a recursive datatype by</p>
<ul>
<li><strong>declaring</strong> the operation in the abstract datatype interface</li>
<li><strong>implementing</strong> the operation (recursively) in each concrete variant</li>
</ul>
<p>is a very common and practical design pattern. It sometimes goes by the unhelpful name <em>interpreter pattern</em>.</p>
<p>Let's try a few more examples:</p>
<p><strong>isEmpty : ImList → boolean</strong></p>
<blockquote>
<p>isEmpty(Empty) = true
<br> isEmpty(Cons(first: E, rest: ImList)) = false</p>
</blockquote>
<p><strong>contains : ImList × E → boolean</strong></p>
<blockquote>
<p>contains(Empty, e: E) = false
<br> contains(Cons(first: E, rest: ImList), e: E) = (first = e) ∨ contains(rest, e)</p>
</blockquote>
<p><strong>get: ImList × int → E</strong></p>
<blockquote>
<p>get(Empty, n: int) = undefined
<br> get(Cons(first: E, rest: ImList), n: int) = if n=0 then first else get(rest, n-1)</p>
</blockquote>
<p><strong>append: ImList × ImList → ImList</strong></p>
<blockquote>
<p>append(Empty, list2: ImList) = list2
<br> append(Cons(first: E, rest: ImList), list2: ImList) = cons(first, append(rest, list2))</p>
</blockquote>
<p><strong>reverse: ImList → ImList</strong></p>
<blockquote>
<p>reverse(Empty) = empty()
<br> reverse(Cons(first: E, rest: ImList)) = append(reverse(rest), cons(first, empty())</p>
</blockquote>
<p>For <em>reverse</em>, it turns out that the recursive definition produces a pretty bad implementation in Java, with performance that's quadratic in the length of the list you're reversing. We could rewrite it using an iterative approach if needed.</p>
</div>
</div>
</div>
</div>
</div>
<div class="xblock xblock-public_view xblock-public_view-vertical" data-has-score="False" data-runtime-class="LmsRuntime" data-graded="True" data-request-token="3f7f1aefe9a311efbd7412d4917dea95" data-runtime-version="1" data-block-type="vertical" data-course-id="course-v1:MITx+6.005.2x+1T2017" data-init="VerticalStudentView" data-usage-id="block-v1:MITx+6.005.2x+1T2017+type@vertical+block@vertical_Questions_ae046f81cd6d">
<h2 class="hd hd-2 unit-title">Questions</h2>
<div class="vert-mod">
<div class="vert vert-0" data-id="block-v1:MITx+6.005.2x+1T2017+type@html+block@Functions_over_recursive_datatypes">
<div class="xblock xblock-public_view xblock-public_view-html xmodule_display xmodule_HtmlBlock" data-has-score="False" data-runtime-class="LmsRuntime" data-graded="True" data-request-token="3f7f1aefe9a311efbd7412d4917dea95" data-runtime-version="1" data-block-type="html" data-course-id="course-v1:MITx+6.005.2x+1T2017" data-init="XBlockToXModuleShim" data-usage-id="block-v1:MITx+6.005.2x+1T2017+type@html+block@Functions_over_recursive_datatypes">
<script type="json/xblock-args" class="xblock-json-init-args">
{"xmodule-type": "HTMLModule"}
</script>
<link href="/assets/courseware/v1/b2188f0a95a7a9062748278f7d5a584f/asset-v1:MITx+6.005.2x+1T2017+type@asset+block/syntax-highlighting.css" rel="stylesheet" type="text/css" />
<script src="/assets/courseware/v1/c9cee8830885f59e75b8782f44026226/asset-v1:MITx+6.005.2x+1T2017+type@asset+block/edx-script-v1.js"></script>
</div>
</div>
<div class="vert vert-1" data-id="block-v1:MITx+6.005.2x+1T2017+type@problem+block@02-isempty-no-isimplemented">
<div class="xblock xblock-public_view xblock-public_view-problem xmodule_display xmodule_ProblemBlock" data-has-score="True" data-runtime-class="LmsRuntime" data-graded="True" data-request-token="3f7f1aefe9a311efbd7412d4917dea95" data-runtime-version="1" data-block-type="problem" data-course-id="course-v1:MITx+6.005.2x+1T2017" data-init="XBlockToXModuleShim" data-usage-id="block-v1:MITx+6.005.2x+1T2017+type@problem+block@02-isempty-no-isimplemented">
<script type="json/xblock-args" class="xblock-json-init-args">
{"xmodule-type": "Problem"}
</script>
<div id="problem_02-isempty-no-isimplemented" class="problems-wrapper" role="group"
aria-labelledby="02-isempty-no-isimplemented-problem-title"
data-problem-id="block-v1:MITx+6.005.2x+1T2017+type@problem+block@02-isempty-no-isimplemented" data-url="/courses/course-v1:MITx+6.005.2x+1T2017/xblock/block-v1:MITx+6.005.2x+1T2017+type@problem+block@02-isempty-no-isimplemented/handler/xmodule_handler"
data-problem-score="0"
data-problem-total-possible="3"
data-attempts-used="0"
data-content="
<h3 class="hd hd-3 problem-header" id="02-isempty-no-isimplemented-problem-title" aria-describedby="block-v1:MITx+6.005.2x+1T2017+type@problem+block@02-isempty-no-isimplemented-problem-progress" tabindex="-1">
isEmpty? No, isImplemented!
</h3>
<div class="problem-progress" id="block-v1:MITx+6.005.2x+1T2017+type@problem+block@02-isempty-no-isimplemented-problem-progress"></div>
<div class="problem">
<div>
<pre>
isEmpty : ImList -&gt; boolean
isEmpty(Empty) = true
isEmpty(Cons(first:E, rest:ImList)) = false
</pre>
<p>Let's implement <code>ImList.isEmpty</code>.</p>
<pre>
public interface ImList&lt;E&gt;
// ...
/**
* @return true iff this list is empty
*/
</pre>
<div class="wrapper-problem-response" tabindex="-1" aria-label="Question 1" role="group"><div id="inputtype_02-isempty-no-isimplemented_2_1" class=" capa_inputtype textline">
<div class="unanswered ">
<input type="text" name="input_02-isempty-no-isimplemented_2_1" id="input_02-isempty-no-isimplemented_2_1" aria-describedby="status_02-isempty-no-isimplemented_2_1" value="" size="20"/>
<span class="trailing_text" id="trailing_text_02-isempty-no-isimplemented_2_1"/>
<span class="status unanswered" id="status_02-isempty-no-isimplemented_2_1" data-tooltip="Not yet answered.">
<span class="sr">unanswered</span><span class="status-icon" aria-hidden="true"/>
</span>
<p id="answer_02-isempty-no-isimplemented_2_1" class="answer"/>
</div>
</div></div>
<div class="solution-span">
<span id="solution_02-isempty-no-isimplemented_solution_1"/>
</div><pre>
}
</pre>
<p>...</p>
<pre>
class Empty&lt;E&gt; implements ImList&lt;E&gt; {
// ...
public boolean isEmpty() {
</pre>
<div class="wrapper-problem-response" tabindex="-1" aria-label="Question 2" role="group"><div id="inputtype_02-isempty-no-isimplemented_3_1" class=" capa_inputtype textline">
<div class="unanswered ">
<input type="text" name="input_02-isempty-no-isimplemented_3_1" id="input_02-isempty-no-isimplemented_3_1" aria-describedby="status_02-isempty-no-isimplemented_3_1" value="" size="20"/>
<span class="trailing_text" id="trailing_text_02-isempty-no-isimplemented_3_1"/>
<span class="status unanswered" id="status_02-isempty-no-isimplemented_3_1" data-tooltip="Not yet answered.">
<span class="sr">unanswered</span><span class="status-icon" aria-hidden="true"/>
</span>
<p id="answer_02-isempty-no-isimplemented_3_1" class="answer"/>
</div>
</div></div>
<pre>
}
}
</pre>
<p>...</p>
<pre>
class Cons&lt;E&gt; implements ImList&lt;E&gt; {
private E e;
private ImList&lt;E&gt; rest;
// ...
public boolean isEmpty() {
</pre>
<div class="wrapper-problem-response" tabindex="-1" aria-label="Question 3" role="group"><div id="inputtype_02-isempty-no-isimplemented_4_1" class=" capa_inputtype textline">
<div class="unanswered ">
<input type="text" name="input_02-isempty-no-isimplemented_4_1" id="input_02-isempty-no-isimplemented_4_1" aria-describedby="status_02-isempty-no-isimplemented_4_1" value="" size="20"/>
<span class="trailing_text" id="trailing_text_02-isempty-no-isimplemented_4_1"/>
<span class="status unanswered" id="status_02-isempty-no-isimplemented_4_1" data-tooltip="Not yet answered.">
<span class="sr">unanswered</span><span class="status-icon" aria-hidden="true"/>
</span>
<p id="answer_02-isempty-no-isimplemented_4_1" class="answer"/>
</div>
</div></div>
<pre>
}
}
</pre>
</div>
<div class="action">
<input type="hidden" name="problem_id" value="isEmpty? No, isImplemented!" />
<div class="submit-attempt-container">
<button type="button" class="submit btn-brand" data-submitting="Submitting" data-value="Submit" data-should-enable-submit-button="True" aria-describedby="submission_feedback_02-isempty-no-isimplemented" >
<span class="submit-label">Submit</span>
</button>
<div class="submission-feedback" id="submission_feedback_02-isempty-no-isimplemented">
<span class="sr">Some problems have options such as save, reset, hints, or show answer. These options follow the Submit button.</span>
</div>
</div>
<div class="problem-action-buttons-wrapper">
</div>
</div>
<div class="notification warning notification-gentle-alert
is-hidden"
tabindex="-1">
<span class="icon fa fa-exclamation-circle" aria-hidden="true"></span>
<span class="notification-message" aria-describedby="02-isempty-no-isimplemented-problem-title">
</span>
<div class="notification-btn-wrapper">
<button type="button" class="btn btn-default btn-small notification-btn review-btn sr">Review</button>
</div>
</div>
<div class="notification warning notification-save
is-hidden"
tabindex="-1">
<span class="icon fa fa-save" aria-hidden="true"></span>
<span class="notification-message" aria-describedby="02-isempty-no-isimplemented-problem-title">None
</span>
<div class="notification-btn-wrapper">
<button type="button" class="btn btn-default btn-small notification-btn review-btn sr">Review</button>
</div>
</div>
<div class="notification general notification-show-answer
is-hidden"
tabindex="-1">
<span class="icon fa fa-info-circle" aria-hidden="true"></span>
<span class="notification-message" aria-describedby="02-isempty-no-isimplemented-problem-title">Answers are displayed within the problem
</span>
<div class="notification-btn-wrapper">
<button type="button" class="btn btn-default btn-small notification-btn review-btn sr">Review</button>
</div>
</div>
</div>
"
data-graded="True">
<p class="loading-spinner">
<i class="fa fa-spinner fa-pulse fa-2x fa-fw"></i>
<span class="sr">Loading…</span>
</p>
</div>
</div>
</div>
</div>
</div>
<div class="xblock xblock-public_view xblock-public_view-vertical" data-has-score="False" data-runtime-class="LmsRuntime" data-graded="True" data-request-token="3f7f1aefe9a311efbd7412d4917dea95" data-runtime-version="1" data-block-type="vertical" data-course-id="course-v1:MITx+6.005.2x+1T2017" data-init="VerticalStudentView" data-usage-id="block-v1:MITx+6.005.2x+1T2017+type@vertical+block@vertical-tuning-the-rep">
<h2 class="hd hd-2 unit-title">Null vs. empty, Declared type vs. actual type</h2>
<div class="vert-mod">
<div class="vert vert-0" data-id="block-v1:MITx+6.005.2x+1T2017+type@html+block@html_800fcaeee8ea">
<div class="xblock xblock-public_view xblock-public_view-html xmodule_display xmodule_HtmlBlock" data-has-score="False" data-runtime-class="LmsRuntime" data-graded="True" data-request-token="3f7f1aefe9a311efbd7412d4917dea95" data-runtime-version="1" data-block-type="html" data-course-id="course-v1:MITx+6.005.2x+1T2017" data-init="XBlockToXModuleShim" data-usage-id="block-v1:MITx+6.005.2x+1T2017+type@html+block@html_800fcaeee8ea">
<script type="json/xblock-args" class="xblock-json-init-args">
{"xmodule-type": "HTMLModule"}
</script>
<link href="/assets/courseware/v1/b2188f0a95a7a9062748278f7d5a584f/asset-v1:MITx+6.005.2x+1T2017+type@asset+block/syntax-highlighting.css" rel="stylesheet" type="text/css" />
<h2 id="tuning_the_rep">Tuning the rep</h2>
<div data-outline="tuning_the_rep">
<p>Getting the size of a list is a common operation. Right now our implementation of <code>size()</code> takes <a href="https://rob-bell.net/2009/06/a-beginners-guide-to-big-o-notation/"><em>O(n)</em> time</a>, where <em>n</em> is the length of the list — that's linear in the number of list items. We can make it better with a simple change to the rep of the list that caches the size the first time we compute it, so that subsequently it costs only <a href="https://rob-bell.net/2009/06/a-beginners-guide-to-big-o-notation/"><em>O(1)</em> time</a> — constant time, independent of the number of list items — to get:</p><pre><code class="language-java hljs"><span class="hljs-keyword">public</span> <span class="hljs-class"><span class="hljs-keyword">class</span> <span class="hljs-title">Cons</span><<span class="hljs-title">E</span>> <span class="hljs-keyword">implements</span> <span class="hljs-title">ImList</span><<span class="hljs-title">E</span>> </span>{
<span class="hljs-keyword">private</span> <span class="hljs-keyword">final</span> E e;
<span class="hljs-keyword">private</span> <span class="hljs-keyword">final</span> ImList<E> rest;
<span class="hljs-keyword">private</span> <span class="hljs-keyword">int</span> size = <span class="hljs-number">0</span>;
<span class="hljs-comment">// rep invariant:</span>
<span class="hljs-comment">// e != null, rest != null, size >= 0</span>
<span class="hljs-comment">// size > 0 implies size == 1+rest.size()</span>
<span class="hljs-comment">// ...</span>
<span class="hljs-function"><span class="hljs-keyword">public</span> <span class="hljs-keyword">int</span> <span class="hljs-title">size</span><span class="hljs-params">()</span> </span>{
<span class="hljs-keyword">if</span> (size == <span class="hljs-number">0</span>) size = <span class="hljs-number">1</span> + rest.size();
<span class="hljs-keyword">return</span> size;
}
}</code></pre>
<p>Note that we're using the special value 0 (which can never be the size of a <code>Cons</code>) to indicate that we haven't computed the size yet. Note also that this change introduces a new clause to the rep invariant, relating the <code>size</code> field to the <code>rest</code> field.</p>
<p>There's something interesting happening here: this is an immutable datatype, and yet it has a mutable rep. It's modifying its own size field, in this case to cache the result of an expensive operation. This is an example of a <strong>beneficent mutation</strong>, a state change that doesn't change the abstract value represented by the object, so the type is still immutable.</p>
<h3 id="rep_independence_and_rep_exposure_revisited">Rep independence and rep exposure revisited</h3>
<div data-outline="rep_independence_and_rep_exposure_revisited">
<p>Does our Java implementation of <code>ImList</code> still have rep independence? We've concealed the <code>Empty</code> contructor behind the static method <code>ImList.empty()</code>, and clients should never need to use the <code>Empty</code> or <code>Cons</code> constructors directly. We can hide them further by making them package-private (declared with neither the <code>public</code> nor <code>private</code> keyword) so that classes outside of <code>ImList</code>'s package cannot see or use them.</p>
<p>We have a great deal of freedom to change our implementation — indeed, we just added a <code>size</code> field to the internal rep of <code>Cons</code>. We could even have an extra array in there to make <code>get()</code> run fast! This might get expensive in space, however, but we are free to make those tradeoffs.</p>
<p>Is there rep exposure because <code>Cons.rest()</code> returns a reference to its internal list? Could a clumsy client add elements to the rest of the list? If so, this would threaten two of <code>Cons</code>'s invariants: that it's immutable, and that the cached size is always correct. But there's no risk of rep exposure, because the internal list is immutable. Nobody can threaten the rep invariant of <code>Cons</code>.</p>
</div>
</div>
<h2 id="null_vs_empty">Null vs. empty</h2>
<div data-outline="null_vs_empty">
<p>It might be tempting to get rid of the <code>Empty</code> class and just use <code>null</code> instead. Resist that temptation.</p>
<p>Using an object, rather than a null reference, to signal the base case or endpoint of a data structure is an example of a design pattern called <em>sentinel objects</em>. The enormous advantage that a sentinel object provides is that it acts like an object in the datatype, so you can call methods on it. So we can call the <code>size()</code> method even on an empty list. If empty lists were represented by <code>null</code>, then we wouldn't be able to do that, and as a consequence our code would be full of tests like:</p><pre><code class="language-java hljs"><span class="hljs-keyword">if</span> (lst != <span class="hljs-keyword">null</span>) n = lst.size();</code></pre>
<p>which clutter the code, obscure its meaning, and are easy to forget. Better the much simpler</p><pre><code class="language-java hljs">n = lst.size();</code></pre>
<p>which will always work, including when an empty <code>lst</code> refers to an <code>Empty</code> object.</p>
<p>Keep <code>null</code>s out of your data structures, and your life will be happier.</p>
</div>
<h2 id="declared_type_vs_actual_type">Declared type vs. actual type</h2>
<div data-outline="declared_type_vs_actual_type">
<p>Now that we're using interfaces and classes, it's worth taking a moment to reinforce an important point about how Java's type-checking works. In fact every statically-checked object-oriented language works this way.</p>
<p>There are two worlds in type checking: <strong>compile time</strong> before the program runs, and run time when the program is executing.</p>
<p>At compile time, every variable has a <strong>declared type</strong>, stated in its declaration. The compiler uses the declared types of variables (and method return values) to deduce declared types for every expression in the program.</p>
<p>At run time, every object has an <strong>actual type</strong>, imbued in it by the constructor that created the object. For example, <code>new String()</code> makes an object whose actual type is <code>String</code>.
<code>new Empty()</code> makes an object whose actual type is <code>Empty</code>.
<code>new ImList()</code> is forbidden by Java, because <code>ImList</code> is an interface — it has no object values of its own, and no constructors.</p>
</div>
</div>
</div>
</div>
</div>
<div class="xblock xblock-public_view xblock-public_view-vertical" data-has-score="False" data-runtime-class="LmsRuntime" data-graded="True" data-request-token="3f7f1aefe9a311efbd7412d4917dea95" data-runtime-version="1" data-block-type="vertical" data-course-id="course-v1:MITx+6.005.2x+1T2017" data-init="VerticalStudentView" data-usage-id="block-v1:MITx+6.005.2x+1T2017+type@vertical+block@vertical_Questions_23e4cf8891de">
<h2 class="hd hd-2 unit-title">Questions</h2>
<div class="vert-mod">
<div class="vert vert-0" data-id="block-v1:MITx+6.005.2x+1T2017+type@html+block@Declared_vs._actual_types">
<div class="xblock xblock-public_view xblock-public_view-html xmodule_display xmodule_HtmlBlock" data-has-score="False" data-runtime-class="LmsRuntime" data-graded="True" data-request-token="3f7f1aefe9a311efbd7412d4917dea95" data-runtime-version="1" data-block-type="html" data-course-id="course-v1:MITx+6.005.2x+1T2017" data-init="XBlockToXModuleShim" data-usage-id="block-v1:MITx+6.005.2x+1T2017+type@html+block@Declared_vs._actual_types">
<script type="json/xblock-args" class="xblock-json-init-args">
{"xmodule-type": "HTMLModule"}
</script>
<link href="/assets/courseware/v1/b2188f0a95a7a9062748278f7d5a584f/asset-v1:MITx+6.005.2x+1T2017+type@asset+block/syntax-highlighting.css" rel="stylesheet" type="text/css" />
<script src="/assets/courseware/v1/c9cee8830885f59e75b8782f44026226/asset-v1:MITx+6.005.2x+1T2017+type@asset+block/edx-script-v1.js"></script>
</div>
</div>
<div class="vert vert-1" data-id="block-v1:MITx+6.005.2x+1T2017+type@problem+block@02-i-do-declare">
<div class="xblock xblock-public_view xblock-public_view-problem xmodule_display xmodule_ProblemBlock" data-has-score="True" data-runtime-class="LmsRuntime" data-graded="True" data-request-token="3f7f1aefe9a311efbd7412d4917dea95" data-runtime-version="1" data-block-type="problem" data-course-id="course-v1:MITx+6.005.2x+1T2017" data-init="XBlockToXModuleShim" data-usage-id="block-v1:MITx+6.005.2x+1T2017+type@problem+block@02-i-do-declare">
<script type="json/xblock-args" class="xblock-json-init-args">
{"xmodule-type": "Problem"}
</script>
<div id="problem_02-i-do-declare" class="problems-wrapper" role="group"
aria-labelledby="02-i-do-declare-problem-title"
data-problem-id="block-v1:MITx+6.005.2x+1T2017+type@problem+block@02-i-do-declare" data-url="/courses/course-v1:MITx+6.005.2x+1T2017/xblock/block-v1:MITx+6.005.2x+1T2017+type@problem+block@02-i-do-declare/handler/xmodule_handler"
data-problem-score="0"
data-problem-total-possible="4"
data-attempts-used="0"
data-content="
<h3 class="hd hd-3 problem-header" id="02-i-do-declare-problem-title" aria-describedby="block-v1:MITx+6.005.2x+1T2017+type@problem+block@02-i-do-declare-problem-progress" tabindex="-1">
I do declare
</h3>
<div class="problem-progress" id="block-v1:MITx+6.005.2x+1T2017+type@problem+block@02-i-do-declare-problem-progress"></div>
<div class="problem">
<div>
<pre>
String hello = "Hello";
List&lt;String&gt; words1 = new ArrayList&lt;&gt;();
words1.add(hello);
ImList&lt;String&gt; words2 = ImList.empty();
words2.cons(hello);
</pre>
<p>What is the declared type of variable <code>hello</code>?</p>
<div class="wrapper-problem-response" tabindex="-1" aria-label="Question 1" role="group"><div class="choicegroup capa_inputtype" id="inputtype_02-i-do-declare_2_1">
<fieldset aria-describedby="status_02-i-do-declare_2_1">
<div class="field">
<input type="radio" name="input_02-i-do-declare_2_1" id="input_02-i-do-declare_2_1_choice_0" class="field-input input-radio" value="choice_0"/><label id="02-i-do-declare_2_1-choice_0-label" for="input_02-i-do-declare_2_1_choice_0" class="response-label field-label label-inline" aria-describedby="status_02-i-do-declare_2_1"> none
</label>
</div>
<div class="field">
<input type="radio" name="input_02-i-do-declare_2_1" id="input_02-i-do-declare_2_1_choice_1" class="field-input input-radio" value="choice_1"/><label id="02-i-do-declare_2_1-choice_1-label" for="input_02-i-do-declare_2_1_choice_1" class="response-label field-label label-inline" aria-describedby="status_02-i-do-declare_2_1"> char[]
</label>
</div>
<div class="field">
<input type="radio" name="input_02-i-do-declare_2_1" id="input_02-i-do-declare_2_1_choice_2" class="field-input input-radio" value="choice_2"/><label id="02-i-do-declare_2_1-choice_2-label" for="input_02-i-do-declare_2_1_choice_2" class="response-label field-label label-inline" aria-describedby="status_02-i-do-declare_2_1"> String
</label>
</div>
<div class="field">
<input type="radio" name="input_02-i-do-declare_2_1" id="input_02-i-do-declare_2_1_choice_3" class="field-input input-radio" value="choice_3"/><label id="02-i-do-declare_2_1-choice_3-label" for="input_02-i-do-declare_2_1_choice_3" class="response-label field-label label-inline" aria-describedby="status_02-i-do-declare_2_1"> unknown, depends on rep of String
</label>
</div>
<div class="field">
<input type="radio" name="input_02-i-do-declare_2_1" id="input_02-i-do-declare_2_1_choice_4" class="field-input input-radio" value="choice_4"/><label id="02-i-do-declare_2_1-choice_4-label" for="input_02-i-do-declare_2_1_choice_4" class="response-label field-label label-inline" aria-describedby="status_02-i-do-declare_2_1"> invalid question
</label>
</div>
<span id="answer_02-i-do-declare_2_1"/>
</fieldset>
<div class="indicator-container">
<span class="status unanswered" id="status_02-i-do-declare_2_1" data-tooltip="Not yet answered.">
<span class="sr">unanswered</span><span class="status-icon" aria-hidden="true"/>
</span>
</div>
</div></div>
<p>What is the actual type of variable <code>hello</code>?</p>
<div class="wrapper-problem-response" tabindex="-1" aria-label="Question 2" role="group"><div class="choicegroup capa_inputtype" id="inputtype_02-i-do-declare_3_1">
<fieldset aria-describedby="status_02-i-do-declare_3_1">
<div class="field">
<input type="radio" name="input_02-i-do-declare_3_1" id="input_02-i-do-declare_3_1_choice_0" class="field-input input-radio" value="choice_0"/><label id="02-i-do-declare_3_1-choice_0-label" for="input_02-i-do-declare_3_1_choice_0" class="response-label field-label label-inline" aria-describedby="status_02-i-do-declare_3_1"> none
</label>
</div>
<div class="field">
<input type="radio" name="input_02-i-do-declare_3_1" id="input_02-i-do-declare_3_1_choice_1" class="field-input input-radio" value="choice_1"/><label id="02-i-do-declare_3_1-choice_1-label" for="input_02-i-do-declare_3_1_choice_1" class="response-label field-label label-inline" aria-describedby="status_02-i-do-declare_3_1"> char[]
</label>
</div>
<div class="field">
<input type="radio" name="input_02-i-do-declare_3_1" id="input_02-i-do-declare_3_1_choice_2" class="field-input input-radio" value="choice_2"/><label id="02-i-do-declare_3_1-choice_2-label" for="input_02-i-do-declare_3_1_choice_2" class="response-label field-label label-inline" aria-describedby="status_02-i-do-declare_3_1"> String
</label>
</div>
<div class="field">
<input type="radio" name="input_02-i-do-declare_3_1" id="input_02-i-do-declare_3_1_choice_3" class="field-input input-radio" value="choice_3"/><label id="02-i-do-declare_3_1-choice_3-label" for="input_02-i-do-declare_3_1_choice_3" class="response-label field-label label-inline" aria-describedby="status_02-i-do-declare_3_1"> unknown, depends on rep of String
</label>
</div>
<div class="field">
<input type="radio" name="input_02-i-do-declare_3_1" id="input_02-i-do-declare_3_1_choice_4" class="field-input input-radio" value="choice_4"/><label id="02-i-do-declare_3_1-choice_4-label" for="input_02-i-do-declare_3_1_choice_4" class="response-label field-label label-inline" aria-describedby="status_02-i-do-declare_3_1"> invalid question
</label>
</div>
<span id="answer_02-i-do-declare_3_1"/>
</fieldset>
<div class="indicator-container">
<span class="status unanswered" id="status_02-i-do-declare_3_1" data-tooltip="Not yet answered.">
<span class="sr">unanswered</span><span class="status-icon" aria-hidden="true"/>
</span>
</div>
</div></div>
<p>What is the declared type of the object <code>hello</code> refers to?</p>
<div class="wrapper-problem-response" tabindex="-1" aria-label="Question 3" role="group"><div class="choicegroup capa_inputtype" id="inputtype_02-i-do-declare_4_1">
<fieldset aria-describedby="status_02-i-do-declare_4_1">
<div class="field">
<input type="radio" name="input_02-i-do-declare_4_1" id="input_02-i-do-declare_4_1_choice_0" class="field-input input-radio" value="choice_0"/><label id="02-i-do-declare_4_1-choice_0-label" for="input_02-i-do-declare_4_1_choice_0" class="response-label field-label label-inline" aria-describedby="status_02-i-do-declare_4_1"> none
</label>
</div>
<div class="field">
<input type="radio" name="input_02-i-do-declare_4_1" id="input_02-i-do-declare_4_1_choice_1" class="field-input input-radio" value="choice_1"/><label id="02-i-do-declare_4_1-choice_1-label" for="input_02-i-do-declare_4_1_choice_1" class="response-label field-label label-inline" aria-describedby="status_02-i-do-declare_4_1"> char[]
</label>
</div>
<div class="field">
<input type="radio" name="input_02-i-do-declare_4_1" id="input_02-i-do-declare_4_1_choice_2" class="field-input input-radio" value="choice_2"/><label id="02-i-do-declare_4_1-choice_2-label" for="input_02-i-do-declare_4_1_choice_2" class="response-label field-label label-inline" aria-describedby="status_02-i-do-declare_4_1"> String
</label>
</div>
<div class="field">
<input type="radio" name="input_02-i-do-declare_4_1" id="input_02-i-do-declare_4_1_choice_3" class="field-input input-radio" value="choice_3"/><label id="02-i-do-declare_4_1-choice_3-label" for="input_02-i-do-declare_4_1_choice_3" class="response-label field-label label-inline" aria-describedby="status_02-i-do-declare_4_1"> unknown, depends on rep of String
</label>
</div>
<div class="field">
<input type="radio" name="input_02-i-do-declare_4_1" id="input_02-i-do-declare_4_1_choice_4" class="field-input input-radio" value="choice_4"/><label id="02-i-do-declare_4_1-choice_4-label" for="input_02-i-do-declare_4_1_choice_4" class="response-label field-label label-inline" aria-describedby="status_02-i-do-declare_4_1"> invalid question
</label>
</div>
<span id="answer_02-i-do-declare_4_1"/>
</fieldset>
<div class="indicator-container">
<span class="status unanswered" id="status_02-i-do-declare_4_1" data-tooltip="Not yet answered.">
<span class="sr">unanswered</span><span class="status-icon" aria-hidden="true"/>
</span>
</div>
</div></div>
<p>What is the actual type of the object <code>hello</code> refers to?</p>
<div class="wrapper-problem-response" tabindex="-1" aria-label="Question 4" role="group"><div class="choicegroup capa_inputtype" id="inputtype_02-i-do-declare_5_1">
<fieldset aria-describedby="status_02-i-do-declare_5_1">
<div class="field">
<input type="radio" name="input_02-i-do-declare_5_1" id="input_02-i-do-declare_5_1_choice_0" class="field-input input-radio" value="choice_0"/><label id="02-i-do-declare_5_1-choice_0-label" for="input_02-i-do-declare_5_1_choice_0" class="response-label field-label label-inline" aria-describedby="status_02-i-do-declare_5_1"> none
</label>
</div>
<div class="field">
<input type="radio" name="input_02-i-do-declare_5_1" id="input_02-i-do-declare_5_1_choice_1" class="field-input input-radio" value="choice_1"/><label id="02-i-do-declare_5_1-choice_1-label" for="input_02-i-do-declare_5_1_choice_1" class="response-label field-label label-inline" aria-describedby="status_02-i-do-declare_5_1"> char[]
</label>
</div>
<div class="field">
<input type="radio" name="input_02-i-do-declare_5_1" id="input_02-i-do-declare_5_1_choice_2" class="field-input input-radio" value="choice_2"/><label id="02-i-do-declare_5_1-choice_2-label" for="input_02-i-do-declare_5_1_choice_2" class="response-label field-label label-inline" aria-describedby="status_02-i-do-declare_5_1"> String
</label>
</div>
<div class="field">
<input type="radio" name="input_02-i-do-declare_5_1" id="input_02-i-do-declare_5_1_choice_3" class="field-input input-radio" value="choice_3"/><label id="02-i-do-declare_5_1-choice_3-label" for="input_02-i-do-declare_5_1_choice_3" class="response-label field-label label-inline" aria-describedby="status_02-i-do-declare_5_1"> unknown, depends on rep of String
</label>
</div>
<div class="field">
<input type="radio" name="input_02-i-do-declare_5_1" id="input_02-i-do-declare_5_1_choice_4" class="field-input input-radio" value="choice_4"/><label id="02-i-do-declare_5_1-choice_4-label" for="input_02-i-do-declare_5_1_choice_4" class="response-label field-label label-inline" aria-describedby="status_02-i-do-declare_5_1"> invalid question
</label>
</div>
<span id="answer_02-i-do-declare_5_1"/>
</fieldset>
<div class="indicator-container">
<span class="status unanswered" id="status_02-i-do-declare_5_1" data-tooltip="Not yet answered.">
<span class="sr">unanswered</span><span class="status-icon" aria-hidden="true"/>
</span>
</div>
</div></div>
<div class="solution-span">
<span id="solution_02-i-do-declare_solution_1"/>
</div></div>
<div class="action">
<input type="hidden" name="problem_id" value="I do declare" />
<div class="submit-attempt-container">
<button type="button" class="submit btn-brand" data-submitting="Submitting" data-value="Submit" data-should-enable-submit-button="True" aria-describedby="submission_feedback_02-i-do-declare" >
<span class="submit-label">Submit</span>
</button>
<div class="submission-feedback" id="submission_feedback_02-i-do-declare">
<span class="sr">Some problems have options such as save, reset, hints, or show answer. These options follow the Submit button.</span>
</div>
</div>
<div class="problem-action-buttons-wrapper">
</div>
</div>
<div class="notification warning notification-gentle-alert
is-hidden"
tabindex="-1">
<span class="icon fa fa-exclamation-circle" aria-hidden="true"></span>
<span class="notification-message" aria-describedby="02-i-do-declare-problem-title">
</span>
<div class="notification-btn-wrapper">
<button type="button" class="btn btn-default btn-small notification-btn review-btn sr">Review</button>
</div>
</div>
<div class="notification warning notification-save
is-hidden"
tabindex="-1">
<span class="icon fa fa-save" aria-hidden="true"></span>
<span class="notification-message" aria-describedby="02-i-do-declare-problem-title">None
</span>
<div class="notification-btn-wrapper">
<button type="button" class="btn btn-default btn-small notification-btn review-btn sr">Review</button>
</div>
</div>
<div class="notification general notification-show-answer
is-hidden"
tabindex="-1">
<span class="icon fa fa-info-circle" aria-hidden="true"></span>
<span class="notification-message" aria-describedby="02-i-do-declare-problem-title">Answers are displayed within the problem
</span>
<div class="notification-btn-wrapper">
<button type="button" class="btn btn-default btn-small notification-btn review-btn sr">Review</button>
</div>
</div>
</div>
"
data-graded="True">
<p class="loading-spinner">
<i class="fa fa-spinner fa-pulse fa-2x fa-fw"></i>
<span class="sr">Loading…</span>
</p>
</div>
</div>
</div>
<div class="vert vert-2" data-id="block-v1:MITx+6.005.2x+1T2017+type@problem+block@02-words-words-words">
<div class="xblock xblock-public_view xblock-public_view-problem xmodule_display xmodule_ProblemBlock" data-has-score="True" data-runtime-class="LmsRuntime" data-graded="True" data-request-token="3f7f1aefe9a311efbd7412d4917dea95" data-runtime-version="1" data-block-type="problem" data-course-id="course-v1:MITx+6.005.2x+1T2017" data-init="XBlockToXModuleShim" data-usage-id="block-v1:MITx+6.005.2x+1T2017+type@problem+block@02-words-words-words">
<script type="json/xblock-args" class="xblock-json-init-args">
{"xmodule-type": "Problem"}
</script>
<div id="problem_02-words-words-words" class="problems-wrapper" role="group"
aria-labelledby="02-words-words-words-problem-title"
data-problem-id="block-v1:MITx+6.005.2x+1T2017+type@problem+block@02-words-words-words" data-url="/courses/course-v1:MITx+6.005.2x+1T2017/xblock/block-v1:MITx+6.005.2x+1T2017+type@problem+block@02-words-words-words/handler/xmodule_handler"
data-problem-score="0"
data-problem-total-possible="4"
data-attempts-used="0"
data-content="
<h3 class="hd hd-3 problem-header" id="02-words-words-words-problem-title" aria-describedby="block-v1:MITx+6.005.2x+1T2017+type@problem+block@02-words-words-words-problem-progress" tabindex="-1">
Words, words, words
</h3>
<div class="problem-progress" id="block-v1:MITx+6.005.2x+1T2017+type@problem+block@02-words-words-words-problem-progress"></div>
<div class="problem">
<div>
<p>Same code again:</p>
<pre>
String hello = "Hello";
List&lt;String&gt; words1 = new ArrayList&lt;&gt;();
words1.add(hello);
ImList&lt;String&gt; words2 = ImList.empty();
words2.cons(hello);
</pre>
<p>This time, when we say declared/actual type of a variable, we always mean the variable itself <b>or</b> the object pointed to by that variable, whichever is appropriate.</p>
<p>What is the declared type of <code>words1</code>?</p>
<div class="wrapper-problem-response" tabindex="-1" aria-label="Question 1" role="group"><div class="choicegroup capa_inputtype" id="inputtype_02-words-words-words_2_1">
<fieldset aria-describedby="status_02-words-words-words_2_1">
<div class="field">
<input type="radio" name="input_02-words-words-words_2_1" id="input_02-words-words-words_2_1_choice_0" class="field-input input-radio" value="choice_0"/><label id="02-words-words-words_2_1-choice_0-label" for="input_02-words-words-words_2_1_choice_0" class="response-label field-label label-inline" aria-describedby="status_02-words-words-words_2_1"> String
</label>
</div>
<div class="field">
<input type="radio" name="input_02-words-words-words_2_1" id="input_02-words-words-words_2_1_choice_1" class="field-input input-radio" value="choice_1"/><label id="02-words-words-words_2_1-choice_1-label" for="input_02-words-words-words_2_1_choice_1" class="response-label field-label label-inline" aria-describedby="status_02-words-words-words_2_1"> List
</label>
</div>
<div class="field">
<input type="radio" name="input_02-words-words-words_2_1" id="input_02-words-words-words_2_1_choice_2" class="field-input input-radio" value="choice_2"/><label id="02-words-words-words_2_1-choice_2-label" for="input_02-words-words-words_2_1_choice_2" class="response-label field-label label-inline" aria-describedby="status_02-words-words-words_2_1"> ArrayList
</label>
</div>
<div class="field">
<input type="radio" name="input_02-words-words-words_2_1" id="input_02-words-words-words_2_1_choice_3" class="field-input input-radio" value="choice_3"/><label id="02-words-words-words_2_1-choice_3-label" for="input_02-words-words-words_2_1_choice_3" class="response-label field-label label-inline" aria-describedby="status_02-words-words-words_2_1"> ImList
</label>
</div>
<div class="field">
<input type="radio" name="input_02-words-words-words_2_1" id="input_02-words-words-words_2_1_choice_4" class="field-input input-radio" value="choice_4"/><label id="02-words-words-words_2_1-choice_4-label" for="input_02-words-words-words_2_1_choice_4" class="response-label field-label label-inline" aria-describedby="status_02-words-words-words_2_1"> Empty
</label>
</div>
<div class="field">
<input type="radio" name="input_02-words-words-words_2_1" id="input_02-words-words-words_2_1_choice_5" class="field-input input-radio" value="choice_5"/><label id="02-words-words-words_2_1-choice_5-label" for="input_02-words-words-words_2_1_choice_5" class="response-label field-label label-inline" aria-describedby="status_02-words-words-words_2_1"> Cons
</label>
</div>
<span id="answer_02-words-words-words_2_1"/>
</fieldset>
<div class="indicator-container">
<span class="status unanswered" id="status_02-words-words-words_2_1" data-tooltip="Not yet answered.">
<span class="sr">unanswered</span><span class="status-icon" aria-hidden="true"/>
</span>
</div>
</div></div>
<p>What is the actual type of <code>words1</code>?</p>
<div class="wrapper-problem-response" tabindex="-1" aria-label="Question 2" role="group"><div class="choicegroup capa_inputtype" id="inputtype_02-words-words-words_3_1">
<fieldset aria-describedby="status_02-words-words-words_3_1">
<div class="field">
<input type="radio" name="input_02-words-words-words_3_1" id="input_02-words-words-words_3_1_choice_0" class="field-input input-radio" value="choice_0"/><label id="02-words-words-words_3_1-choice_0-label" for="input_02-words-words-words_3_1_choice_0" class="response-label field-label label-inline" aria-describedby="status_02-words-words-words_3_1"> String
</label>
</div>
<div class="field">
<input type="radio" name="input_02-words-words-words_3_1" id="input_02-words-words-words_3_1_choice_1" class="field-input input-radio" value="choice_1"/><label id="02-words-words-words_3_1-choice_1-label" for="input_02-words-words-words_3_1_choice_1" class="response-label field-label label-inline" aria-describedby="status_02-words-words-words_3_1"> List
</label>
</div>
<div class="field">
<input type="radio" name="input_02-words-words-words_3_1" id="input_02-words-words-words_3_1_choice_2" class="field-input input-radio" value="choice_2"/><label id="02-words-words-words_3_1-choice_2-label" for="input_02-words-words-words_3_1_choice_2" class="response-label field-label label-inline" aria-describedby="status_02-words-words-words_3_1"> ArrayList
</label>
</div>
<div class="field">
<input type="radio" name="input_02-words-words-words_3_1" id="input_02-words-words-words_3_1_choice_3" class="field-input input-radio" value="choice_3"/><label id="02-words-words-words_3_1-choice_3-label" for="input_02-words-words-words_3_1_choice_3" class="response-label field-label label-inline" aria-describedby="status_02-words-words-words_3_1"> ImList
</label>
</div>
<div class="field">
<input type="radio" name="input_02-words-words-words_3_1" id="input_02-words-words-words_3_1_choice_4" class="field-input input-radio" value="choice_4"/><label id="02-words-words-words_3_1-choice_4-label" for="input_02-words-words-words_3_1_choice_4" class="response-label field-label label-inline" aria-describedby="status_02-words-words-words_3_1"> Empty
</label>
</div>
<div class="field">
<input type="radio" name="input_02-words-words-words_3_1" id="input_02-words-words-words_3_1_choice_5" class="field-input input-radio" value="choice_5"/><label id="02-words-words-words_3_1-choice_5-label" for="input_02-words-words-words_3_1_choice_5" class="response-label field-label label-inline" aria-describedby="status_02-words-words-words_3_1"> Cons
</label>
</div>
<span id="answer_02-words-words-words_3_1"/>
</fieldset>
<div class="indicator-container">
<span class="status unanswered" id="status_02-words-words-words_3_1" data-tooltip="Not yet answered.">
<span class="sr">unanswered</span><span class="status-icon" aria-hidden="true"/>
</span>
</div>
</div></div>
<p>What is the declared type of <code>words2</code>?</p>
<div class="wrapper-problem-response" tabindex="-1" aria-label="Question 3" role="group"><div class="choicegroup capa_inputtype" id="inputtype_02-words-words-words_4_1">
<fieldset aria-describedby="status_02-words-words-words_4_1">
<div class="field">
<input type="radio" name="input_02-words-words-words_4_1" id="input_02-words-words-words_4_1_choice_0" class="field-input input-radio" value="choice_0"/><label id="02-words-words-words_4_1-choice_0-label" for="input_02-words-words-words_4_1_choice_0" class="response-label field-label label-inline" aria-describedby="status_02-words-words-words_4_1"> String
</label>
</div>
<div class="field">
<input type="radio" name="input_02-words-words-words_4_1" id="input_02-words-words-words_4_1_choice_1" class="field-input input-radio" value="choice_1"/><label id="02-words-words-words_4_1-choice_1-label" for="input_02-words-words-words_4_1_choice_1" class="response-label field-label label-inline" aria-describedby="status_02-words-words-words_4_1"> List
</label>
</div>
<div class="field">
<input type="radio" name="input_02-words-words-words_4_1" id="input_02-words-words-words_4_1_choice_2" class="field-input input-radio" value="choice_2"/><label id="02-words-words-words_4_1-choice_2-label" for="input_02-words-words-words_4_1_choice_2" class="response-label field-label label-inline" aria-describedby="status_02-words-words-words_4_1"> ArrayList
</label>
</div>
<div class="field">
<input type="radio" name="input_02-words-words-words_4_1" id="input_02-words-words-words_4_1_choice_3" class="field-input input-radio" value="choice_3"/><label id="02-words-words-words_4_1-choice_3-label" for="input_02-words-words-words_4_1_choice_3" class="response-label field-label label-inline" aria-describedby="status_02-words-words-words_4_1"> ImList
</label>
</div>
<div class="field">
<input type="radio" name="input_02-words-words-words_4_1" id="input_02-words-words-words_4_1_choice_4" class="field-input input-radio" value="choice_4"/><label id="02-words-words-words_4_1-choice_4-label" for="input_02-words-words-words_4_1_choice_4" class="response-label field-label label-inline" aria-describedby="status_02-words-words-words_4_1"> Empty
</label>
</div>
<div class="field">
<input type="radio" name="input_02-words-words-words_4_1" id="input_02-words-words-words_4_1_choice_5" class="field-input input-radio" value="choice_5"/><label id="02-words-words-words_4_1-choice_5-label" for="input_02-words-words-words_4_1_choice_5" class="response-label field-label label-inline" aria-describedby="status_02-words-words-words_4_1"> Cons
</label>
</div>
<span id="answer_02-words-words-words_4_1"/>
</fieldset>
<div class="indicator-container">
<span class="status unanswered" id="status_02-words-words-words_4_1" data-tooltip="Not yet answered.">
<span class="sr">unanswered</span><span class="status-icon" aria-hidden="true"/>
</span>
</div>
</div></div>
<p>What is the actual type of <code>words2</code>?</p>
<div class="wrapper-problem-response" tabindex="-1" aria-label="Question 4" role="group"><div class="choicegroup capa_inputtype" id="inputtype_02-words-words-words_5_1">
<fieldset aria-describedby="status_02-words-words-words_5_1">
<div class="field">
<input type="radio" name="input_02-words-words-words_5_1" id="input_02-words-words-words_5_1_choice_0" class="field-input input-radio" value="choice_0"/><label id="02-words-words-words_5_1-choice_0-label" for="input_02-words-words-words_5_1_choice_0" class="response-label field-label label-inline" aria-describedby="status_02-words-words-words_5_1"> String
</label>
</div>
<div class="field">
<input type="radio" name="input_02-words-words-words_5_1" id="input_02-words-words-words_5_1_choice_1" class="field-input input-radio" value="choice_1"/><label id="02-words-words-words_5_1-choice_1-label" for="input_02-words-words-words_5_1_choice_1" class="response-label field-label label-inline" aria-describedby="status_02-words-words-words_5_1"> List
</label>
</div>
<div class="field">
<input type="radio" name="input_02-words-words-words_5_1" id="input_02-words-words-words_5_1_choice_2" class="field-input input-radio" value="choice_2"/><label id="02-words-words-words_5_1-choice_2-label" for="input_02-words-words-words_5_1_choice_2" class="response-label field-label label-inline" aria-describedby="status_02-words-words-words_5_1"> ArrayList
</label>
</div>
<div class="field">
<input type="radio" name="input_02-words-words-words_5_1" id="input_02-words-words-words_5_1_choice_3" class="field-input input-radio" value="choice_3"/><label id="02-words-words-words_5_1-choice_3-label" for="input_02-words-words-words_5_1_choice_3" class="response-label field-label label-inline" aria-describedby="status_02-words-words-words_5_1"> ImList
</label>
</div>
<div class="field">
<input type="radio" name="input_02-words-words-words_5_1" id="input_02-words-words-words_5_1_choice_4" class="field-input input-radio" value="choice_4"/><label id="02-words-words-words_5_1-choice_4-label" for="input_02-words-words-words_5_1_choice_4" class="response-label field-label label-inline" aria-describedby="status_02-words-words-words_5_1"> Empty
</label>
</div>
<div class="field">
<input type="radio" name="input_02-words-words-words_5_1" id="input_02-words-words-words_5_1_choice_5" class="field-input input-radio" value="choice_5"/><label id="02-words-words-words_5_1-choice_5-label" for="input_02-words-words-words_5_1_choice_5" class="response-label field-label label-inline" aria-describedby="status_02-words-words-words_5_1"> Cons
</label>
</div>
<span id="answer_02-words-words-words_5_1"/>
</fieldset>
<div class="indicator-container">
<span class="status unanswered" id="status_02-words-words-words_5_1" data-tooltip="Not yet answered.">
<span class="sr">unanswered</span><span class="status-icon" aria-hidden="true"/>
</span>
</div>
</div></div>
<div class="solution-span">
<span id="solution_02-words-words-words_solution_1"/>
</div></div>
<div class="action">
<input type="hidden" name="problem_id" value="Words, words, words" />
<div class="submit-attempt-container">
<button type="button" class="submit btn-brand" data-submitting="Submitting" data-value="Submit" data-should-enable-submit-button="True" aria-describedby="submission_feedback_02-words-words-words" >
<span class="submit-label">Submit</span>
</button>
<div class="submission-feedback" id="submission_feedback_02-words-words-words">
<span class="sr">Some problems have options such as save, reset, hints, or show answer. These options follow the Submit button.</span>
</div>
</div>
<div class="problem-action-buttons-wrapper">
</div>
</div>
<div class="notification warning notification-gentle-alert
is-hidden"
tabindex="-1">
<span class="icon fa fa-exclamation-circle" aria-hidden="true"></span>
<span class="notification-message" aria-describedby="02-words-words-words-problem-title">
</span>
<div class="notification-btn-wrapper">
<button type="button" class="btn btn-default btn-small notification-btn review-btn sr">Review</button>
</div>
</div>
<div class="notification warning notification-save
is-hidden"
tabindex="-1">
<span class="icon fa fa-save" aria-hidden="true"></span>
<span class="notification-message" aria-describedby="02-words-words-words-problem-title">None
</span>
<div class="notification-btn-wrapper">
<button type="button" class="btn btn-default btn-small notification-btn review-btn sr">Review</button>
</div>
</div>
<div class="notification general notification-show-answer
is-hidden"
tabindex="-1">
<span class="icon fa fa-info-circle" aria-hidden="true"></span>
<span class="notification-message" aria-describedby="02-words-words-words-problem-title">Answers are displayed within the problem
</span>
<div class="notification-btn-wrapper">
<button type="button" class="btn btn-default btn-small notification-btn review-btn sr">Review</button>
</div>
</div>
</div>
"
data-graded="True">
<p class="loading-spinner">
<i class="fa fa-spinner fa-pulse fa-2x fa-fw"></i>
<span class="sr">Loading…</span>
</p>
</div>
</div>
</div>
</div>
</div>
<div class="xblock xblock-public_view xblock-public_view-vertical" data-has-score="False" data-runtime-class="LmsRuntime" data-graded="True" data-request-token="3f7f1aefe9a311efbd7412d4917dea95" data-runtime-version="1" data-block-type="vertical" data-course-id="course-v1:MITx+6.005.2x+1T2017" data-init="VerticalStudentView" data-usage-id="block-v1:MITx+6.005.2x+1T2017+type@vertical+block@vertical-boolean-formulas">
<h2 class="hd hd-2 unit-title">Another example: Boolean formulas</h2>
<div class="vert-mod">
<div class="vert vert-0" data-id="block-v1:MITx+6.005.2x+1T2017+type@html+block@html_b77041deffbd">
<div class="xblock xblock-public_view xblock-public_view-html xmodule_display xmodule_HtmlBlock" data-has-score="False" data-runtime-class="LmsRuntime" data-graded="True" data-request-token="3f7f1aefe9a311efbd7412d4917dea95" data-runtime-version="1" data-block-type="html" data-course-id="course-v1:MITx+6.005.2x+1T2017" data-init="XBlockToXModuleShim" data-usage-id="block-v1:MITx+6.005.2x+1T2017+type@html+block@html_b77041deffbd">
<script type="json/xblock-args" class="xblock-json-init-args">
{"xmodule-type": "HTMLModule"}
</script>
<link href="/assets/courseware/v1/b2188f0a95a7a9062748278f7d5a584f/asset-v1:MITx+6.005.2x+1T2017+type@asset+block/syntax-highlighting.css" rel="stylesheet" type="text/css" />
<h2 id="another_example_boolean_formulas">Another example: Boolean formulas</h2>
<div data-outline="another_example_boolean_formulas">
<p>Another useful sort of recursive datatype in computer science is for Boolean formulas. For instance, here's a formula of propositional logic:</p>
<blockquote>
<p>(P <a href="https://en.wikipedia.org/wiki/Logical_disjunction">∨</a> Q) <a href="https://en.wikipedia.org/wiki/Logical_conjunction">∧</a> (<a href="https://en.wikipedia.org/wiki/Logical_negation">¬</a>P <a href="https://en.wikipedia.org/wiki/Logical_disjunction">∨</a> R)</p>
</blockquote>
<p>which means “either P or Q is true, <em>and</em> either P is false or R is true.”</p>
<p>We can give a datatype definition suitable for representing all formulas of propositional logic.</p><pre><code class="hljs php">Formula = Variable(name:String)
+ Not(formula:Formula)
+ <span class="hljs-keyword">And</span>(left:Formula, right:Formula)
+ <span class="hljs-keyword">Or</span>(left:Formula, right:Formula)
</code></pre>
<p><em>(P ∨ Q) ∧ (¬P ∨ R)</em> would be</p><pre><code class="hljs php"><span class="hljs-keyword">And</span>( <span class="hljs-keyword">Or</span>(Variable(<span class="hljs-string">"P"</span>), Variable(<span class="hljs-string">"Q"</span>)),
<span class="hljs-keyword">Or</span>(Not(Variable(<span class="hljs-string">"P"</span>)), Variable(<span class="hljs-string">"R"</span>)) )
</code></pre>
<p>A key operation for Boolean formulas is testing whether they are <em>satisfiable</em>, that is, whether some assignment of true/false values to the variables leads the formula to evaluate to true. There is a simple but slow algorithm for checking satisfiability:</p>
<ol>
<li>
<p>Extract the set of variables from the formula.</p>
</li>
<li>
<p>Try all possible assignments of true/false values to those variables.
<br> We can represent an assignment with an <code>Environment</code>: a list of variables and their values. We could use <code>ImList</code> to implement the <code>Environment</code>, or develop an immutable map type.</p>
</li>
<li>
<p>Evaluate the formula for each environment.
<br> For this, we'll define <strong>evaluate : Formula × Environment → Boolean</strong>.</p>
</li>
<li>
<p>Return the first environment in which the formula evaluates to true.</p>
</li>
</ol>
<p>Defining these pieces and putting them together into a <strong>satisfiable : Formula → Boolean</strong> function is an exercise for another time.</p>
</div>
<h3 id="backtracking_search_with_immutability">Backtracking search with immutability</h3>
<div data-outline="backtracking_search_with_immutability">
<p>We started out this part of the reading with immutable lists, which are a representation that permits a lot of sharing between different list instances. Sharing of a particular kind, though: only the ends of lists can actually be shared. If two lists are identical at the beginning but then diverge from each other, they have to be stored separately. (Why?)
</p>
<p>It turns out that backtracking search is a great application for these lists, and here's why. A search through a space (like the space of assignments to a set of Boolean variables) generally proceeds by making one choice after another, and when a choice leads to a dead end, you backtrack.</p>
<p>Mutable data structures are typically not a good approach for backtracking. If you use a mutable <code>Map</code>, say, to keep track of the current variable bindings you're trying, then you have to undo those bindings every time you backtrack. That's error-prone and painful compared to what you do with immutable maps — when you backtrack, you just throw the map away!</p>
<p>But immutable data structures with no sharing aren't a great idea either, because the space you need to keep track of where you are (in the case of the satisfiability problem, the environment) will grow quadratically if you have to make a complete copy every time you take a new step. You need to hold on to all the previous environments on your path, in case you need to back up.</p>
<p>Immutable lists have the nice property that each step taken on the path can share all the information from the previous steps, just by adding to the front of the list. When you have to backtrack, you stop using the current step's state — but you still have references to the previous step's state.</p>
<p>Finally, a search that uses immutable data structures is immediately ready to be parallelized. You can delegate multiple processors to search multiple paths at once, without having to deal with the problem that they'll step on each other in a shared mutable data structure. We'll talk about this more when we get to concurrency.</p>
</div>
</div>
</div>
</div>
</div>
<div class="xblock xblock-public_view xblock-public_view-vertical" data-has-score="False" data-runtime-class="LmsRuntime" data-graded="True" data-request-token="3f7f1aefe9a311efbd7412d4917dea95" data-runtime-version="1" data-block-type="vertical" data-course-id="course-v1:MITx+6.005.2x+1T2017" data-init="VerticalStudentView" data-usage-id="block-v1:MITx+6.005.2x+1T2017+type@vertical+block@vertical_Questions_65d8e9a23362">
<h2 class="hd hd-2 unit-title">Questions</h2>
<div class="vert-mod">
<div class="vert vert-0" data-id="block-v1:MITx+6.005.2x+1T2017+type@html+block@Boolean_formulas">
<div class="xblock xblock-public_view xblock-public_view-html xmodule_display xmodule_HtmlBlock" data-has-score="False" data-runtime-class="LmsRuntime" data-graded="True" data-request-token="3f7f1aefe9a311efbd7412d4917dea95" data-runtime-version="1" data-block-type="html" data-course-id="course-v1:MITx+6.005.2x+1T2017" data-init="XBlockToXModuleShim" data-usage-id="block-v1:MITx+6.005.2x+1T2017+type@html+block@Boolean_formulas">
<script type="json/xblock-args" class="xblock-json-init-args">
{"xmodule-type": "HTMLModule"}
</script>
<link href="/assets/courseware/v1/b2188f0a95a7a9062748278f7d5a584f/asset-v1:MITx+6.005.2x+1T2017+type@asset+block/syntax-highlighting.css" rel="stylesheet" type="text/css" />
<script src="/assets/courseware/v1/c9cee8830885f59e75b8782f44026226/asset-v1:MITx+6.005.2x+1T2017+type@asset+block/edx-script-v1.js"></script>
</div>
</div>
<div class="vert vert-1" data-id="block-v1:MITx+6.005.2x+1T2017+type@problem+block@02-not">
<div class="xblock xblock-public_view xblock-public_view-problem xmodule_display xmodule_ProblemBlock" data-has-score="True" data-runtime-class="LmsRuntime" data-graded="True" data-request-token="3f7f1aefe9a311efbd7412d4917dea95" data-runtime-version="1" data-block-type="problem" data-course-id="course-v1:MITx+6.005.2x+1T2017" data-init="XBlockToXModuleShim" data-usage-id="block-v1:MITx+6.005.2x+1T2017+type@problem+block@02-not">
<script type="json/xblock-args" class="xblock-json-init-args">
{"xmodule-type": "Problem"}
</script>
<div id="problem_02-not" class="problems-wrapper" role="group"
aria-labelledby="02-not-problem-title"
data-problem-id="block-v1:MITx+6.005.2x+1T2017+type@problem+block@02-not" data-url="/courses/course-v1:MITx+6.005.2x+1T2017/xblock/block-v1:MITx+6.005.2x+1T2017+type@problem+block@02-not/handler/xmodule_handler"
data-problem-score="0"
data-problem-total-possible="1"
data-attempts-used="0"
data-content="
<h3 class="hd hd-3 problem-header" id="02-not-problem-title" aria-describedby="block-v1:MITx+6.005.2x+1T2017+type@problem+block@02-not-problem-progress" tabindex="-1">
Not
</h3>
<div class="problem-progress" id="block-v1:MITx+6.005.2x+1T2017+type@problem+block@02-not-problem-progress"></div>
<div class="problem">
<div>
<p>Alyssa and Ben are studying the recursive datatype for Boolean formulas.</p>
<p>Ben suggests changing the <code>Not</code> variant from <code>Not(formula:Formula)</code> to <code>Not(var:Variable)</code>. Which of these formulas should Alyssa offer as a counterexamples?</p>
<div class="wrapper-problem-response" tabindex="-1" aria-label="Question 1" role="group"><div class="choicegroup capa_inputtype" id="inputtype_02-not_2_1">
<fieldset aria-describedby="status_02-not_2_1">
<div class="field">
<input type="checkbox" name="input_02-not_2_1[]" id="input_02-not_2_1_choice_0" class="field-input input-checkbox" value="choice_0"/><label id="02-not_2_1-choice_0-label" for="input_02-not_2_1_choice_0" class="response-label field-label label-inline" aria-describedby="status_02-not_2_1"> `(P\vee Q)\wedge(\not P\vee R)`
</label>
</div>
<div class="field">
<input type="checkbox" name="input_02-not_2_1[]" id="input_02-not_2_1_choice_1" class="field-input input-checkbox" value="choice_1"/><label id="02-not_2_1-choice_1-label" for="input_02-not_2_1_choice_1" class="response-label field-label label-inline" aria-describedby="status_02-not_2_1"> `(P\vee Q)\wedge(P\vee \not R)`
</label>
</div>
<div class="field">
<input type="checkbox" name="input_02-not_2_1[]" id="input_02-not_2_1_choice_2" class="field-input input-checkbox" value="choice_2"/><label id="02-not_2_1-choice_2-label" for="input_02-not_2_1_choice_2" class="response-label field-label label-inline" aria-describedby="status_02-not_2_1"> `(P\vee Q)\wedge(\notP\vee \not R)`
</label>
</div>
<div class="field">
<input type="checkbox" name="input_02-not_2_1[]" id="input_02-not_2_1_choice_3" class="field-input input-checkbox" value="choice_3"/><label id="02-not_2_1-choice_3-label" for="input_02-not_2_1_choice_3" class="response-label field-label label-inline" aria-describedby="status_02-not_2_1"> `(P\vee Q)\wedge\not (P\vee R)`
</label>
</div>
<div class="field">
<input type="checkbox" name="input_02-not_2_1[]" id="input_02-not_2_1_choice_4" class="field-input input-checkbox" value="choice_4"/><label id="02-not_2_1-choice_4-label" for="input_02-not_2_1_choice_4" class="response-label field-label label-inline" aria-describedby="status_02-not_2_1"> `\not ((P\vee Q)\wedge(P\vee R))`
</label>
</div>
<span id="answer_02-not_2_1"/>
</fieldset>
<div class="indicator-container">
<span class="status unanswered" id="status_02-not_2_1" data-tooltip="Not yet answered.">
<span class="sr">unanswered</span><span class="status-icon" aria-hidden="true"/>
</span>
</div>
</div></div>
<div class="solution-span">
<span id="solution_02-not_solution_1"/>
</div></div>
<div class="action">
<input type="hidden" name="problem_id" value="Not" />
<div class="submit-attempt-container">
<button type="button" class="submit btn-brand" data-submitting="Submitting" data-value="Submit" data-should-enable-submit-button="True" aria-describedby="submission_feedback_02-not" >
<span class="submit-label">Submit</span>
</button>
<div class="submission-feedback" id="submission_feedback_02-not">
<span class="sr">Some problems have options such as save, reset, hints, or show answer. These options follow the Submit button.</span>
</div>
</div>
<div class="problem-action-buttons-wrapper">
</div>
</div>
<div class="notification warning notification-gentle-alert
is-hidden"
tabindex="-1">
<span class="icon fa fa-exclamation-circle" aria-hidden="true"></span>
<span class="notification-message" aria-describedby="02-not-problem-title">
</span>
<div class="notification-btn-wrapper">
<button type="button" class="btn btn-default btn-small notification-btn review-btn sr">Review</button>
</div>
</div>
<div class="notification warning notification-save
is-hidden"
tabindex="-1">
<span class="icon fa fa-save" aria-hidden="true"></span>
<span class="notification-message" aria-describedby="02-not-problem-title">None
</span>
<div class="notification-btn-wrapper">
<button type="button" class="btn btn-default btn-small notification-btn review-btn sr">Review</button>
</div>
</div>
<div class="notification general notification-show-answer
is-hidden"
tabindex="-1">
<span class="icon fa fa-info-circle" aria-hidden="true"></span>
<span class="notification-message" aria-describedby="02-not-problem-title">Answers are displayed within the problem
</span>
<div class="notification-btn-wrapper">
<button type="button" class="btn btn-default btn-small notification-btn review-btn sr">Review</button>
</div>
</div>
</div>
"
data-graded="True">
<p class="loading-spinner">
<i class="fa fa-spinner fa-pulse fa-2x fa-fw"></i>
<span class="sr">Loading…</span>
</p>
</div>
</div>
</div>
<div class="vert vert-2" data-id="block-v1:MITx+6.005.2x+1T2017+type@problem+block@02-pair">
<div class="xblock xblock-public_view xblock-public_view-problem xmodule_display xmodule_ProblemBlock" data-has-score="True" data-runtime-class="LmsRuntime" data-graded="True" data-request-token="3f7f1aefe9a311efbd7412d4917dea95" data-runtime-version="1" data-block-type="problem" data-course-id="course-v1:MITx+6.005.2x+1T2017" data-init="XBlockToXModuleShim" data-usage-id="block-v1:MITx+6.005.2x+1T2017+type@problem+block@02-pair">
<script type="json/xblock-args" class="xblock-json-init-args">
{"xmodule-type": "Problem"}
</script>
<div id="problem_02-pair" class="problems-wrapper" role="group"
aria-labelledby="02-pair-problem-title"
data-problem-id="block-v1:MITx+6.005.2x+1T2017+type@problem+block@02-pair" data-url="/courses/course-v1:MITx+6.005.2x+1T2017/xblock/block-v1:MITx+6.005.2x+1T2017+type@problem+block@02-pair/handler/xmodule_handler"
data-problem-score="0"
data-problem-total-possible="1"
data-attempts-used="0"
data-content="
<h3 class="hd hd-3 problem-header" id="02-pair-problem-title" aria-describedby="block-v1:MITx+6.005.2x+1T2017+type@problem+block@02-pair-problem-progress" tabindex="-1">
Pair
</h3>
<div class="problem-progress" id="block-v1:MITx+6.005.2x+1T2017+type@problem+block@02-pair-problem-progress"></div>
<div class="problem">
<div>
<p>When we write <code>Environment = ImList&lt;Variable x Boolean&gt;</code>, we mean that an <code>Environment</code> is implemented as an <code>ImList</code> of two-element tuples (a.k.a. pairs) where the first element is a <code>Variable</code> and the second is a <code>Boolean</code>.</p>
<p>Then we wrote statements like:</p>
<pre>
lookup(Cons((var, val), rest), x) = if var = x then val else lookup(rest, x)
</pre>
<p>which says: when we look up <em>x</em> in an <code>Environment</code> whose first pair is <em>(var, val)</em>, if <em>var</em> is <em>x</em>, return <em>val</em>, otherwise keep looking for <em>x</em> in the <code>rest</code> of the <code>Environment</code> (which is just an <code>ImList</code> of these pairs).</p>
<p>Unlike Python, Java does not have tuples. What could we do instead to store these tuples?</p>
<div class="wrapper-problem-response" tabindex="-1" aria-label="Question 1" role="group"><div class="choicegroup capa_inputtype" id="inputtype_02-pair_2_1">
<fieldset aria-describedby="status_02-pair_2_1">
<div class="field">
<input class="field-input input-checkbox" type="checkbox" name="input_02-pair_2_1[]" id="input_02-pair_2_1_choice_0" value="choice_0"/><label class="response-label field-label label-inline" for="input_02-pair_2_1_choice_0" id="02-pair_2_1-choice_0-label" aria-describedby="status_02-pair_2_1"> Environment = ImList&lt; List&lt; Variable, Boolean&gt;&gt;
</label>
</div>
<div class="field">
<input class="field-input input-checkbox" type="checkbox" name="input_02-pair_2_1[]" id="input_02-pair_2_1_choice_1" value="choice_1"/><label class="response-label field-label label-inline" for="input_02-pair_2_1_choice_1" id="02-pair_2_1-choice_1-label" aria-describedby="status_02-pair_2_1"> Environment = ImList&lt; List&lt; String, Boolean&gt;&gt;
</label>
</div>
<div class="field">
<input class="field-input input-checkbox" type="checkbox" name="input_02-pair_2_1[]" id="input_02-pair_2_1_choice_2" value="choice_2"/><label class="response-label field-label label-inline" for="input_02-pair_2_1_choice_2" id="02-pair_2_1-choice_2-label" aria-describedby="status_02-pair_2_1"> Environment = ImList&lt; List&lt; Object&gt;&gt;
</label>
</div>
<div class="field">
<input class="field-input input-checkbox" type="checkbox" name="input_02-pair_2_1[]" id="input_02-pair_2_1_choice_3" value="choice_3"/><label class="response-label field-label label-inline" for="input_02-pair_2_1_choice_3" id="02-pair_2_1-choice_3-label" aria-describedby="status_02-pair_2_1"> Environment = ImList&lt; Variable[]&gt;
</label>
</div>
<div class="field">
<input class="field-input input-checkbox" type="checkbox" name="input_02-pair_2_1[]" id="input_02-pair_2_1_choice_4" value="choice_4"/><label class="response-label field-label label-inline" for="input_02-pair_2_1_choice_4" id="02-pair_2_1-choice_4-label" aria-describedby="status_02-pair_2_1"> Environment = ImList&lt; Boolean[]&gt;
</label>
</div>
<div class="field">
<input class="field-input input-checkbox" type="checkbox" name="input_02-pair_2_1[]" id="input_02-pair_2_1_choice_5" value="choice_5"/><label class="response-label field-label label-inline" for="input_02-pair_2_1_choice_5" id="02-pair_2_1-choice_5-label" aria-describedby="status_02-pair_2_1"> Environment = ImList&lt; String[]&gt;
</label>
</div>
<div class="field">
<input class="field-input input-checkbox" type="checkbox" name="input_02-pair_2_1[]" id="input_02-pair_2_1_choice_6" value="choice_6"/><label class="response-label field-label label-inline" for="input_02-pair_2_1_choice_6" id="02-pair_2_1-choice_6-label" aria-describedby="status_02-pair_2_1"> Environment = ImList&lt; Object[]&gt;
</label>
</div>
<span id="answer_02-pair_2_1"/>
</fieldset>
<div class="indicator-container">
<span class="status unanswered" data-tooltip="Not yet answered." id="status_02-pair_2_1">
<span class="sr">unanswered</span><span class="status-icon" aria-hidden="true"/>
</span>
</div>
</div></div>
<div class="solution-span">
<span id="solution_02-pair_solution_1"/>
</div></div>
<div class="action">
<input type="hidden" name="problem_id" value="Pair" />
<div class="submit-attempt-container">
<button type="button" class="submit btn-brand" data-submitting="Submitting" data-value="Submit" data-should-enable-submit-button="True" aria-describedby="submission_feedback_02-pair" >
<span class="submit-label">Submit</span>
</button>
<div class="submission-feedback" id="submission_feedback_02-pair">
<span class="sr">Some problems have options such as save, reset, hints, or show answer. These options follow the Submit button.</span>
</div>
</div>
<div class="problem-action-buttons-wrapper">
</div>
</div>
<div class="notification warning notification-gentle-alert
is-hidden"
tabindex="-1">
<span class="icon fa fa-exclamation-circle" aria-hidden="true"></span>
<span class="notification-message" aria-describedby="02-pair-problem-title">
</span>
<div class="notification-btn-wrapper">
<button type="button" class="btn btn-default btn-small notification-btn review-btn sr">Review</button>
</div>
</div>
<div class="notification warning notification-save
is-hidden"
tabindex="-1">
<span class="icon fa fa-save" aria-hidden="true"></span>
<span class="notification-message" aria-describedby="02-pair-problem-title">None
</span>
<div class="notification-btn-wrapper">
<button type="button" class="btn btn-default btn-small notification-btn review-btn sr">Review</button>
</div>
</div>
<div class="notification general notification-show-answer
is-hidden"
tabindex="-1">
<span class="icon fa fa-info-circle" aria-hidden="true"></span>
<span class="notification-message" aria-describedby="02-pair-problem-title">Answers are displayed within the problem
</span>
<div class="notification-btn-wrapper">
<button type="button" class="btn btn-default btn-small notification-btn review-btn sr">Review</button>
</div>
</div>
</div>
"
data-graded="True">
<p class="loading-spinner">
<i class="fa fa-spinner fa-pulse fa-2x fa-fw"></i>
<span class="sr">Loading…</span>
</p>
</div>
</div>
</div>
<div class="vert vert-3" data-id="block-v1:MITx+6.005.2x+1T2017+type@problem+block@02-pair-problems">
<div class="xblock xblock-public_view xblock-public_view-problem xmodule_display xmodule_ProblemBlock" data-has-score="True" data-runtime-class="LmsRuntime" data-graded="True" data-request-token="3f7f1aefe9a311efbd7412d4917dea95" data-runtime-version="1" data-block-type="problem" data-course-id="course-v1:MITx+6.005.2x+1T2017" data-init="XBlockToXModuleShim" data-usage-id="block-v1:MITx+6.005.2x+1T2017+type@problem+block@02-pair-problems">
<script type="json/xblock-args" class="xblock-json-init-args">
{"xmodule-type": "Problem"}
</script>
<div id="problem_02-pair-problems" class="problems-wrapper" role="group"
aria-labelledby="02-pair-problems-problem-title"
data-problem-id="block-v1:MITx+6.005.2x+1T2017+type@problem+block@02-pair-problems" data-url="/courses/course-v1:MITx+6.005.2x+1T2017/xblock/block-v1:MITx+6.005.2x+1T2017+type@problem+block@02-pair-problems/handler/xmodule_handler"
data-problem-score="0"
data-problem-total-possible="1"
data-attempts-used="0"
data-content="
<h3 class="hd hd-3 problem-header" id="02-pair-problems-problem-title" aria-describedby="block-v1:MITx+6.005.2x+1T2017+type@problem+block@02-pair-problems-problem-progress" tabindex="-1">
Pair problems
</h3>
<div class="problem-progress" id="block-v1:MITx+6.005.2x+1T2017+type@problem+block@02-pair-problems-problem-progress"></div>
<div class="problem">
<div>
<p>The solutions for storing pairs in the previous question are pretty bad. What do they <em>not</em> provide?</p>
<div class="wrapper-problem-response" tabindex="-1" aria-label="Question 1" role="group"><div class="choicegroup capa_inputtype" id="inputtype_02-pair-problems_2_1">
<fieldset aria-describedby="status_02-pair-problems_2_1">
<div class="field">
<input type="checkbox" name="input_02-pair-problems_2_1[]" id="input_02-pair-problems_2_1_choice_0" class="field-input input-checkbox" value="choice_0"/><label id="02-pair-problems_2_1-choice_0-label" for="input_02-pair-problems_2_1_choice_0" class="response-label field-label label-inline" aria-describedby="status_02-pair-problems_2_1"> static checking of the types of objects in the pair
</label>
</div>
<div class="field">
<input type="checkbox" name="input_02-pair-problems_2_1[]" id="input_02-pair-problems_2_1_choice_1" class="field-input input-checkbox" value="choice_1"/><label id="02-pair-problems_2_1-choice_1-label" for="input_02-pair-problems_2_1_choice_1" class="response-label field-label label-inline" aria-describedby="status_02-pair-problems_2_1"> dynamic checking of the types of objects in the pair
</label>
</div>
<div class="field">
<input type="checkbox" name="input_02-pair-problems_2_1[]" id="input_02-pair-problems_2_1_choice_2" class="field-input input-checkbox" value="choice_2"/><label id="02-pair-problems_2_1-choice_2-label" for="input_02-pair-problems_2_1_choice_2" class="response-label field-label label-inline" aria-describedby="status_02-pair-problems_2_1"> static checking of the number of objects in the pair
</label>
</div>
<div class="field">
<input type="checkbox" name="input_02-pair-problems_2_1[]" id="input_02-pair-problems_2_1_choice_3" class="field-input input-checkbox" value="choice_3"/><label id="02-pair-problems_2_1-choice_3-label" for="input_02-pair-problems_2_1_choice_3" class="response-label field-label label-inline" aria-describedby="status_02-pair-problems_2_1"> dynamic checking of the number of objects in the pair
</label>
</div>
<div class="field">
<input type="checkbox" name="input_02-pair-problems_2_1[]" id="input_02-pair-problems_2_1_choice_4" class="field-input input-checkbox" value="choice_4"/><label id="02-pair-problems_2_1-choice_4-label" for="input_02-pair-problems_2_1_choice_4" class="response-label field-label label-inline" aria-describedby="status_02-pair-problems_2_1"> static checking that we only access valid indices in the pair
</label>
</div>
<div class="field">
<input type="checkbox" name="input_02-pair-problems_2_1[]" id="input_02-pair-problems_2_1_choice_5" class="field-input input-checkbox" value="choice_5"/><label id="02-pair-problems_2_1-choice_5-label" for="input_02-pair-problems_2_1_choice_5" class="response-label field-label label-inline" aria-describedby="status_02-pair-problems_2_1"> dynamic checking that we only access valid indices in the pair
</label>
</div>
<span id="answer_02-pair-problems_2_1"/>
</fieldset>
<div class="indicator-container">
<span class="status unanswered" id="status_02-pair-problems_2_1" data-tooltip="Not yet answered.">
<span class="sr">unanswered</span><span class="status-icon" aria-hidden="true"/>
</span>
</div>
</div></div>
<div class="solution-span">
<span id="solution_02-pair-problems_solution_1"/>
</div></div>
<div class="action">
<input type="hidden" name="problem_id" value="Pair problems" />
<div class="submit-attempt-container">
<button type="button" class="submit btn-brand" data-submitting="Submitting" data-value="Submit" data-should-enable-submit-button="True" aria-describedby="submission_feedback_02-pair-problems" >
<span class="submit-label">Submit</span>
</button>
<div class="submission-feedback" id="submission_feedback_02-pair-problems">
<span class="sr">Some problems have options such as save, reset, hints, or show answer. These options follow the Submit button.</span>
</div>
</div>
<div class="problem-action-buttons-wrapper">
</div>
</div>
<div class="notification warning notification-gentle-alert
is-hidden"
tabindex="-1">
<span class="icon fa fa-exclamation-circle" aria-hidden="true"></span>
<span class="notification-message" aria-describedby="02-pair-problems-problem-title">
</span>
<div class="notification-btn-wrapper">
<button type="button" class="btn btn-default btn-small notification-btn review-btn sr">Review</button>
</div>
</div>
<div class="notification warning notification-save
is-hidden"
tabindex="-1">
<span class="icon fa fa-save" aria-hidden="true"></span>
<span class="notification-message" aria-describedby="02-pair-problems-problem-title">None
</span>
<div class="notification-btn-wrapper">
<button type="button" class="btn btn-default btn-small notification-btn review-btn sr">Review</button>
</div>
</div>
<div class="notification general notification-show-answer
is-hidden"
tabindex="-1">
<span class="icon fa fa-info-circle" aria-hidden="true"></span>
<span class="notification-message" aria-describedby="02-pair-problems-problem-title">Answers are displayed within the problem
</span>
<div class="notification-btn-wrapper">
<button type="button" class="btn btn-default btn-small notification-btn review-btn sr">Review</button>
</div>
</div>
</div>
"
data-graded="True">
<p class="loading-spinner">
<i class="fa fa-spinner fa-pulse fa-2x fa-fw"></i>
<span class="sr">Loading…</span>
</p>
</div>
</div>
</div>
<div class="vert vert-4" data-id="block-v1:MITx+6.005.2x+1T2017+type@problem+block@02-pair-progress">
<div class="xblock xblock-public_view xblock-public_view-problem xmodule_display xmodule_ProblemBlock" data-has-score="True" data-runtime-class="LmsRuntime" data-graded="True" data-request-token="3f7f1aefe9a311efbd7412d4917dea95" data-runtime-version="1" data-block-type="problem" data-course-id="course-v1:MITx+6.005.2x+1T2017" data-init="XBlockToXModuleShim" data-usage-id="block-v1:MITx+6.005.2x+1T2017+type@problem+block@02-pair-progress">
<script type="json/xblock-args" class="xblock-json-init-args">
{"xmodule-type": "Problem"}
</script>
<div id="problem_02-pair-progress" class="problems-wrapper" role="group"
aria-labelledby="02-pair-progress-problem-title"
data-problem-id="block-v1:MITx+6.005.2x+1T2017+type@problem+block@02-pair-progress" data-url="/courses/course-v1:MITx+6.005.2x+1T2017/xblock/block-v1:MITx+6.005.2x+1T2017+type@problem+block@02-pair-progress/handler/xmodule_handler"
data-problem-score="0"
data-problem-total-possible="4"
data-attempts-used="0"
data-content="
<h3 class="hd hd-3 problem-header" id="02-pair-progress-problem-title" aria-describedby="block-v1:MITx+6.005.2x+1T2017+type@problem+block@02-pair-progress-problem-progress" tabindex="-1">
Pair progress
</h3>
<div class="problem-progress" id="block-v1:MITx+6.005.2x+1T2017+type@problem+block@02-pair-progress-problem-progress"></div>
<div class="problem">
<div>
<p>Let's define an abstract datatype <code>Pair&lt;T, U&gt;</code> to store pairs of values. This is another generic type: the first element of the pair is of some unknown type we'll call <code>T</code>, and the second is of unknown type <code>U</code>. For Boolean formula environments, we will use <code>Pair&lt;Variable, Boolean&gt;</code>.</p>
<p>This ADT will be characterized by two operations: <code>first</code>, to retrieve the first element in the pair, and <code>second</code>, to retrieve the second element.</p>
<p>To work on the concrete implementation, we'll write a datatype definition:</p>
<pre>
Pair&lt;T, U&gt; = Pair(first:T, second:U)
</pre>
<p>Pair has only one concrete variant.</p>
<p>Fill in the blanks to define operations:</p>
<pre>
first : FIRST_INPUTS -&gt; FIRST_OUTPUTS
second : SECOND_INPUTS -&gt; SECOND_OUTPUTS
</pre>
<p>FIRST_INPUTS</p>
<div class="wrapper-problem-response" tabindex="-1" aria-label="Question 1" role="group"><div class="choicegroup capa_inputtype" id="inputtype_02-pair-progress_2_1">
<fieldset aria-describedby="status_02-pair-progress_2_1">
<div class="field">
<input class="field-input input-radio" type="radio" name="input_02-pair-progress_2_1" id="input_02-pair-progress_2_1_choice_0" value="choice_0"/><label class="response-label field-label label-inline" for="input_02-pair-progress_2_1_choice_0" id="02-pair-progress_2_1-choice_0-label" aria-describedby="status_02-pair-progress_2_1"> Pair&lt; T, U&gt;
</label>
</div>
<div class="field">
<input class="field-input input-radio" type="radio" name="input_02-pair-progress_2_1" id="input_02-pair-progress_2_1_choice_1" value="choice_1"/><label class="response-label field-label label-inline" for="input_02-pair-progress_2_1_choice_1" id="02-pair-progress_2_1-choice_1-label" aria-describedby="status_02-pair-progress_2_1"> T
</label>
</div>
<div class="field">
<input class="field-input input-radio" type="radio" name="input_02-pair-progress_2_1" id="input_02-pair-progress_2_1_choice_2" value="choice_2"/><label class="response-label field-label label-inline" for="input_02-pair-progress_2_1_choice_2" id="02-pair-progress_2_1-choice_2-label" aria-describedby="status_02-pair-progress_2_1"> U
</label>
</div>
<div class="field">
<input class="field-input input-radio" type="radio" name="input_02-pair-progress_2_1" id="input_02-pair-progress_2_1_choice_3" value="choice_3"/><label class="response-label field-label label-inline" for="input_02-pair-progress_2_1_choice_3" id="02-pair-progress_2_1-choice_3-label" aria-describedby="status_02-pair-progress_2_1"> first
</label>
</div>
<div class="field">
<input class="field-input input-radio" type="radio" name="input_02-pair-progress_2_1" id="input_02-pair-progress_2_1_choice_4" value="choice_4"/><label class="response-label field-label label-inline" for="input_02-pair-progress_2_1_choice_4" id="02-pair-progress_2_1-choice_4-label" aria-describedby="status_02-pair-progress_2_1"> t
</label>
</div>
<div class="field">
<input class="field-input input-radio" type="radio" name="input_02-pair-progress_2_1" id="input_02-pair-progress_2_1_choice_5" value="choice_5"/><label class="response-label field-label label-inline" for="input_02-pair-progress_2_1_choice_5" id="02-pair-progress_2_1-choice_5-label" aria-describedby="status_02-pair-progress_2_1"> u
</label>
</div>
<span id="answer_02-pair-progress_2_1"/>
</fieldset>
<div class="indicator-container">
<span class="status unanswered" data-tooltip="Not yet answered." id="status_02-pair-progress_2_1">
<span class="sr">unanswered</span><span class="status-icon" aria-hidden="true"/>
</span>
</div>
</div></div>
<p>FIRST_OUTPUTS</p>
<div class="wrapper-problem-response" tabindex="-1" aria-label="Question 2" role="group"><div class="choicegroup capa_inputtype" id="inputtype_02-pair-progress_3_1">
<fieldset aria-describedby="status_02-pair-progress_3_1">
<div class="field">
<input class="field-input input-radio" type="radio" name="input_02-pair-progress_3_1" id="input_02-pair-progress_3_1_choice_0" value="choice_0"/><label class="response-label field-label label-inline" for="input_02-pair-progress_3_1_choice_0" id="02-pair-progress_3_1-choice_0-label" aria-describedby="status_02-pair-progress_3_1"> Pair&lt; T, U&gt;
</label>
</div>
<div class="field">
<input class="field-input input-radio" type="radio" name="input_02-pair-progress_3_1" id="input_02-pair-progress_3_1_choice_1" value="choice_1"/><label class="response-label field-label label-inline" for="input_02-pair-progress_3_1_choice_1" id="02-pair-progress_3_1-choice_1-label" aria-describedby="status_02-pair-progress_3_1"> T
</label>
</div>
<div class="field">
<input class="field-input input-radio" type="radio" name="input_02-pair-progress_3_1" id="input_02-pair-progress_3_1_choice_2" value="choice_2"/><label class="response-label field-label label-inline" for="input_02-pair-progress_3_1_choice_2" id="02-pair-progress_3_1-choice_2-label" aria-describedby="status_02-pair-progress_3_1"> U
</label>
</div>
<div class="field">
<input class="field-input input-radio" type="radio" name="input_02-pair-progress_3_1" id="input_02-pair-progress_3_1_choice_3" value="choice_3"/><label class="response-label field-label label-inline" for="input_02-pair-progress_3_1_choice_3" id="02-pair-progress_3_1-choice_3-label" aria-describedby="status_02-pair-progress_3_1"> first
</label>
</div>
<div class="field">
<input class="field-input input-radio" type="radio" name="input_02-pair-progress_3_1" id="input_02-pair-progress_3_1_choice_4" value="choice_4"/><label class="response-label field-label label-inline" for="input_02-pair-progress_3_1_choice_4" id="02-pair-progress_3_1-choice_4-label" aria-describedby="status_02-pair-progress_3_1"> t
</label>
</div>
<div class="field">
<input class="field-input input-radio" type="radio" name="input_02-pair-progress_3_1" id="input_02-pair-progress_3_1_choice_5" value="choice_5"/><label class="response-label field-label label-inline" for="input_02-pair-progress_3_1_choice_5" id="02-pair-progress_3_1-choice_5-label" aria-describedby="status_02-pair-progress_3_1"> u
</label>
</div>
<span id="answer_02-pair-progress_3_1"/>
</fieldset>
<div class="indicator-container">
<span class="status unanswered" data-tooltip="Not yet answered." id="status_02-pair-progress_3_1">
<span class="sr">unanswered</span><span class="status-icon" aria-hidden="true"/>
</span>
</div>
</div></div>
<p>SECOND_INPUTS</p>
<div class="wrapper-problem-response" tabindex="-1" aria-label="Question 3" role="group"><div class="choicegroup capa_inputtype" id="inputtype_02-pair-progress_4_1">
<fieldset aria-describedby="status_02-pair-progress_4_1">
<div class="field">
<input class="field-input input-radio" type="radio" name="input_02-pair-progress_4_1" id="input_02-pair-progress_4_1_choice_0" value="choice_0"/><label class="response-label field-label label-inline" for="input_02-pair-progress_4_1_choice_0" id="02-pair-progress_4_1-choice_0-label" aria-describedby="status_02-pair-progress_4_1"> Pair&lt; T, U&gt;
</label>
</div>
<div class="field">
<input class="field-input input-radio" type="radio" name="input_02-pair-progress_4_1" id="input_02-pair-progress_4_1_choice_1" value="choice_1"/><label class="response-label field-label label-inline" for="input_02-pair-progress_4_1_choice_1" id="02-pair-progress_4_1-choice_1-label" aria-describedby="status_02-pair-progress_4_1"> T
</label>
</div>
<div class="field">
<input class="field-input input-radio" type="radio" name="input_02-pair-progress_4_1" id="input_02-pair-progress_4_1_choice_2" value="choice_2"/><label class="response-label field-label label-inline" for="input_02-pair-progress_4_1_choice_2" id="02-pair-progress_4_1-choice_2-label" aria-describedby="status_02-pair-progress_4_1"> U
</label>
</div>
<div class="field">
<input class="field-input input-radio" type="radio" name="input_02-pair-progress_4_1" id="input_02-pair-progress_4_1_choice_3" value="choice_3"/><label class="response-label field-label label-inline" for="input_02-pair-progress_4_1_choice_3" id="02-pair-progress_4_1-choice_3-label" aria-describedby="status_02-pair-progress_4_1"> second
</label>
</div>
<div class="field">
<input class="field-input input-radio" type="radio" name="input_02-pair-progress_4_1" id="input_02-pair-progress_4_1_choice_4" value="choice_4"/><label class="response-label field-label label-inline" for="input_02-pair-progress_4_1_choice_4" id="02-pair-progress_4_1-choice_4-label" aria-describedby="status_02-pair-progress_4_1"> t
</label>
</div>
<div class="field">
<input class="field-input input-radio" type="radio" name="input_02-pair-progress_4_1" id="input_02-pair-progress_4_1_choice_5" value="choice_5"/><label class="response-label field-label label-inline" for="input_02-pair-progress_4_1_choice_5" id="02-pair-progress_4_1-choice_5-label" aria-describedby="status_02-pair-progress_4_1"> u
</label>
</div>
<span id="answer_02-pair-progress_4_1"/>
</fieldset>
<div class="indicator-container">
<span class="status unanswered" data-tooltip="Not yet answered." id="status_02-pair-progress_4_1">
<span class="sr">unanswered</span><span class="status-icon" aria-hidden="true"/>
</span>
</div>
</div></div>
<p>SECOND_OUTPUTS</p>
<div class="wrapper-problem-response" tabindex="-1" aria-label="Question 4" role="group"><div class="choicegroup capa_inputtype" id="inputtype_02-pair-progress_5_1">
<fieldset aria-describedby="status_02-pair-progress_5_1">
<div class="field">
<input class="field-input input-radio" type="radio" name="input_02-pair-progress_5_1" id="input_02-pair-progress_5_1_choice_0" value="choice_0"/><label class="response-label field-label label-inline" for="input_02-pair-progress_5_1_choice_0" id="02-pair-progress_5_1-choice_0-label" aria-describedby="status_02-pair-progress_5_1"> Pair&lt; T, U&gt;
</label>
</div>
<div class="field">
<input class="field-input input-radio" type="radio" name="input_02-pair-progress_5_1" id="input_02-pair-progress_5_1_choice_1" value="choice_1"/><label class="response-label field-label label-inline" for="input_02-pair-progress_5_1_choice_1" id="02-pair-progress_5_1-choice_1-label" aria-describedby="status_02-pair-progress_5_1"> T
</label>
</div>
<div class="field">
<input class="field-input input-radio" type="radio" name="input_02-pair-progress_5_1" id="input_02-pair-progress_5_1_choice_2" value="choice_2"/><label class="response-label field-label label-inline" for="input_02-pair-progress_5_1_choice_2" id="02-pair-progress_5_1-choice_2-label" aria-describedby="status_02-pair-progress_5_1"> U
</label>
</div>
<div class="field">
<input class="field-input input-radio" type="radio" name="input_02-pair-progress_5_1" id="input_02-pair-progress_5_1_choice_3" value="choice_3"/><label class="response-label field-label label-inline" for="input_02-pair-progress_5_1_choice_3" id="02-pair-progress_5_1-choice_3-label" aria-describedby="status_02-pair-progress_5_1"> second
</label>
</div>
<div class="field">
<input class="field-input input-radio" type="radio" name="input_02-pair-progress_5_1" id="input_02-pair-progress_5_1_choice_4" value="choice_4"/><label class="response-label field-label label-inline" for="input_02-pair-progress_5_1_choice_4" id="02-pair-progress_5_1-choice_4-label" aria-describedby="status_02-pair-progress_5_1"> t
</label>
</div>
<div class="field">
<input class="field-input input-radio" type="radio" name="input_02-pair-progress_5_1" id="input_02-pair-progress_5_1_choice_5" value="choice_5"/><label class="response-label field-label label-inline" for="input_02-pair-progress_5_1_choice_5" id="02-pair-progress_5_1-choice_5-label" aria-describedby="status_02-pair-progress_5_1"> u
</label>
</div>
<span id="answer_02-pair-progress_5_1"/>
</fieldset>
<div class="indicator-container">
<span class="status unanswered" data-tooltip="Not yet answered." id="status_02-pair-progress_5_1">
<span class="sr">unanswered</span><span class="status-icon" aria-hidden="true"/>
</span>
</div>
</div></div>
<div class="solution-span">
<span id="solution_02-pair-progress_solution_1"/>
</div></div>
<div class="action">
<input type="hidden" name="problem_id" value="Pair progress" />
<div class="submit-attempt-container">
<button type="button" class="submit btn-brand" data-submitting="Submitting" data-value="Submit" data-should-enable-submit-button="True" aria-describedby="submission_feedback_02-pair-progress" >
<span class="submit-label">Submit</span>
</button>
<div class="submission-feedback" id="submission_feedback_02-pair-progress">
<span class="sr">Some problems have options such as save, reset, hints, or show answer. These options follow the Submit button.</span>
</div>
</div>
<div class="problem-action-buttons-wrapper">
</div>
</div>
<div class="notification warning notification-gentle-alert
is-hidden"
tabindex="-1">
<span class="icon fa fa-exclamation-circle" aria-hidden="true"></span>
<span class="notification-message" aria-describedby="02-pair-progress-problem-title">
</span>
<div class="notification-btn-wrapper">
<button type="button" class="btn btn-default btn-small notification-btn review-btn sr">Review</button>
</div>
</div>
<div class="notification warning notification-save
is-hidden"
tabindex="-1">
<span class="icon fa fa-save" aria-hidden="true"></span>
<span class="notification-message" aria-describedby="02-pair-progress-problem-title">None
</span>
<div class="notification-btn-wrapper">
<button type="button" class="btn btn-default btn-small notification-btn review-btn sr">Review</button>
</div>
</div>
<div class="notification general notification-show-answer
is-hidden"
tabindex="-1">
<span class="icon fa fa-info-circle" aria-hidden="true"></span>
<span class="notification-message" aria-describedby="02-pair-progress-problem-title">Answers are displayed within the problem
</span>
<div class="notification-btn-wrapper">
<button type="button" class="btn btn-default btn-small notification-btn review-btn sr">Review</button>
</div>
</div>
</div>
"
data-graded="True">
<p class="loading-spinner">
<i class="fa fa-spinner fa-pulse fa-2x fa-fw"></i>
<span class="sr">Loading…</span>
</p>
</div>
</div>
</div>
</div>
</div>
<div class="xblock xblock-public_view xblock-public_view-vertical" data-has-score="False" data-runtime-class="LmsRuntime" data-graded="True" data-request-token="3f7f1aefe9a311efbd7412d4917dea95" data-runtime-version="1" data-block-type="vertical" data-course-id="course-v1:MITx+6.005.2x+1T2017" data-init="VerticalStudentView" data-usage-id="block-v1:MITx+6.005.2x+1T2017+type@vertical+block@Reading_2_Summary">
<h2 class="hd hd-2 unit-title">Reading 2 Summary</h2>
<div class="vert-mod">
<div class="vert vert-0" data-id="block-v1:MITx+6.005.2x+1T2017+type@html+block@html_2257b496f76e">
<div class="xblock xblock-public_view xblock-public_view-html xmodule_display xmodule_HtmlBlock" data-has-score="False" data-runtime-class="LmsRuntime" data-graded="True" data-request-token="3f7f1aefe9a311efbd7412d4917dea95" data-runtime-version="1" data-block-type="html" data-course-id="course-v1:MITx+6.005.2x+1T2017" data-init="XBlockToXModuleShim" data-usage-id="block-v1:MITx+6.005.2x+1T2017+type@html+block@html_2257b496f76e">
<script type="json/xblock-args" class="xblock-json-init-args">
{"xmodule-type": "HTMLModule"}
</script>
<link href="/assets/courseware/v1/b2188f0a95a7a9062748278f7d5a584f/asset-v1:MITx+6.005.2x+1T2017+type@asset+block/syntax-highlighting.css" rel="stylesheet" type="text/css" />
<h2 id="summary">Summary</h2>
<div data-outline="summary">
<p>In addition to the big idea of <strong>recursive datatypes</strong>, we saw in this reading:</p>
<ul>
<li><strong>datatype definitions</strong>: a powerful way to think about abstract types, particularly recursive ones</li>
<li><strong>functions over recursive datatypes</strong>: declared in the specification for the type, and implemented with one case per concrete variant</li>
<li>immutable lists: a classic, canonical example of an immutable datatype</li>
</ul>
<p>As always, we ask how these ideas make our code <strong>safer from bugs</strong>, <strong>easier to understand</strong>, and more <strong>ready for change</strong>. Look again at the <a href="/courses/course-v1:MITx+6.005.2x+1T2017/jump_to_id/vertical-functions-over-recursive-datatypes">definition and implementation of <code>size()</code> in <code>ImList</code></a>. The definition is little more than the mathematical definition of size. The code is little more than the definition, with some semicolons to placate the compiler.</p>
<p>If we examine the definitions for further methods — <code>isEmpty</code>, <code>contains</code>, etc. — in each case we see a safe, easy-to-read implementation waiting to be coded. Since we've taken the time to specify these operations, if we avoid rep exposure and maintain rep independence, we know our code is ready for change: different clients will be able to reuse our datatype, and we will be able to update the implementation without breaking them.</p>
<p>Let's review how recursive datatypes fit in with the main goals of this course:</p>
<ul>
<li>
<p><strong>Safe from bugs</strong>. Recursive datatypes allow us to tackle problems with a recursive or unbounded structure. Implementing appropriate data structures that encapsulate important operations and maintain their own invariants is crucial for correctness.</p>
</li>
<li>
<p><strong>Easy to understand</strong>. Functions over recursive datatypes, specified in the abstract type and implemented in each concrete variant, organize the different behavior of the type.</p>
</li>
<li>
<p><strong>Ready for change</strong>. A recursive ADT, like any ADT, separates abstract values from concrete representations, making it possible to change low-level code and high-level structure of the implementation without changing clients.</p>
</li>
</ul>
</div>
<div class="license">This reading was collaboratively authored with contributions from: Saman Amarasinghe, Adam Chlipala, Srini Devadas, Michael Ernst, Max Goldman, John Guttag, Daniel Jackson, Rob Miller, Martin Rinard, and Armando Solar-Lezama. This work is licensed under <a rel="license" href="http://creativecommons.org/licenses/by-sa/4.0/">CC BY-SA 4.0</a>.</div>
</div>
</div>
</div>
</div>