{ "cells": [ { "cell_type": "markdown", "id": "3d02434f", "metadata": {}, "source": [ "Before you turn this problem in, make sure everything runs as expected. First, **restart the kernel** (in the menubar, select Kernel $\\rightarrow$ Restart) and then **run all cells** (in the menubar, select Cell $\\rightarrow$ Run All).\n", "\n", "Make sure you fill in any place that says `???`, `YOUR CODE HERE`, \"???\", \"YOUR ANSWER HERE\", as well as your name and collaborators below:" ] }, { "cell_type": "code", "execution_count": 47, "id": "8a89a7aa", "metadata": {}, "outputs": [ { "data": { "text/plain": [ "\u001b[36mNAME\u001b[39m: \u001b[32mString\u001b[39m = \u001b[32m\"Jack Sangdahl\"\u001b[39m\n", "\u001b[36mCOLLABORATORS\u001b[39m: \u001b[32mString\u001b[39m = \u001b[32m\"N/A\"\u001b[39m" ] }, "execution_count": 47, "metadata": {}, "output_type": "execute_result" } ], "source": [ "val NAME = \"Jack Sangdahl\"\n", "val COLLABORATORS = \"N/A\"" ] }, { "cell_type": "markdown", "id": "d009c835", "metadata": {}, "source": [ "---" ] }, { "cell_type": "markdown", "id": "9d34c7c8-c787-4f41-bd3a-5628797aa728", "metadata": {}, "source": [ "# Exercise: Expressions and Data Types\n", "\n", "\n", "\n", "\n", "\n", "The purpose of this assignment is to warm-up with Scala.\n", "\n", "### Learning Goals\n", "\n", "The primary learning goals of this assignment are to build intuition for\n", "the following:\n", "\n", "- thinking in terms of types, values, and expressions; and\n", "- imperative iteration.\n", "\n", "### Instructions\n", "\n", "This assignment asks you to write Scala code. There are restrictions\n", "associated with how you can solve these problems. Please pay careful\n", "heed to those. If you are unsure, ask the course staff.\n", "\n", "Note that `???` indicates that there is a missing function or code\n", "fragment that needs to be filled in. In Scala, it is also an expression\n", "that throws a `NotImplementedError` exception. Make sure that you remove\n", "the `???` and replace it with the answer.\n", "\n", "Use the test cases provided to test your implementations. You are also\n", "encouraged to write your own test cases to help debug your work.\n", "However, please delete any extra cells you may have created lest they\n", "break an autograder.\n", "\n", "## Type Checking\n", "\n", "In the following, I have left off the return type of function `g`. The\n", "body of `g` is well-typed if we can come up with a valid return type. In\n", "this question, we will reason for ourselves that `g` is indeed\n", "well-typed." ] }, { "cell_type": "code", "execution_count": 48, "id": "0db88593", "metadata": {}, "outputs": [ { "data": { "text/plain": [ "defined \u001b[32mfunction\u001b[39m \u001b[36mg\u001b[39m" ] }, "execution_count": 48, "metadata": {}, "output_type": "execute_result" } ], "source": [ "def g(x: Int) = /*e1*/({\n", " // env1\n", " val (a, b) = /*e2*/(\n", " // env2\n", " (1, (x, 3))\n", " )\n", " /*e3*/(\n", " // env3\n", " if (x == 0) (b, 1) else (b, a + 2)\n", " )\n", "})" ] }, { "cell_type": "markdown", "id": "27d6ff35-074c-4171-a7f5-a035015e7b83", "metadata": {}, "source": [ "We have added parentheses around 3 key sub-expressions of the body of\n", "`g` (e.g., `/*e1*/(`$\\ldots$`)`) and noted that there are corresponding\n", "environments (e.g., `// env1` for each sub-expression).\n", "\n", "### Q1.1: What is the type environment `env1`? Briefly explain.\n", "\n", "Use either format shown in the notes (e.g.,\n", "$[ x_1 : \\tau_1, \\ldots, x_n : \\tau_n ]$)." ] }, { "cell_type": "markdown", "id": "672c616d-04fb-41cf-aad5-6f025548b7b7", "metadata": { "deletable": false, "nbgrader": { "cell_type": "markdown", "checksum": "e41ca86f62e024565d1f2956f3950f48", "grade": true, "grade_id": "q1_1", "locked": false, "points": 2, "schema_version": 3, "solution": true, "task": false } }, "source": [ "The type environment of `env1` alone is $[\\:\\mathtt{env1} \\mapsto\\mathtt{Int}\\:]$. At this point, the only variable in scope is the parameter `x: Int`, so `env1` also maps to `Int`." ] }, { "cell_type": "markdown", "id": "d577d0ca-7375-4e10-a89f-6a9f067a8f9f", "metadata": {}, "source": [ "### Q1.2: What is the type environment `env2`? Briefly explain." ] }, { "cell_type": "markdown", "id": "62ae6788-7ed6-4acd-9d5c-40192d303dc9", "metadata": { "deletable": false, "nbgrader": { "cell_type": "markdown", "checksum": "4660b9558a8195d26712214909a62db2", "grade": true, "grade_id": "q1_2", "locked": false, "points": 2, "schema_version": 3, "solution": true, "task": false } }, "source": [ "The type environment of `env2` is $[\\:\\mathtt{env2} \\mapsto\\mathtt{Int}\\:]$. `env2` references the known type of `x: Int`, which also maps `env2` to `Int`." ] }, { "cell_type": "markdown", "id": "93547002-40ae-42f1-a910-38131a7d26f6", "metadata": {}, "source": [ "### Q1.3: Derive the type of expression `e2`.\n", "\n", "Showing the type for each sub-expression of `e2`; stop when you reach\n", "literals or variable uses." ] }, { "cell_type": "markdown", "id": "4114c6c1-7098-466c-bf92-69aa4a321664", "metadata": { "deletable": false, "nbgrader": { "cell_type": "markdown", "checksum": "315ba92969984b267763af81ebd0f5d0", "grade": true, "grade_id": "q1_3", "locked": false, "points": 10, "schema_version": 3, "solution": true, "task": false } }, "source": [ "```scala\n", "(1, (x, 3)): (Int, (Int, Int))\n", "- if 1: Int\n", "- if (x, 3): (Int, Int)\n", " - if x: Int\n", " - if 3: Int\n", "```" ] }, { "cell_type": "markdown", "id": "934b39f4-9eb5-4186-8e8d-f05f24d0f578", "metadata": {}, "source": [ "#### Notes\n", "\n", "Use the format shown in the notes. Here’s such a derivation for the type\n", "of the expression `(1 + 2) + (3 + 4)`.\n", "\n", "``` scala\n", "(1 + 2) + (3 + 4): Int\n", "- if 1 + 2: Int\n", " - if 1: Int\n", " - if 2: Int\n", "- if 3 + 4: Int\n", " - if 3: Int\n", " - if 4: Int\n", "```\n", "\n", "### Q1.4: What is the type environment `env3`? Briefly explain." ] }, { "cell_type": "markdown", "id": "2e94876a-32b9-477c-9aa1-91253dde0d30", "metadata": { "deletable": false, "nbgrader": { "cell_type": "markdown", "checksum": "e5b9bc3f55c403acbbb1e709d2b68f12", "grade": true, "grade_id": "q1_4", "locked": false, "points": 2, "schema_version": 3, "solution": true, "task": false } }, "source": [ "The type environment of `env3` alone is $[\\:\\mathtt{env3} \\mapsto\\mathtt{x: Int, a: Int, b: (Int, Int)}\\:]$. At this point, `env3` includes the variables `x`, `a`, and `b`. We know `x: Int` from the function argument, `a: Int` from the tuple deconstruction, and `b: (Int, Int)` also from the tuple deconstruction." ] }, { "cell_type": "markdown", "id": "7faf5604-c103-44b1-a711-334dfdab5d6c", "metadata": {}, "source": [ "### Q1.5: Derive the type of expression `e3`." ] }, { "cell_type": "markdown", "id": "ceae2d55-bef9-4cc5-a3dc-cfd11db90e43", "metadata": { "deletable": false, "nbgrader": { "cell_type": "markdown", "checksum": "52869852b70e53b19066a880678a23b7", "grade": true, "grade_id": "q1_5", "locked": false, "points": 2, "schema_version": 3, "solution": true, "task": false } }, "source": [ "```scala\n", "if (x == 0) (b, 1) else (b, a + 2): ((Int, Int), Int)\n", "- if x == 0: Boolean\n", " - if (b, 1): Int\n", " - if b: Int\n", " - if 1: Int\n", " - if (b, a + 2): Int\n", " - if b: Int\n", " - if a + 2: Int\n", " - if a: Int\n", " - if 2: Int\n", "```" ] }, { "cell_type": "markdown", "id": "bab903c4-188f-46ed-86dd-9495e781ff51", "metadata": {}, "source": [ "### Q1.6: Confirm your derivations by adding type assertions to each sub-expression of `g` and adding the return type of `g`.\n", "\n", "That is, replace sub-expressions $e$ of `g` with expressions $e$ `:`\n", "$\\tau$. You may need to add some parentheses—`(` $e$ `:` $\\tau$ `)`—to\n", "preserve the syntactic structure. Skip adding typing assertions for\n", "literals and variable uses.\n", "\n", "**Edit this cell:**" ] }, { "cell_type": "code", "execution_count": 6, "id": "b472b0a7", "metadata": { "deletable": false, "nbgrader": { "cell_type": "code", "checksum": "c4abe7222641b8ec119ec31036e39b95", "grade": true, "grade_id": "q1_6", "locked": false, "points": 9, "schema_version": 3, "solution": true, "task": false } }, "outputs": [ { "data": { "text/plain": [ "defined \u001b[32mfunction\u001b[39m \u001b[36mg\u001b[39m" ] }, "execution_count": 6, "metadata": {}, "output_type": "execute_result" } ], "source": [ "def g(x: Int) = /*e1*/({\n", " // env1\n", " val (a: Int, b: (Int, Int)) = /*e2*/(\n", " // env2\n", " (1, (x, 3)): (Int, (Int, Int))\n", " )\n", " /*e3*/(\n", " // env3\n", " if (x == 0: Boolean) (b, 1): ((Int, Int), Int) else (b, a + 2): ((Int, Int), Int)\n", " ): ((Int, Int), Int)\n", "}): ((Int, Int), Int) " ] }, { "cell_type": "markdown", "id": "d5e75af2-a72c-4fed-a247-aa90d3f8f0ad", "metadata": {}, "source": [ "*Hint*: There are 8 sub-expressions that are not literals nor variable\n", "uses that need typing assertions (i.e., $e$ `:` $\\tau$), plus 1 more\n", "annotation for the return type of `g`.\n", "\n", "## Unit Testing\n", "\n", "When starting to program in the large, it is useful to use a testing\n", "framework to manage tests and integrate with IDEs. One that is commonly\n", "used in Scala is [ScalaTest](https://www.scalatest.org/).\n", "\n", "While it is somewhat overkill for testing small exercises like the ones\n", "to come, we practice here writing tests using ScalaTest.\n", "\n", "To load the ScalaTest library, run the following cell:" ] }, { "cell_type": "code", "execution_count": 50, "id": "8fea5968", "metadata": { "deletable": false, "editable": false, "nbgrader": { "cell_type": "code", "checksum": "bdf4aa1ba5caa128e0dbcd6cc1ad5766", "grade": false, "grade_id": "testing", "locked": true, "schema_version": 3, "solution": false, "task": false } }, "outputs": [ { "data": { "text/plain": [ "\u001b[32mimport \u001b[39m\u001b[36mRUN this cell FIRST before testing\n", "import $ivy.$ , org.scalatest._, events._, flatspec._\n", "\u001b[39m\n", "defined \u001b[32mfunction\u001b[39m \u001b[36mreport\u001b[39m\n", "defined \u001b[32mfunction\u001b[39m \u001b[36massertPassed\u001b[39m\n", "defined \u001b[32mfunction\u001b[39m \u001b[36mtest\u001b[39m" ] }, "execution_count": 50, "metadata": {}, "output_type": "execute_result" } ], "source": [ "// RUN this cell FIRST before testing\n", "import $ivy.`org.scalatest::scalatest:3.2.19`, org.scalatest._, events._, flatspec._\n", "def report(suite: Suite) = suite.execute(stats = true)\n", "def assertPassed(suite: Suite) =\n", " suite.run(None, Args(new Reporter {\n", " def apply(e: Event) = e match {\n", " case e @ (_: TestFailed) => assert(false, s\"${e.message} (${e.testName})\")\n", " case _ => ()\n", " }\n", " }))\n", "def test(suite: Suite) = {\n", " report(suite)\n", " assertPassed(suite)\n", "}" ] }, { "cell_type": "markdown", "id": "67ac4efd-c505-4a4f-a6f5-91610f977849", "metadata": {}, "source": [ "### Q2.1: Unit Test `plus`\n", "\n", "For this question, **edit the next two code cells** to fix the\n", "implementation of `plus` and add the appropriate assertion for the third\n", "test case `\"add (3,4) == 7\"`.\n", "\n", "Our goal is unit test the following complicated function (that we’ve\n", "gotten wrong!):" ] }, { "cell_type": "code", "execution_count": 51, "id": "6bc42853", "metadata": {}, "outputs": [ { "data": { "text/plain": [ "defined \u001b[32mfunction\u001b[39m \u001b[36mplus\u001b[39m" ] }, "execution_count": 51, "metadata": {}, "output_type": "execute_result" } ], "source": [ "def plus(n: Int, m: Int): Int = n + m" ] }, { "cell_type": "markdown", "id": "2fd19eae-bb49-4616-94f4-e2383aad90c9", "metadata": {}, "source": [ "To use ScalaTest, we create “Spec” objects using ScalaTest methods like\n", "`should` that define an embedded domain-specific language (DSL) for\n", "defining tests:" ] }, { "cell_type": "code", "execution_count": 52, "id": "1255cbba", "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "\u001b[36mRun starting. Expected test count is: 3\u001b[0m\n", "\u001b[32mcmd52$Helper$$anon$1:\u001b[0m\n", "\u001b[32mplus\u001b[0m\n", "\u001b[32m- should add 1 + 1 == 2\u001b[0m\n", "\u001b[32m- should add 2 + 2 == 4\u001b[0m\n", "\u001b[32m- should add 3 + 4 == 7\u001b[0m\n", "\u001b[36mRun completed in 2 milliseconds.\u001b[0m\n", "\u001b[36mTotal number of tests run: 3\u001b[0m\n", "\u001b[36mSuites: completed 1, aborted 0\u001b[0m\n", "\u001b[36mTests: succeeded 3, failed 0, canceled 0, ignored 0, pending 0\u001b[0m\n", "\u001b[32mAll tests passed.\u001b[0m\n" ] }, { "data": { "text/plain": [ "\u001b[36mplusSuite\u001b[39m: \u001b[32mAnyFlatSpec\u001b[39m = cmd52$Helper$$anon$1" ] }, "execution_count": 52, "metadata": {}, "output_type": "execute_result" } ], "source": [ "val plusSuite = new AnyFlatSpec {\n", " // Define a *subject* to test (e.g., \"plus\").\n", " // After `should`, name a test (e.g, \"add (1, 1) == 2\").\n", " // After `in`, specify assertions (e.g., `assert(plus(1,1) == 2))\n", " \"plus\" should \"add 1 + 1 == 2\" in {\n", " // Specify assertions here.\n", " assert(plus(1,1) == 2)\n", " }\n", "\n", " it should \"add 2 + 2 == 4\" in {\n", " // It is convenient to distinguish the expected result from the code that\n", " // you're testing, which affects the error messages when the test fails.\n", " assertResult(2 + 2) {\n", " plus(2,2)\n", " }\n", " }\n", " it should \"add 3 + 4 == 7\" in {\n", " assertResult(3 + 4) {\n", " plus(3, 4)\n", " }\n", " }\n", "}\n", "report(plusSuite)" ] }, { "cell_type": "code", "execution_count": 53, "id": "27368277", "metadata": { "deletable": false, "editable": false, "nbgrader": { "cell_type": "code", "checksum": "8ac2636aa17b31fca777bf3064b8d491", "grade": true, "grade_id": "q2_1", "locked": true, "points": 3, "schema_version": 3, "solution": false, "task": false } }, "outputs": [ { "data": { "text/plain": [ "\u001b[36mres53\u001b[39m: \u001b[32mStatus\u001b[39m = org.scalatest.CompositeStatus@48f724de" ] }, "execution_count": 53, "metadata": {}, "output_type": "execute_result" } ], "source": [ "assertPassed(plusSuite)" ] }, { "cell_type": "markdown", "id": "be1d876b-25dc-451a-86db-ed1cf1fed54e", "metadata": {}, "source": [ "## Run-Time Library\n", "\n", "Most languages come with a standard library with support for things like\n", "data structures, mathematical operators, string processing, etc.\n", "Standard library functions may be implemented in the object language\n", "(perhaps for portability) or the meta language (perhaps for\n", "implementation efficiency).\n", "\n", "For this question, we will implement some library functions in Scala,\n", "our meta language, that we can imagine will be part of the run-time for\n", "our object language interpreter. In actuality, the main purpose of this\n", "exercise is to warm-up with Scala programming.\n", "\n", "### Q3.1: Write and test a function `abs`\n", "\n", "**Edit this cell:**" ] }, { "cell_type": "code", "execution_count": 54, "id": "3f001698", "metadata": { "deletable": false, "nbgrader": { "cell_type": "code", "checksum": "d1bacc19634bfb1bf864bd58b41906c4", "grade": false, "grade_id": "q3_1_code", "locked": false, "schema_version": 3, "solution": true, "task": false } }, "outputs": [ { "data": { "text/plain": [ "defined \u001b[32mfunction\u001b[39m \u001b[36mabs\u001b[39m" ] }, "execution_count": 54, "metadata": {}, "output_type": "execute_result" } ], "source": [ "def abs(n: Double): Double = ({\n", " if (n < 0) {\n", " -n\n", " } else {\n", " n\n", " }\n", "})" ] }, { "cell_type": "markdown", "id": "71c5328d-b26d-497d-adaf-6ef22d22688f", "metadata": {}, "source": [ "that returns the absolute value of `n`. This a function that takes a\n", "value of type `Double` and returns a value of type `Double`. This\n", "function corresponds to the JavaScript library function `Math.abs`.\n", "\n", "#### Notes\n", "\n", "- Do not use any Scala library functions.\n", "\n", "#### Tests\n", "\n", "**Edit this cell:**" ] }, { "cell_type": "code", "execution_count": 55, "id": "d913e614", "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "\u001b[36mRun starting. Expected test count is: 4\u001b[0m\n", "\u001b[32mcmd55$Helper$$anon$1:\u001b[0m\n", "\u001b[32mabs\u001b[0m\n", "\u001b[32m- should abs(2) == 2\u001b[0m\n", "\u001b[32m- should abs(-2) == 2\u001b[0m\n", "\u001b[32m- should abs(0) == 0\u001b[0m\n", "\u001b[32m- should abs(1) == 1\u001b[0m\n", "\u001b[36mRun completed in 3 milliseconds.\u001b[0m\n", "\u001b[36mTotal number of tests run: 4\u001b[0m\n", "\u001b[36mSuites: completed 1, aborted 0\u001b[0m\n", "\u001b[36mTests: succeeded 4, failed 0, canceled 0, ignored 0, pending 0\u001b[0m\n", "\u001b[32mAll tests passed.\u001b[0m\n" ] }, { "data": { "text/plain": [ "\u001b[36mabsSuite\u001b[39m: \u001b[32mAnyFlatSpec\u001b[39m = cmd55$Helper$$anon$1" ] }, "execution_count": 55, "metadata": {}, "output_type": "execute_result" } ], "source": [ "val absSuite = new AnyFlatSpec {\n", " \"abs\" should \"abs(2) == 2\" in {\n", " assert(abs(2) == 2)\n", " }\n", " it should \"abs(-2) == 2\" in {\n", " assert(abs(-2) == 2)\n", " }\n", " it should \"abs(0) == 0\" in {\n", " assert(abs(0) === 0)\n", " }\n", " it should \"abs(1) == 1\" in {\n", " assert(abs(1) === 1)\n", " }\n", "}\n", "report(absSuite)" ] }, { "cell_type": "code", "execution_count": 56, "id": "1956942b", "metadata": { "deletable": false, "editable": false, "nbgrader": { "cell_type": "code", "checksum": "8ae14654f39c831149cca3cd7bc9901f", "grade": true, "grade_id": "q3_1", "locked": true, "points": 4, "schema_version": 3, "solution": false, "task": false } }, "outputs": [ { "data": { "text/plain": [ "\u001b[36mres56\u001b[39m: \u001b[32mStatus\u001b[39m = org.scalatest.CompositeStatus@4fd24e85" ] }, "execution_count": 56, "metadata": {}, "output_type": "execute_result" } ], "source": [ "assertPassed(absSuite)" ] }, { "cell_type": "markdown", "id": "21898c2c-2b50-42c1-85f9-df4be93e8284", "metadata": {}, "source": [ "### Q3.2: Write and test a function `xor`\n", "\n", "**Edit this cell:**" ] }, { "cell_type": "code", "execution_count": 57, "id": "3c119212", "metadata": { "deletable": false, "nbgrader": { "cell_type": "code", "checksum": "ac179e4aa90d501026fc34ffbf524ab7", "grade": false, "grade_id": "q3_2_code", "locked": false, "schema_version": 3, "solution": true, "task": false } }, "outputs": [ { "data": { "text/plain": [ "defined \u001b[32mfunction\u001b[39m \u001b[36mxor\u001b[39m" ] }, "execution_count": 57, "metadata": {}, "output_type": "execute_result" } ], "source": [ "def xor(a: Boolean, b: Boolean): Boolean = a ^ b" ] }, { "cell_type": "markdown", "id": "5b47755a-a0e7-44ee-acc5-10a06d925697", "metadata": {}, "source": [ "that returns the exclusive-or of `a` and `b`. The exclusive-or returns\n", "`true` if and only if exactly one of `a` or `b` is `true`.\n", "\n", "#### Notes\n", "\n", "- For practice, do not use the Boolean operators. Instead, only use\n", " the `if`- expression and the Boolean literals (i.e., `true` or\n", " `false`).\n", "\n", "#### Tests\n", "\n", "**Edit this cell:**" ] }, { "cell_type": "code", "execution_count": 58, "id": "f723c395", "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "\u001b[36mRun starting. Expected test count is: 4\u001b[0m\n", "\u001b[32mcmd58$Helper$$anon$1:\u001b[0m\n", "\u001b[32mxor\u001b[0m\n", "\u001b[32m- should !xor(true, true)\u001b[0m\n", "\u001b[32m- should xor(true, false)\u001b[0m\n", "\u001b[32m- should xor(false, true)\u001b[0m\n", "\u001b[32m- should !xor(false, false)\u001b[0m\n", "\u001b[36mRun completed in 11 milliseconds.\u001b[0m\n", "\u001b[36mTotal number of tests run: 4\u001b[0m\n", "\u001b[36mSuites: completed 1, aborted 0\u001b[0m\n", "\u001b[36mTests: succeeded 4, failed 0, canceled 0, ignored 0, pending 0\u001b[0m\n", "\u001b[32mAll tests passed.\u001b[0m\n" ] }, { "data": { "text/plain": [ "\u001b[36mxorSuite\u001b[39m: \u001b[32mAnyFlatSpec\u001b[39m = cmd58$Helper$$anon$1" ] }, "execution_count": 58, "metadata": {}, "output_type": "execute_result" } ], "source": [ "val xorSuite = new AnyFlatSpec {\n", " \"xor\" should \"!xor(true, true)\" in {\n", " assert(!xor(true, true))\n", " }\n", " it should \"xor(true, false)\" in {\n", " assert(xor(true, false))\n", " }\n", " it should \"xor(false, true)\" in {\n", " assert(xor(false, true))\n", " }\n", " it should \"!xor(false, false)\" in {\n", " assert(!xor(false, false))\n", " }\n", "}\n", "report(xorSuite)" ] }, { "cell_type": "code", "execution_count": 59, "id": "5fc09530", "metadata": { "deletable": false, "editable": false, "nbgrader": { "cell_type": "code", "checksum": "475a7a4bd08579befea92b998fc9a712", "grade": true, "grade_id": "q3_2", "locked": true, "points": 4, "schema_version": 3, "solution": false, "task": false } }, "outputs": [ { "data": { "text/plain": [ "\u001b[36mres59\u001b[39m: \u001b[32mStatus\u001b[39m = org.scalatest.CompositeStatus@2780f927" ] }, "execution_count": 59, "metadata": {}, "output_type": "execute_result" } ], "source": [ "assertPassed(xorSuite)" ] }, { "cell_type": "markdown", "id": "4b0a894d-67f5-480a-bbcb-2abe33b45784", "metadata": {}, "source": [ "## Imperative Iteration and Complexity\n", "\n", "### Q4.1: Write a function `filterPairsByBound`\n", "\n", "**Edit this cell:**" ] }, { "cell_type": "code", "execution_count": 60, "id": "a9436132", "metadata": { "deletable": false, "nbgrader": { "cell_type": "code", "checksum": "ed640d35faac5ce44926effc28995737", "grade": false, "grade_id": "q4_1_code", "locked": false, "schema_version": 3, "solution": true, "task": false } }, "outputs": [ { "data": { "text/plain": [ "defined \u001b[32mfunction\u001b[39m \u001b[36mfilterPairsByBound\u001b[39m" ] }, "execution_count": 60, "metadata": {}, "output_type": "execute_result" } ], "source": [ "def filterPairsByBound(list: List[(Int, Int)], k: Int): List[(Int, Int)] =\n", " list.filter { // iterate through the tuples in list\n", " case (n1, n2) => // for each pair (n1, n2)...\n", " // return appropriate value when leq k \n", " // using our abs() function from Q3.1\n", " abs(n1 - n2) <= k\n", " }" ] }, { "cell_type": "markdown", "id": "d95cdad4-4de8-440e-8a25-b1f9d901091a", "metadata": {}, "source": [ "that given a list of pairs of integers, for example," ] }, { "cell_type": "code", "execution_count": 61, "id": "15116cf9", "metadata": {}, "outputs": [ { "data": { "text/plain": [ "\u001b[36minput1_l\u001b[39m: \u001b[32mList\u001b[39m[(\u001b[32mInt\u001b[39m, \u001b[32mInt\u001b[39m)] = \u001b[33mList\u001b[39m(\n", " (\u001b[32m1\u001b[39m, \u001b[32m5\u001b[39m),\n", " (\u001b[32m2\u001b[39m, \u001b[32m7\u001b[39m),\n", " (\u001b[32m15\u001b[39m, \u001b[32m14\u001b[39m),\n", " (\u001b[32m18\u001b[39m, \u001b[32m19\u001b[39m),\n", " (\u001b[32m14\u001b[39m, \u001b[32m28\u001b[39m),\n", " (\u001b[32m0\u001b[39m, \u001b[32m0\u001b[39m),\n", " (\u001b[32m35\u001b[39m, \u001b[32m24\u001b[39m)\n", ")" ] }, "execution_count": 61, "metadata": {}, "output_type": "execute_result" } ], "source": [ "val input1_l = List( (1, 5), (2, 7), (15, 14), (18, 19), (14, 28), (0,0), (35, 24) )" ] }, { "cell_type": "markdown", "id": "46a2bbe6-ac0c-4fd1-a4e2-15f66b895bf8", "metadata": {}, "source": [ "output a list consisting of just those pairs $(n_1, n_2)$ in the\n", "original list wherein $|n_1 - n_2| \\leq k$ where $k$ is an integer given\n", "as input. Ensure that the order of the elements in the output list is\n", "the same as that in the input list.\n", "\n", "For the list `input1`, the expected output, with `k == 1`, the expected\n", "output is as follows:" ] }, { "cell_type": "code", "execution_count": 62, "id": "c378241a", "metadata": {}, "outputs": [ { "data": { "text/plain": [ "\u001b[36minput1_k\u001b[39m: \u001b[32mInt\u001b[39m = \u001b[32m1\u001b[39m\n", "\u001b[36moutput1\u001b[39m: \u001b[32mList\u001b[39m[(\u001b[32mInt\u001b[39m, \u001b[32mInt\u001b[39m)] = \u001b[33mList\u001b[39m((\u001b[32m15\u001b[39m, \u001b[32m14\u001b[39m), (\u001b[32m18\u001b[39m, \u001b[32m19\u001b[39m), (\u001b[32m0\u001b[39m, \u001b[32m0\u001b[39m))" ] }, "execution_count": 62, "metadata": {}, "output_type": "execute_result" } ], "source": [ "val input1_k = 1\n", "val output1 = List( (15,14), (18,19), (0,0) )\n", "assert(filterPairsByBound(input1_l, input1_k) == output1)" ] }, { "cell_type": "markdown", "id": "b55b49e4-2a4b-4dc6-80de-c600151fcf5a", "metadata": {}, "source": [ "With `k == 4`, the expected output is as follows:" ] }, { "cell_type": "code", "execution_count": 63, "id": "d05fe5b9", "metadata": {}, "outputs": [ { "data": { "text/plain": [ "\u001b[36minput2_k\u001b[39m: \u001b[32mInt\u001b[39m = \u001b[32m4\u001b[39m\n", "\u001b[36moutput2\u001b[39m: \u001b[32mList\u001b[39m[(\u001b[32mInt\u001b[39m, \u001b[32mInt\u001b[39m)] = \u001b[33mList\u001b[39m((\u001b[32m1\u001b[39m, \u001b[32m5\u001b[39m), (\u001b[32m15\u001b[39m, \u001b[32m14\u001b[39m), (\u001b[32m18\u001b[39m, \u001b[32m19\u001b[39m), (\u001b[32m0\u001b[39m, \u001b[32m0\u001b[39m))" ] }, "execution_count": 63, "metadata": {}, "output_type": "execute_result" } ], "source": [ "val input2_k = 4\n", "val output2 = List( (1, 5), (15, 14), (18, 19), (0,0) )\n", "assert(filterPairsByBound(input1_l, input2_k) == output2)" ] }, { "cell_type": "markdown", "id": "984c452b-5302-48a6-8fe1-e1a1ff22cbaa", "metadata": {}, "source": [ "#### Notes\n", "\n", "- Your function must be called `filterPairsByBound` with two\n", " arguments: (1) a list of pairs of integers, and (2) the $k$ value.\n", " It must return a list of pairs of integers.\n", "- You can use `for`-loops (or `foreach`) and the following operators\n", " for concatenating elements to a list:\n", " - `:+` appends an element to the back of a list.\n", " - `:::` concatenates two lists together.\n", " - `::` prepends an element to the front of a list.\n", "- You can use the `List` API method `reverse`. You may also use the\n", " `Int` `abs` method to obtain the absolute value of an integer (or\n", " use your `abs` function above).\n", "- You should not use any other `List` API functions including\n", " `filter`, `map`, `foldLeft`, `foldRight`, etc. Plenty of time to\n", " learn them properly later on.\n", "- Do not try to convert your list to an array or vector so that you\n", " can mutate it.\n", "- If you are unable to solve the problem without violating the\n", " restrictions or unsure, ask us.\n", "- You will need to use `var` given the above restrictions.\n", "\n", "#### Hints\n", "\n", "- In Scala, pairs of integers have the type `(Int, Int)`.\n", "- A list containing pairs of integers has the type `List[(Int, Int)]`.\n", "- Recall from the notes, here is how one iterates over the elements of\n", " a list in Scala:" ] }, { "cell_type": "code", "execution_count": 64, "id": "757f5f83", "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "1\n", "2\n", "3\n" ] }, { "data": { "text/plain": [ "\u001b[36mlist\u001b[39m: \u001b[32mList\u001b[39m[\u001b[32mInt\u001b[39m] = \u001b[33mList\u001b[39m(\u001b[32m1\u001b[39m, \u001b[32m2\u001b[39m, \u001b[32m3\u001b[39m)" ] }, "execution_count": 64, "metadata": {}, "output_type": "execute_result" } ], "source": [ "val list = List(1, 2, 3)\n", "\n", "for (elt <- list) {\n", " // do stuff with elt\n", " println(elt)\n", "}" ] }, { "cell_type": "markdown", "id": "e8155fd8-8f76-4131-86e7-3d9bc3f583b4", "metadata": {}, "source": [ "- Append an element to the end of a list and update a `var`:" ] }, { "cell_type": "code", "execution_count": 65, "id": "d20926f0", "metadata": {}, "outputs": [ { "data": { "text/html": [ "
resultList: List[Int] = List(1, 2, 3, 42)\n",
"elt: Int = 42
\n",
"resultList: List[Int] = List(1, 2, 3, 42)\n",
"elt: Int = 42
\n",
"resultList: List[Int] = List(42, 1, 2, 3)\n",
"elt: Int = 42
\n",
"