{ "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", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\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", "**Exercise 1 (5 points)** 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": [ "**Exercise 2 (5 points)** 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": [ "**Exercise 3 (5 points)** 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": [ "**Exercise 4 (5 points)** 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": [ "**Exercise 5 (5 points)** 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", "**Exercise 6 (5 points)** 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": [ "**Exercise 7 (5 points)** 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": [ "**Exercise 8 (10 points)** 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": [ "**Exercise 9 (10 points)** 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", "**Exercise 10 (5 points)** 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", "
lt: List[Node] = List(\n", " Node(\n", " l = Node(l = Empty, d = 1, r = Empty),\n", " d = 2,\n", " r = Node(l = Empty, d = 3, r = Empty)\n", " ),\n", " Node(\n", " l = Node(l = Empty, d = 4, r = Empty),\n", " d = 5,\n", " r = Node(l = Empty, d = 6, r = Empty)\n", " )\n", ")\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", "**Exercise 11 (5 points)** 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", "**Exercise 12 (5 points)** 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", "
res22: List[String] = List(\"Functions\", \"are\", \"values\")\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 }