aboutsummaryrefslogtreecommitdiff
path: root/higher-order-functions-exercise.ipynb
diff options
context:
space:
mode:
Diffstat (limited to 'higher-order-functions-exercise.ipynb')
-rw-r--r--higher-order-functions-exercise.ipynb1576
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
+}