diff options
Diffstat (limited to 'higher-order-functions-exercise.ipynb')
-rw-r--r-- | higher-order-functions-exercise.ipynb | 1576 |
1 files changed, 1576 insertions, 0 deletions
diff --git a/higher-order-functions-exercise.ipynb b/higher-order-functions-exercise.ipynb new file mode 100644 index 0000000..454095c --- /dev/null +++ b/higher-order-functions-exercise.ipynb @@ -0,0 +1,1576 @@ +{ + "cells": [ + { + "cell_type": "markdown", + "id": "c6d055b3", + "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": 51, + "id": "7d37a207", + "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": 51, + "metadata": {}, + "output_type": "execute_result" + } + ], + "source": [ + "val NAME = \"Jack Sangdahl\"\n", + "val COLLABORATORS = \"N/A\"" + ] + }, + { + "cell_type": "markdown", + "id": "d2cb60f5", + "metadata": {}, + "source": [ + "---" + ] + }, + { + "cell_type": "markdown", + "id": "7e183df6-99f9-4b1a-9801-d9c76f2b1ae8", + "metadata": {}, + "source": [ + "# Exercise: Higher-Order Functions\n", + "\n", + "<!-- 3 Expressions -->\n", + "\n", + "<!-- 4 Binding and Scope -->\n", + "\n", + "<!-- 8 Recursion -->\n", + "\n", + "<!-- 9 Inductive Data Types -->\n", + "\n", + "<!-- 11 Concrete Syntax -->\n", + "\n", + "<!-- 12 Abstract Syntax and Parsing -->\n", + "\n", + "<!-- 13 Exercise: Syntax -->\n", + "\n", + "<!-- 14 Static Scoping -->\n", + "\n", + "<!-- 15 Judgments -->\n", + "\n", + "<!-- 16 Variables, Basic Values, and Judgments Lab -->\n", + "\n", + "<!-- 18 Operational Semantics -->\n", + "\n", + "<!-- 19 Functions and Dynamic Scoping -->\n", + "\n", + "<!-- 20 Big-Step Exercise -->\n", + "\n", + "<!-- 21 Evaluation Order -->\n", + "\n", + "### Learning Goals\n", + "\n", + "The primary learning goal of this exercise is to get experience\n", + "programming with higher-order functions.\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. Make sure that you remove the `???`\n", + "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", + "### Imports" + ] + }, + { + "cell_type": "code", + "execution_count": 52, + "id": "7047114a", + "metadata": { + "deletable": false, + "editable": false, + "nbgrader": { + "cell_type": "code", + "checksum": "afc1ca0eb6ddf4e8f942a9b59b4d2e8e", + "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[36mpassed\u001b[39m\n", + "defined \u001b[32mfunction\u001b[39m \u001b[36mtest\u001b[39m" + ] + }, + "execution_count": 52, + "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): Unit = suite.execute(stats = true)\n", + "def assertPassed(suite: Suite): Unit =\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 passed(points: Int): Unit = {\n", + " require(points >=0)\n", + " if (points == 1) println(\"*** π Tests Passed (1 point) ***\")\n", + " else println(s\"*** π Tests Passed ($points points) ***\")\n", + "}\n", + "def test(suite: Suite, points: Int): Unit = {\n", + " report(suite)\n", + " assertPassed(suite)\n", + " passed(points)\n", + "}" + ] + }, + { + "cell_type": "markdown", + "id": "6b6ea94a-7824-4ed5-9614-534a797b0cb0", + "metadata": {}, + "source": [ + "## Collections\n", + "\n", + "When working with and organizing data, we primarily use collections from\n", + "Scalaβs standard library. One of the most fundamental operations that\n", + "one needs to perform with a collection is to iterate over the elements.\n", + "Like many other languages with first-class functions (e.g., Python, ML),\n", + "the Scala library provides various iteration operations via\n", + "*higher-order functions*. Higher-order functions are functions that take\n", + "functions as parameters. The function parameters are often called\n", + "*callbacks*, and for collections, they typically specify what the\n", + "library client wants to do for each element. We have seen examples of\n", + "these functions in class. In the following questions, we practice both\n", + "writing such higher-order functions in a library and using them as a\n", + "client.\n", + "\n", + "### Lists\n", + "\n", + "First, we will implement functions that eliminate consecutive duplicates\n", + "of list elements. If a list contains repeated elements they should be\n", + "replaced with a single copy of the element. The order of the elements\n", + "should not be changed. For example, the following\n", + "`List(1, 2, 2, 3, 3, 3)` should be converted to `List(1,2,3)`.\n", + "\n", + "<span class=\"theorem-title\">**Exercise 1 (5 points)**</span> Write a\n", + "function `compressRec` that implements this behavior. Implement the\n", + "function by direct recursion (e.g., pattern match on `l` and call\n", + "`compressRec` recursively). Do not call any `List` library methods.\n", + "\n", + "**Edit this cell:**" + ] + }, + { + "cell_type": "code", + "execution_count": 53, + "id": "ccffe3bf", + "metadata": { + "deletable": false, + "nbgrader": { + "cell_type": "code", + "checksum": "92e68b3abc6873aeb3256c3a889785b9", + "grade": false, + "grade_id": "compress-rec-answer", + "locked": false, + "schema_version": 3, + "solution": true, + "task": false + } + }, + "outputs": [ + { + "data": { + "text/plain": [ + "defined \u001b[32mfunction\u001b[39m \u001b[36mcompressRec\u001b[39m" + ] + }, + "execution_count": 53, + "metadata": {}, + "output_type": "execute_result" + } + ], + "source": [ + "def compressRec[A](l: List[A]): List[A] = l match {\n", + " case Nil | _ :: Nil => l\n", + " case h1 :: (t1 @ (h2 :: _)) => \n", + " if (h1 == h2) compressRec(t1)\n", + " else h1:: compressRec(t1)\n", + "}" + ] + }, + { + "cell_type": "markdown", + "id": "94a281c0-ccd2-4fb8-9daa-53a6e4e1dc9e", + "metadata": {}, + "source": [ + "#### Notes\n", + "\n", + "- This exercise is from [Ninety-Nine Scala\n", + " Problems](http://aperiodic.net/phil/scala/s-99/). Some sample\n", + " solutions are given there, which you are welcome to view. However,\n", + " we *strongly* recommend you attempt this exercise before looking\n", + " there. The purpose of the exercise is to get some practice for the\n", + " later part of this homework. Note that the solutions there do not\n", + " satisfy the requirements here, as they use library functions. If at\n", + " some point you feel like you need more practice with collections,\n", + " this site is a good resource.\n", + "\n", + "#### Tests" + ] + }, + { + "cell_type": "code", + "execution_count": 54, + "id": "24666dbc", + "metadata": { + "deletable": false, + "editable": false, + "nbgrader": { + "cell_type": "code", + "checksum": "37105b713cdf2fd778ba04c25e81034b", + "grade": true, + "grade_id": "eval-compress-rec-tester", + "locked": true, + "points": 5, + "schema_version": 3, + "solution": false, + "task": false + } + }, + "outputs": [ + { + "name": "stdout", + "output_type": "stream", + "text": [ + "\u001b[36mRun starting. Expected test count is: 1\u001b[0m\n", + "\u001b[32mcmd54$Helper$$anon$1:\u001b[0m\n", + "\u001b[32mcompressRec\u001b[0m\n", + "\u001b[32m- should Test Case 1\u001b[0m\n", + "\u001b[36mRun completed in 1 millisecond.\u001b[0m\n", + "\u001b[36mTotal number of tests run: 1\u001b[0m\n", + "\u001b[36mSuites: completed 1, aborted 0\u001b[0m\n", + "\u001b[36mTests: succeeded 1, failed 0, canceled 0, ignored 0, pending 0\u001b[0m\n", + "\u001b[32mAll tests passed.\u001b[0m\n", + "*** π Tests Passed (5 points) ***\n" + ] + } + ], + "source": [ + "test(new AnyFlatSpec {\n", + " val l1 = List(1, 2, 2, 3, 3, 3)\n", + " val r1 = List(1, 2, 3)\n", + "\n", + " \"compressRec\" should \"Test Case 1\" in { assertResult( r1 ) { compressRec(l1) } }\n", + "}, 5)" + ] + }, + { + "cell_type": "markdown", + "id": "a33fc3ee-b0ce-496f-acfb-960b0a2dc115", + "metadata": {}, + "source": [ + "<span class=\"theorem-title\">**Exercise 2 (5 points)**</span> Write a\n", + "different function `compressFold` that re-implements the behavior of\n", + "`compressRec` using the `foldRight` method from the `List` library. The\n", + "call to `foldRight` has been provided for you. Do not call\n", + "`compressFold` recursively or any other `List` library methods.\n", + "\n", + "**Edit this cell:**" + ] + }, + { + "cell_type": "code", + "execution_count": 55, + "id": "cfb2b5e2", + "metadata": { + "deletable": false, + "nbgrader": { + "cell_type": "code", + "checksum": "3c8e6b1a366ae91df01dc1de5be522b2", + "grade": false, + "grade_id": "compress-fold-answer", + "locked": false, + "schema_version": 3, + "solution": true, + "task": false + } + }, + "outputs": [ + { + "data": { + "text/plain": [ + "defined \u001b[32mfunction\u001b[39m \u001b[36mcompressFold\u001b[39m" + ] + }, + "execution_count": 55, + "metadata": {}, + "output_type": "execute_result" + } + ], + "source": [ + "def compressFold[A](l: List[A]): List[A] = l.foldRight(Nil: List[A]){ (h, acc) => \n", + " acc match {\n", + " case Nil => h :: Nil\n", + " case x :: _ =>\n", + " if (h != x) h :: acc\n", + " else acc\n", + " }\n", + "}" + ] + }, + { + "cell_type": "markdown", + "id": "c0365e1b-8f3f-4069-96e0-e486d2a4ec01", + "metadata": {}, + "source": [ + "#### Tests" + ] + }, + { + "cell_type": "code", + "execution_count": 56, + "id": "4b823624", + "metadata": { + "deletable": false, + "editable": false, + "nbgrader": { + "cell_type": "code", + "checksum": "1cc99e752a01d9179e59e4d37c41c8ee", + "grade": true, + "grade_id": "eval-compress-fold-tester", + "locked": true, + "points": 5, + "schema_version": 3, + "solution": false, + "task": false + } + }, + "outputs": [ + { + "name": "stdout", + "output_type": "stream", + "text": [ + "\u001b[36mRun starting. Expected test count is: 1\u001b[0m\n", + "\u001b[32mcmd56$Helper$$anon$1:\u001b[0m\n", + "\u001b[32mcompressFold\u001b[0m\n", + "\u001b[32m- should Test Case 1\u001b[0m\n", + "\u001b[36mRun completed in 1 millisecond.\u001b[0m\n", + "\u001b[36mTotal number of tests run: 1\u001b[0m\n", + "\u001b[36mSuites: completed 1, aborted 0\u001b[0m\n", + "\u001b[36mTests: succeeded 1, failed 0, canceled 0, ignored 0, pending 0\u001b[0m\n", + "\u001b[32mAll tests passed.\u001b[0m\n", + "*** π Tests Passed (5 points) ***\n" + ] + } + ], + "source": [ + "test(new AnyFlatSpec {\n", + " val l1 = List(1, 2, 2, 3, 3, 3)\n", + " val r1 = List(1, 2, 3)\n", + "\n", + " \"compressFold\" should \"Test Case 1\" in { assertResult( r1 ) { compressFold(l1) } }\n", + "}, 5)" + ] + }, + { + "cell_type": "markdown", + "id": "c11a6086-6902-40e5-8395-c4c604fb3675", + "metadata": {}, + "source": [ + "<span class=\"theorem-title\">**Exercise 3 (5 points)**</span> Explain in\n", + "1β2 sentences the similarities and differences between your two\n", + "implementations: `compressRec` and `compressFold`.\n", + "\n", + "**Edit this cell:**" + ] + }, + { + "cell_type": "markdown", + "id": "d056d0b1-eac0-4df7-a5a7-230719f41328", + "metadata": { + "deletable": false, + "nbgrader": { + "cell_type": "markdown", + "checksum": "b62196190ebfcba2945446be01a232b6", + "grade": true, + "grade_id": "explain-compress", + "locked": false, + "points": 5, + "schema_version": 3, + "solution": true, + "task": false + } + }, + "source": [ + "In terms of similarities, these functions both remove consecutive duplicates from a list. `compressRec` uses direct recursion to iterate through the list and construct the result, whereas `compressFold` uses a higher-order function `foldRight` to accumulate the result without explicit recursion." + ] + }, + { + "cell_type": "markdown", + "id": "7e27db0c-4a97-435c-b53e-c780ae1e1753", + "metadata": {}, + "source": [ + "<span class=\"theorem-title\">**Exercise 4 (5 points)**</span> Implement a\n", + "higher-order recursive function `mapFirst` that finds the first element\n", + "of `l: List[A]` where `f: A => Option[A]` applied to it returns\n", + "`Some(a)` for some value `a`. The function should replace that element\n", + "with `a` and leave `l` the same everywhere else. For example,\n", + "\n", + "``` scala\n", + "mapFirst(List(1,2,-3,4,-5)) { i => if (i < 0) Some(-i) else None } \n", + "```\n", + "\n", + "should result in `List[Int] = List(1, 2, 3, 4, -5)`.\n", + "\n", + "**Edit this cell:**" + ] + }, + { + "cell_type": "code", + "execution_count": 57, + "id": "4490826a", + "metadata": { + "deletable": false, + "nbgrader": { + "cell_type": "code", + "checksum": "c5bfc2453712c057957b0644045ede51", + "grade": false, + "grade_id": "map-first-answer", + "locked": false, + "schema_version": 3, + "solution": true, + "task": false + } + }, + "outputs": [ + { + "data": { + "text/plain": [ + "defined \u001b[32mfunction\u001b[39m \u001b[36mmapFirst\u001b[39m" + ] + }, + "execution_count": 57, + "metadata": {}, + "output_type": "execute_result" + } + ], + "source": [ + "def mapFirst[A](l: List[A])(f: A => Option[A]): List[A] = l match {\n", + " case Nil => Nil\n", + " case h :: t => \n", + " f(h) match {\n", + " case None => h :: mapFirst(t)(f)\n", + " case Some(a) => a :: t\n", + " }\n", + "}" + ] + }, + { + "cell_type": "markdown", + "id": "29a2b79b-d276-475e-a560-1a1330a16fd2", + "metadata": {}, + "source": [ + "#### Tests" + ] + }, + { + "cell_type": "code", + "execution_count": 58, + "id": "e5973775", + "metadata": { + "deletable": false, + "editable": false, + "nbgrader": { + "cell_type": "code", + "checksum": "ae49d2319356b384b728df4baa3e61a2", + "grade": true, + "grade_id": "eval-map-first-tester", + "locked": true, + "points": 5, + "schema_version": 3, + "solution": false, + "task": false + } + }, + "outputs": [ + { + "name": "stdout", + "output_type": "stream", + "text": [ + "\u001b[36mRun starting. Expected test count is: 1\u001b[0m\n", + "\u001b[32mcmd58$Helper$$anon$1:\u001b[0m\n", + "\u001b[32mmapFirst\u001b[0m\n", + "\u001b[32m- should Test Case 1\u001b[0m\n", + "\u001b[36mRun completed in 1 millisecond.\u001b[0m\n", + "\u001b[36mTotal number of tests run: 1\u001b[0m\n", + "\u001b[36mSuites: completed 1, aborted 0\u001b[0m\n", + "\u001b[36mTests: succeeded 1, failed 0, canceled 0, ignored 0, pending 0\u001b[0m\n", + "\u001b[32mAll tests passed.\u001b[0m\n", + "*** π Tests Passed (5 points) ***\n" + ] + } + ], + "source": [ + "test(new AnyFlatSpec {\n", + " val l1 = List(1, 2, -3, 4, -5)\n", + " val r1 = List(1, 2, 3, 4, -5)\n", + "\n", + " \"mapFirst\" should \"Test Case 1\" in { \n", + " assertResult(r1) {\n", + " mapFirst(l1) { (i: Int) => if (i < 0) Some(-i) else None }\n", + " }\n", + " }\n", + "}, 5)" + ] + }, + { + "cell_type": "markdown", + "id": "d3abe7ce-8cd8-47f4-a2c2-768c5c5fc69a", + "metadata": {}, + "source": [ + "<span class=\"theorem-title\">**Exercise 5 (5 points)**</span> Write a\n", + "function `composeMap` that sequentially applies a list of functions of\n", + "type `A => A` to all the elements of a `List[A]`. For example, if we\n", + "have a list of functions `List(f1, f2, f3)`, and a list `List(a, b)`, we\n", + "want to output `List(f3(f2(f1(a))), f3(f2(f1(b))))`.\n", + "\n", + "**Edit this cell:**" + ] + }, + { + "cell_type": "code", + "execution_count": 59, + "id": "9afd3378", + "metadata": { + "deletable": false, + "nbgrader": { + "cell_type": "code", + "checksum": "abeb90b3fb6318d3968957d5c4597d1f", + "grade": false, + "grade_id": "compose-map-answer", + "locked": false, + "schema_version": 3, + "solution": true, + "task": false + } + }, + "outputs": [ + { + "data": { + "text/plain": [ + "defined \u001b[32mfunction\u001b[39m \u001b[36mcomposeMap\u001b[39m" + ] + }, + "execution_count": 59, + "metadata": {}, + "output_type": "execute_result" + } + ], + "source": [ + "def composeMap[A](functions: List[A => A])(l: List[A]): List[A] = {\n", + " l.map(h => functions.foldRight(h)( (f, e) => f(e)))\n", + "}" + ] + }, + { + "cell_type": "markdown", + "id": "c5608fc2-a6dc-40d2-a530-13f0185e2286", + "metadata": {}, + "source": [ + "#### Tests" + ] + }, + { + "cell_type": "code", + "execution_count": 60, + "id": "2fafb0b4", + "metadata": { + "deletable": false, + "editable": false, + "nbgrader": { + "cell_type": "code", + "checksum": "9adaca1df7b9f28b5ceba4853b61495e", + "grade": true, + "grade_id": "eval-compose-map-tester", + "locked": true, + "points": 5, + "schema_version": 3, + "solution": false, + "task": false + } + }, + "outputs": [ + { + "name": "stdout", + "output_type": "stream", + "text": [ + "\u001b[36mRun starting. Expected test count is: 1\u001b[0m\n", + "\u001b[32mcmd60$Helper$$anon$1:\u001b[0m\n", + "\u001b[32mcomposeMap\u001b[0m\n", + "\u001b[32m- should Test Case 1\u001b[0m\n", + "\u001b[36mRun completed in 1 millisecond.\u001b[0m\n", + "\u001b[36mTotal number of tests run: 1\u001b[0m\n", + "\u001b[36mSuites: completed 1, aborted 0\u001b[0m\n", + "\u001b[36mTests: succeeded 1, failed 0, canceled 0, ignored 0, pending 0\u001b[0m\n", + "\u001b[32mAll tests passed.\u001b[0m\n", + "*** π Tests Passed (5 points) ***\n" + ] + } + ], + "source": [ + "test(new AnyFlatSpec {\n", + " def plusOne(x: Int): Int = x + 1\n", + " def square(x: Int): Int = x * x\n", + " def timesThree(x: Int): Int = x * 3\n", + "\n", + " val l1 = List(1, 2, 3)\n", + " val r1 = List(10, 37, 82)\n", + " val fs: List[Int => Int] = List(plusOne, square, timesThree)\n", + "\n", + " \"composeMap\" should \"Test Case 1\" in { assertResult(r1) { composeMap(fs)(l1) } }\n", + "}, 5)" + ] + }, + { + "cell_type": "markdown", + "id": "f799539c-e013-4c36-8f76-d5f9c2ac3358", + "metadata": {}, + "source": [ + "### Maps\n", + "\n", + "Recall the `Map[A, B]` data structure from class. Also, recall the\n", + "higher-order function `map`. To avoid confusion we will use the upper\n", + "case `Map` to refer to the type, and the lowercase `map` to refer to the\n", + "higher-order function.\n", + "\n", + "<span class=\"theorem-title\">**Exercise 6 (5 points)**</span> Implement a\n", + "function `mapValues` that takes a `Map[A,B]` and a callback function\n", + "`f: B => C`, that applies `f` to all the values in the `Map`. Your\n", + "function should use the Scala collections `map` method. Do not use the\n", + "standard library method `mapValues` on `Map` (however, note that the\n", + "behavior of your function should be exactly the same as the `mapValues`\n", + "standard library method).\n", + "\n", + "**Edit this cell:**" + ] + }, + { + "cell_type": "code", + "execution_count": 61, + "id": "1f6f4c15", + "metadata": { + "deletable": false, + "nbgrader": { + "cell_type": "code", + "checksum": "943db2a02802c5f62c4a25aefb2e0fab", + "grade": false, + "grade_id": "update-map-answer", + "locked": false, + "schema_version": 3, + "solution": true, + "task": false + } + }, + "outputs": [ + { + "data": { + "text/plain": [ + "defined \u001b[32mfunction\u001b[39m \u001b[36mmapValues\u001b[39m" + ] + }, + "execution_count": 61, + "metadata": {}, + "output_type": "execute_result" + } + ], + "source": [ + "def mapValues[A, B, C](m: Map[A, B])(f: B => C): Map[A, C] = m.map {\n", + " case (key, value) => key -> f(value)\n", + "}" + ] + }, + { + "cell_type": "markdown", + "id": "1d23b72e-12ed-4e87-8cc3-9f894517e08a", + "metadata": {}, + "source": [ + "#### Tests" + ] + }, + { + "cell_type": "code", + "execution_count": 62, + "id": "6fbeb162", + "metadata": { + "deletable": false, + "editable": false, + "nbgrader": { + "cell_type": "code", + "checksum": "a4caabf134684fad42f83e85812648f4", + "grade": true, + "grade_id": "eval-update-map-tester", + "locked": true, + "points": 5, + "schema_version": 3, + "solution": false, + "task": false + } + }, + "outputs": [ + { + "name": "stdout", + "output_type": "stream", + "text": [ + "\u001b[36mRun starting. Expected test count is: 1\u001b[0m\n", + "\u001b[32mcmd62$Helper$$anon$1:\u001b[0m\n", + "\u001b[32mmapValues\u001b[0m\n", + "\u001b[32m- should Test Case 1\u001b[0m\n", + "\u001b[36mRun completed in 1 millisecond.\u001b[0m\n", + "\u001b[36mTotal number of tests run: 1\u001b[0m\n", + "\u001b[36mSuites: completed 1, aborted 0\u001b[0m\n", + "\u001b[36mTests: succeeded 1, failed 0, canceled 0, ignored 0, pending 0\u001b[0m\n", + "\u001b[32mAll tests passed.\u001b[0m\n", + "*** π Tests Passed (5 points) ***\n" + ] + } + ], + "source": [ + "test(new AnyFlatSpec {\n", + " val m1 = Map(\"a\" -> 1, \"b\" -> 2, \"c\" -> 3)\n", + " val r1 = Map(\"a\" -> 1, \"b\" -> 4, \"c\" -> 9)\n", + "\n", + " \"mapValues\" should \"Test Case 1\" in { \n", + " assertResult(r1) {\n", + " mapValues(m1) { (i: Int) => i * i }\n", + " }\n", + " }\n", + "}, 5)" + ] + }, + { + "cell_type": "markdown", + "id": "a55bede4-74af-4a96-a943-97cb5e584e13", + "metadata": {}, + "source": [ + "<span class=\"theorem-title\">**Exercise 7 (5 points)**</span> As we\n", + "mentioned above, we just reimplemented `mapValues` using the `map`\n", + "method from the standard library. Earlier, we implemented higher-order\n", + "functions on `List`s recursively. Could we have implemented `mapValues`\n", + "on `Map`s recursively? If yes, give an example implementation. If no,\n", + "explain why we cannot, and what makes `Map` different from `List` in\n", + "this case.\n", + "\n", + "**Edit this cell:**" + ] + }, + { + "cell_type": "markdown", + "id": "d533e044-1102-4111-aca2-d89b56675e6b", + "metadata": { + "deletable": false, + "nbgrader": { + "cell_type": "markdown", + "checksum": "345e3429a34b13ba9693f3f9a0978bcd", + "grade": true, + "grade_id": "explain-map", + "locked": false, + "points": 5, + "schema_version": 3, + "solution": true, + "task": false + } + }, + "source": [ + "Yes, this could have been done recursively. The main difference between a `Map` and `List` is that a `Map` is an unordered key-value pair data structure, whereas a `List` is an ordered, linear sequence of elements. An example implementation is as follows:" + ] + }, + { + "cell_type": "code", + "execution_count": 63, + "id": "08af9ccd-4e2c-4061-a92d-7bd663685013", + "metadata": {}, + "outputs": [ + { + "data": { + "text/plain": [ + "defined \u001b[32mfunction\u001b[39m \u001b[36mmapValuesRecursive\u001b[39m" + ] + }, + "execution_count": 63, + "metadata": {}, + "output_type": "execute_result" + } + ], + "source": [ + "def mapValuesRecursive[A, B, C](m: Map[A, B])(f: B => C): Map[A, C] = {\n", + " if (m.isEmpty)\n", + " Map.empty\n", + " else {\n", + " val (k, v) = m.head\n", + " mapValuesRecursive(m.tail)(f) + (k -> f(v))\n", + " }\n", + "}" + ] + }, + { + "cell_type": "markdown", + "id": "4c81a60c-833e-402e-8729-262b1d3e1c85", + "metadata": {}, + "source": [ + "### Trees\n", + "\n", + "Recall the binary tree data type:" + ] + }, + { + "cell_type": "code", + "execution_count": 64, + "id": "4b674bde", + "metadata": {}, + "outputs": [ + { + "data": { + "text/plain": [ + "defined \u001b[32mtrait\u001b[39m \u001b[36mTree\u001b[39m\n", + "defined \u001b[32mobject\u001b[39m \u001b[36mEmpty\u001b[39m\n", + "defined \u001b[32mclass\u001b[39m \u001b[36mNode\u001b[39m" + ] + }, + "execution_count": 64, + "metadata": {}, + "output_type": "execute_result" + } + ], + "source": [ + "sealed trait Tree\n", + "case object Empty extends Tree\n", + "case class Node(l: Tree, d: Int, r: Tree) extends Tree" + ] + }, + { + "cell_type": "markdown", + "id": "e6714a92-bf33-4a9f-bb50-60081f14bfce", + "metadata": {}, + "source": [ + "<span class=\"theorem-title\">**Exercise 8 (10 points)**</span> Implement\n", + "a higher-order function `foldLeft` that performs an in-order traversal\n", + "of the input `t: Tree`, calling the callback `f` starting with `z` to\n", + "accumulate a result. For example, suppose the in-order traversal of the\n", + "input tree `t` yields the sequence of data values: $d_1,d_2,\\dots,d_n$.\n", + "Then, `foldLeft(t)(z)(f)` yields\n", + "$f(f(\\dots(f(f(z,d_1),d_2))\\dots d_{n-1}),d_n)$\n", + "\n", + "**Edit this cell:**" + ] + }, + { + "cell_type": "code", + "execution_count": 65, + "id": "e7faa101", + "metadata": { + "deletable": false, + "nbgrader": { + "cell_type": "code", + "checksum": "01a7fd4c23093ca596c8f5efe2b8a86b", + "grade": false, + "grade_id": "tree-foldleft-answer", + "locked": false, + "schema_version": 3, + "solution": true, + "task": false + } + }, + "outputs": [ + { + "data": { + "text/plain": [ + "defined \u001b[32mfunction\u001b[39m \u001b[36mfoldLeft\u001b[39m" + ] + }, + "execution_count": 65, + "metadata": {}, + "output_type": "execute_result" + } + ], + "source": [ + "def foldLeft[A](t: Tree)(z: A)(f: (A, Int) => A): A = {\n", + " def loop(acc: A, t: Tree): A = t match {\n", + " case Empty => acc\n", + " case Node(l, d, r) => \n", + " val leftAcc = loop(acc, l)\n", + " val currAcc = f(leftAcc, d)\n", + " loop(currAcc, r)\n", + " }\n", + " loop(z, t)\n", + "}" + ] + }, + { + "cell_type": "markdown", + "id": "45b0ef95-9430-4447-b091-c6e691310120", + "metadata": {}, + "source": [ + "We have provided a test client `sum` that computes the sum of all of the\n", + "data values in the tree using your `foldLeft` method, along with some\n", + "helper functions to build trees more easily. Feel free to use them to\n", + "write more test cases for your code." + ] + }, + { + "cell_type": "code", + "execution_count": 66, + "id": "d14dd60d", + "metadata": { + "deletable": false, + "editable": false, + "nbgrader": { + "cell_type": "code", + "checksum": "fd47c7f1d30d0afe0a08de165786fe94", + "grade": false, + "grade_id": "tree-foldleft-client", + "locked": true, + "schema_version": 3, + "solution": false, + "task": false + } + }, + "outputs": [ + { + "data": { + "text/plain": [ + "defined \u001b[32mfunction\u001b[39m \u001b[36msum\u001b[39m\n", + "defined \u001b[32mfunction\u001b[39m \u001b[36minsert\u001b[39m\n", + "defined \u001b[32mfunction\u001b[39m \u001b[36mtreeFromList\u001b[39m" + ] + }, + "execution_count": 66, + "metadata": {}, + "output_type": "execute_result" + } + ], + "source": [ + "// An example use of foldLeft\n", + "def sum(t: Tree): Int = foldLeft(t)(0){ (acc, d) => acc + d }\n", + "\n", + "// In-order insertion into a binary search tree\n", + "def insert(t: Tree, n: Int): Tree = t match {\n", + " case Empty => Node(Empty, n, Empty)\n", + " case Node(l, d, r) =>\n", + " if (n < d) Node(insert(l, n), d, r) else Node(l, d, insert(r, n))\n", + "}\n", + "\n", + "// Create a tree from a list. An example use of the List.foldLeft method.\n", + "def treeFromList(l: List[Int]): Tree =\n", + " l.foldLeft(Empty: Tree){ (acc, i) => insert(acc, i) }" + ] + }, + { + "cell_type": "markdown", + "id": "d3bc3e75-025a-4e5f-9618-ff3ef0055ccb", + "metadata": {}, + "source": [ + "#### Tests" + ] + }, + { + "cell_type": "code", + "execution_count": 67, + "id": "ffaf0123", + "metadata": { + "deletable": false, + "editable": false, + "nbgrader": { + "cell_type": "code", + "checksum": "bd11a15eb82027b8f34c1cae8d4c29bc", + "grade": true, + "grade_id": "eval-fold-left-tester", + "locked": true, + "points": 10, + "schema_version": 3, + "solution": false, + "task": false + } + }, + "outputs": [ + { + "name": "stdout", + "output_type": "stream", + "text": [ + "\u001b[36mRun starting. Expected test count is: 3\u001b[0m\n", + "\u001b[32mcmd67$Helper$$anon$1:\u001b[0m\n", + "\u001b[32mfoldLeft\u001b[0m\n", + "\u001b[32m- should Test Case 1\u001b[0m\n", + "\u001b[32m- should Test Case 2\u001b[0m\n", + "\u001b[32m- should Test Case 3\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", + "*** π Tests Passed (10 points) ***\n" + ] + } + ], + "source": [ + "test(new AnyFlatSpec {\n", + " val t1 = treeFromList(List(1, 2, 3))\n", + " \"foldLeft\" should \"Test Case 1\" in { assertResult(6) { sum(t1) } }\n", + "\n", + " val l2 = List(3, 4, 8, 2, 1, 7, 10)\n", + " val sortl2 = l2.sorted\n", + " val t2 = treeFromList(l2)\n", + "\n", + " def rev(acc: List[Int], x: Int): List[Int] = x :: acc\n", + " def prod(acc: Int, x: Int): Int = x * acc\n", + "\n", + " it should \"Test Case 2\" in {\n", + " assertResult( sortl2.foldLeft(Nil: List[Int])(rev) ) {\n", + " foldLeft(t2)(Nil: List[Int])(rev)\n", + " }\n", + " }\n", + "\n", + " it should \"Test Case 3\" in {\n", + " assertResult( l2.foldLeft(1)(prod) ) {\n", + " foldLeft(t2)(1)(prod)\n", + " }\n", + " }\n", + "\n", + "}, 10)" + ] + }, + { + "cell_type": "markdown", + "id": "f5b47cb0-9f83-4f25-857a-8d61bdc93ac3", + "metadata": {}, + "source": [ + "<span class=\"theorem-title\">**Exercise 9 (10 points)**</span> Using your\n", + "`foldLeft` function, write a client function `strictlyOrdered` that\n", + "checks if the data values of an in-order traversal of `t` are in\n", + "strictly ascending order. For example, suppose the in-order traversal of\n", + "the input tree `t` yields the sequence of data values:\n", + "$d_1,d_2,\\dots,d_n$, the `strictlyOrdered` should return `true` iff\n", + "$d_1 < d_2 < \\dots < d_n$.\n", + "\n", + "**Edit this cell:**" + ] + }, + { + "cell_type": "code", + "execution_count": 68, + "id": "6f839e9c", + "metadata": { + "deletable": false, + "nbgrader": { + "cell_type": "code", + "checksum": "aebc268efefe554f4e2fb9721df67464", + "grade": false, + "grade_id": "tree-strictly-ordered-answer", + "locked": false, + "schema_version": 3, + "solution": true, + "task": false + } + }, + "outputs": [ + { + "data": { + "text/plain": [ + "defined \u001b[32mfunction\u001b[39m \u001b[36mstrictlyOrdered\u001b[39m" + ] + }, + "execution_count": 68, + "metadata": {}, + "output_type": "execute_result" + } + ], + "source": [ + "def strictlyOrdered(t: Tree): Boolean = {\n", + " val (b, _) = foldLeft(t)((true, None: Option[Int])) {\n", + " case ((true, None), d) => (true, Some(d))\n", + " case ((true, Some(prev)), d) if d > prev => (true, Some(d))\n", + " case _ => (false, None)\n", + " }\n", + " b\n", + "}" + ] + }, + { + "cell_type": "markdown", + "id": "33c18a55-90c0-4408-8074-f2f7c66668f6", + "metadata": {}, + "source": [ + "#### Tests" + ] + }, + { + "cell_type": "code", + "execution_count": 69, + "id": "0a029a26", + "metadata": { + "deletable": false, + "editable": false, + "nbgrader": { + "cell_type": "code", + "checksum": "f5349c102e6a628f88e43c633f2b79d5", + "grade": true, + "grade_id": "eval-strictly-ordered-tester", + "locked": true, + "points": 10, + "schema_version": 3, + "solution": false, + "task": false + } + }, + "outputs": [ + { + "name": "stdout", + "output_type": "stream", + "text": [ + "\u001b[36mRun starting. Expected test count is: 5\u001b[0m\n", + "\u001b[32mcmd69$Helper$$anon$1:\u001b[0m\n", + "\u001b[32mstrictlyOrdered\u001b[0m\n", + "\u001b[32m- should Test Case 1\u001b[0m\n", + "\u001b[32m- should Test Case 2\u001b[0m\n", + "\u001b[32m- should Test Case 3\u001b[0m\n", + "\u001b[32m- should Test Case 4\u001b[0m\n", + "\u001b[32m- should Test Case 5\u001b[0m\n", + "\u001b[36mRun completed in 1 millisecond.\u001b[0m\n", + "\u001b[36mTotal number of tests run: 5\u001b[0m\n", + "\u001b[36mSuites: completed 1, aborted 0\u001b[0m\n", + "\u001b[36mTests: succeeded 5, failed 0, canceled 0, ignored 0, pending 0\u001b[0m\n", + "\u001b[32mAll tests passed.\u001b[0m\n", + "*** π Tests Passed (10 points) ***\n" + ] + } + ], + "source": [ + "test(new AnyFlatSpec {\n", + " \"strictlyOrdered\" should \"Test Case 1\" in { assert(!strictlyOrdered(treeFromList(List(1,1,2)))) }\n", + " it should \"Test Case 2\" in { assert(strictlyOrdered(treeFromList(List(1,2)))) }\n", + " it should \"Test Case 3\" in { assert(!strictlyOrdered(treeFromList(List(-1,0,1,1,2)))) }\n", + " it should \"Test Case 4\" in { assert(!strictlyOrdered(treeFromList(List(2,1,2,3,4)))) }\n", + " it should \"Test Case 5\" in { assert(strictlyOrdered(treeFromList(List(1,2,3,4,5)))) }\n", + "}, 10)" + ] + }, + { + "cell_type": "markdown", + "id": "a08913be-7d42-468a-a9f6-8ea4e86e7fe1", + "metadata": {}, + "source": [ + "Now, we will write a higher-order function that uses our recent\n", + "higher-order functions as a client.\n", + "\n", + "<span class=\"theorem-title\">**Exercise 10 (5 points)**</span> Implement\n", + "a function `foldLeftTrees` that take as input a `lt: List[Tree]`, and\n", + "applies a callback `f` to all of their nodes in-order (of both the\n", + "`List` and the nested `Tree`s) starting with initial value `z` to\n", + "accumulate a result.\n", + "\n", + "For example, calling `foldLeftTrees` on\n", + "\n", + "``` scala\n", + "val lt = \n", + " List(\n", + " Node(Node(Empty, 1, Empty), 2, Node(Empty, 3, Empty)),\n", + " Node(Node(Empty, 4, Empty), 5, Node(Empty, 6, Empty))\n", + " )\n", + "```\n", + "\n", + "<pre><span class=\"ansi-cyan-fg\">lt</span>: <span class=\"ansi-green-fg\">List</span>[<span class=\"ansi-green-fg\">Node</span>] = <span class=\"ansi-yellow-fg\">List</span>(\n", + " <span class=\"ansi-yellow-fg\">Node</span>(\n", + " l = <span class=\"ansi-yellow-fg\">Node</span>(l = Empty, d = <span class=\"ansi-green-fg\">1</span>, r = Empty),\n", + " d = <span class=\"ansi-green-fg\">2</span>,\n", + " r = <span class=\"ansi-yellow-fg\">Node</span>(l = Empty, d = <span class=\"ansi-green-fg\">3</span>, r = Empty)\n", + " ),\n", + " <span class=\"ansi-yellow-fg\">Node</span>(\n", + " l = <span class=\"ansi-yellow-fg\">Node</span>(l = Empty, d = <span class=\"ansi-green-fg\">4</span>, r = Empty),\n", + " d = <span class=\"ansi-green-fg\">5</span>,\n", + " r = <span class=\"ansi-yellow-fg\">Node</span>(l = Empty, d = <span class=\"ansi-green-fg\">6</span>, r = Empty)\n", + " )\n", + ")</pre>\n", + "\n", + "and a function that sums integers should return `21`.\n", + "\n", + "Use only `foldLeft` on `Tree` that you have defined above and `foldLeft`\n", + "on `List[Tree]` provided in the Scala standard library.\n", + "\n", + "**Edit this cell:**" + ] + }, + { + "cell_type": "code", + "execution_count": 70, + "id": "d6e777bb", + "metadata": { + "deletable": false, + "nbgrader": { + "cell_type": "code", + "checksum": "156a49fe3a557c401f58e63fddec2525", + "grade": false, + "grade_id": "reduce-trees-answer", + "locked": false, + "schema_version": 3, + "solution": true, + "task": false + } + }, + "outputs": [ + { + "data": { + "text/plain": [ + "defined \u001b[32mfunction\u001b[39m \u001b[36mfoldLeftTrees\u001b[39m" + ] + }, + "execution_count": 70, + "metadata": {}, + "output_type": "execute_result" + } + ], + "source": [ + "def foldLeftTrees[B](lt: List[Tree])(z: B)(f: (B, Int) => B): B =\n", + " lt.foldLeft(z) {\n", + " (acc, t) => foldLeft(t)(acc)(f)\n", + " }" + ] + }, + { + "cell_type": "markdown", + "id": "d994727e-2506-454a-aff4-60109f2943e3", + "metadata": {}, + "source": [ + "#### Tests" + ] + }, + { + "cell_type": "code", + "execution_count": 71, + "id": "cb1dd3e8", + "metadata": { + "deletable": false, + "editable": false, + "nbgrader": { + "cell_type": "code", + "checksum": "882cdcfb3b78d41738ff798a0380050f", + "grade": true, + "grade_id": "eval-reduce-trees-tester", + "locked": true, + "points": 5, + "schema_version": 3, + "solution": false, + "task": false + } + }, + "outputs": [ + { + "name": "stdout", + "output_type": "stream", + "text": [ + "\u001b[36mRun starting. Expected test count is: 2\u001b[0m\n", + "\u001b[32mcmd71$Helper$$anon$1:\u001b[0m\n", + "\u001b[32mfoldLeftTrees\u001b[0m\n", + "\u001b[32m- should Test Case 1\u001b[0m\n", + "\u001b[32m- should reverse and flatten\u001b[0m\n", + "\u001b[36mRun completed in 1 millisecond.\u001b[0m\n", + "\u001b[36mTotal number of tests run: 2\u001b[0m\n", + "\u001b[36mSuites: completed 1, aborted 0\u001b[0m\n", + "\u001b[36mTests: succeeded 2, failed 0, canceled 0, ignored 0, pending 0\u001b[0m\n", + "\u001b[32mAll tests passed.\u001b[0m\n", + "*** π Tests Passed (5 points) ***\n" + ] + } + ], + "source": [ + "test(new AnyFlatSpec {\n", + " def sum(trees: List[Tree]): Int = foldLeftTrees(trees)(0){ (acc, d) => acc + d }\n", + "\n", + " val l1 = List(1, 2, 3)\n", + " val l2 = List(4, 5, 6)\n", + " val t1 = treeFromList(l1)\n", + " val t2 = treeFromList(l2)\n", + " val lt1 = List(t1, t2)\n", + "\n", + " val l1l2 = l1 ::: l2\n", + "\n", + " \"foldLeftTrees\" should \"Test Case 1\" in { assertResult(21){ sum(lt1) } }\n", + "\n", + " it should \"reverse and flatten\" in {\n", + " assertResult( l1l2.reverse ) { foldLeftTrees(lt1)(Nil: List[Int]){ (acc, i) => i :: acc } }\n", + " }\n", + "}, 5)" + ] + }, + { + "cell_type": "markdown", + "id": "3d685753-6dd5-4523-96dc-1a13b28b27a4", + "metadata": {}, + "source": [ + "## flatMap\n", + "\n", + "<span class=\"theorem-title\">**Exercise 11 (5 points)**</span> Recall the\n", + "`flatMap` function from class on `List`. Write a new function\n", + "`flatMapNoRec` that implements the same behavior without direct\n", + "recursion; instead, use `foldRight` and `:::`.\n", + "\n", + "**Edit this cell:**" + ] + }, + { + "cell_type": "code", + "execution_count": 72, + "id": "d968e550", + "metadata": { + "deletable": false, + "nbgrader": { + "cell_type": "code", + "checksum": "4735e78fbac810026d9023e023fd3c02", + "grade": false, + "grade_id": "flat-map-no-rec-answer", + "locked": false, + "schema_version": 3, + "solution": true, + "task": false + } + }, + "outputs": [ + { + "data": { + "text/plain": [ + "defined \u001b[32mfunction\u001b[39m \u001b[36mflatMapNoRec\u001b[39m" + ] + }, + "execution_count": 72, + "metadata": {}, + "output_type": "execute_result" + } + ], + "source": [ + "def flatMapNoRec[A, B](l: List[A])(f: A => List[B]): List[B] = \n", + " l.foldRight(List.empty[B])((h, acc) => f(h) ::: acc)" + ] + }, + { + "cell_type": "markdown", + "id": "8a421085-45ef-42e5-883b-3143d04b9c80", + "metadata": {}, + "source": [ + "#### Tests" + ] + }, + { + "cell_type": "code", + "execution_count": 73, + "id": "9b48e422", + "metadata": { + "deletable": false, + "editable": false, + "nbgrader": { + "cell_type": "code", + "checksum": "df083491ef6efe52e1295103f5b27c11", + "grade": true, + "grade_id": "eval-flat-map-no-rec-tester", + "locked": true, + "points": 5, + "schema_version": 3, + "solution": false, + "task": false + } + }, + "outputs": [ + { + "name": "stdout", + "output_type": "stream", + "text": [ + "\u001b[36mRun starting. Expected test count is: 1\u001b[0m\n", + "\u001b[32mcmd73$Helper$$anon$1:\u001b[0m\n", + "\u001b[32mflatMapNoRec\u001b[0m\n", + "\u001b[32m- should Test Case 1\u001b[0m\n", + "\u001b[36mRun completed in 1 millisecond.\u001b[0m\n", + "\u001b[36mTotal number of tests run: 1\u001b[0m\n", + "\u001b[36mSuites: completed 1, aborted 0\u001b[0m\n", + "\u001b[36mTests: succeeded 1, failed 0, canceled 0, ignored 0, pending 0\u001b[0m\n", + "\u001b[32mAll tests passed.\u001b[0m\n", + "*** π Tests Passed (5 points) ***\n" + ] + } + ], + "source": [ + "test(new AnyFlatSpec {\n", + " def duplicate[A](l: List[A]) = flatMapNoRec(l) { a => List(a, a) }\n", + "\n", + " val l1 = List(1, 2, 3)\n", + " val r1 = List(1, 1, 2, 2, 3, 3)\n", + "\n", + " \"flatMapNoRec\" should \"Test Case 1\" in { assertResult(r1) { duplicate(l1) } }\n", + "}, 5)" + ] + }, + { + "cell_type": "markdown", + "id": "18ad4a5a-c8c7-42d0-a331-79942c8213a7", + "metadata": {}, + "source": [ + "Now, we will try to use `flatMap` to do something useful.\n", + "\n", + "<span class=\"theorem-title\">**Exercise 12 (5 points)**</span> Write a\n", + "function `getAllWords` that takes in a `List[String]` of sentences and\n", + "returns a `List[String]` of all the words in the sentences. For\n", + "simplicity, our sentences will have no punctuation, and all words will\n", + "be separated by a single space. For example, given the input\n", + "`List(\"I love 3155\", \"Anish is the best TA\")`, the `getAllWords`\n", + "function should return\n", + "`List(\"I\", \"love\", \"3155\", \"Anish\", \"is\", \"the\", \"best\", \"TA\")`.\n", + "\n", + "Use the String method `split` to separate a sentence into its component\n", + "words:\n", + "\n", + "``` scala\n", + "\"Functions are values\".split(\" \").toList\n", + "```\n", + "\n", + "<pre><span class=\"ansi-cyan-fg\">res22</span>: <span class=\"ansi-green-fg\">List</span>[<span class=\"ansi-green-fg\">String</span>] = <span class=\"ansi-yellow-fg\">List</span>(<span class=\"ansi-green-fg\">\"Functions\"</span>, <span class=\"ansi-green-fg\">\"are\"</span>, <span class=\"ansi-green-fg\">\"values\"</span>)</pre>\n", + "\n", + "**Edit this cell:**" + ] + }, + { + "cell_type": "code", + "execution_count": 74, + "id": "f36f72c6", + "metadata": { + "deletable": false, + "nbgrader": { + "cell_type": "code", + "checksum": "72a81c102de3d1d14329753a39c80c17", + "grade": false, + "grade_id": "get-all-words-answer", + "locked": false, + "schema_version": 3, + "solution": true, + "task": false + } + }, + "outputs": [ + { + "data": { + "text/plain": [ + "defined \u001b[32mfunction\u001b[39m \u001b[36mgetAllWords\u001b[39m" + ] + }, + "execution_count": 74, + "metadata": {}, + "output_type": "execute_result" + } + ], + "source": [ + "def getAllWords(sentences: List[String]): List[String] = \n", + " sentences.flatMap(sentence => sentence.split(\" \").toList)" + ] + }, + { + "cell_type": "markdown", + "id": "4c91d0b4-db4a-4520-8220-f8ee63a6ac77", + "metadata": {}, + "source": [ + "#### Tests" + ] + }, + { + "cell_type": "code", + "execution_count": 75, + "id": "51f3b3c2", + "metadata": { + "deletable": false, + "editable": false, + "nbgrader": { + "cell_type": "code", + "checksum": "651dd0c46359dc33dde3983afbbe2606", + "grade": true, + "grade_id": "eval-get-all-words-tester", + "locked": true, + "points": 5, + "schema_version": 3, + "solution": false, + "task": false + } + }, + "outputs": [ + { + "name": "stdout", + "output_type": "stream", + "text": [ + "\u001b[36mRun starting. Expected test count is: 1\u001b[0m\n", + "\u001b[32mcmd75$Helper$$anon$1:\u001b[0m\n", + "\u001b[32mgetAllWords\u001b[0m\n", + "\u001b[32m- should Test Case 1\u001b[0m\n", + "\u001b[36mRun completed in 0 milliseconds.\u001b[0m\n", + "\u001b[36mTotal number of tests run: 1\u001b[0m\n", + "\u001b[36mSuites: completed 1, aborted 0\u001b[0m\n", + "\u001b[36mTests: succeeded 1, failed 0, canceled 0, ignored 0, pending 0\u001b[0m\n", + "\u001b[32mAll tests passed.\u001b[0m\n", + "*** π Tests Passed (5 points) ***\n" + ] + } + ], + "source": [ + "test(new AnyFlatSpec {\n", + " val l1 = List(\"I love 3155\", \"Anish is the best TA\")\n", + " val r1 = List(\"I\", \"love\", \"3155\", \"Anish\", \"is\", \"the\", \"best\", \"TA\")\n", + "\n", + " \"getAllWords\" should \"Test Case 1\" in { assertResult(r1) { getAllWords(l1) } }\n", + "}, 5)" + ] + } + ], + "metadata": { + "kernelspec": { + "display_name": "Scala", + "language": "scala", + "name": "scala" + }, + "language_info": { + "codemirror_mode": "text/x-scala", + "file_extension": ".sc", + "mimetype": "text/x-scala", + "name": "scala", + "nbconvert_exporter": "script", + "version": "2.13.14" + } + }, + "nbformat": 4, + "nbformat_minor": 5 +} |