25  Exercise: Higher-Order Functions

\(\newcommand{\TirName}[1]{\text{#1}} \newcommand{\inferrule}[3][]{ \let\and\qquad \begin{array}{@{}l@{}} \TirName{#1} \\ \displaystyle \frac{#2}{#3} \end{array} } \newcommand{\infer}[3][]{\inferrule[#1]{#2}{#3}} \)

Learning Goals

The primary learning goal of this exercise is to get experience programming with higher-order functions.

Instructions

This assignment asks you to write Scala code. There are restrictions associated with how you can solve these problems. Please pay careful heed to those. If you are unsure, ask the course staff.

Note that ??? indicates that there is a missing function or code fragment that needs to be filled in. Make sure that you remove the ??? and replace it with the answer.

Use the test cases provided to test your implementations. You are also encouraged to write your own test cases to help debug your work. However, please delete any extra cells you may have created lest they break an autograder.

Imports

org.scalatest._
// Run this cell FIRST before testing.
import $ivy.`org.scalatest::scalatest:3.2.19`, org.scalatest._, events._, flatspec._
def report(suite: Suite): Unit = suite.execute(stats = true)
def assertPassed(suite: Suite): Unit =
  suite.run(None, Args(new Reporter {
    def apply(e: Event) = e match {
      case e @ (_: TestFailed) => assert(false, s"${e.message} (${e.testName})")
      case _ => ()
    }
  }))
def passed(points: Int): Unit = {
  require(points >=0)
  if (points == 1) println("*** 🎉 Tests Passed (1 point) ***")
  else println(s"*** 🎉 Tests Passed ($points points) ***")
}
def test(suite: Suite, points: Int): Unit = {
  report(suite)
  assertPassed(suite)
  passed(points)
}
import $ivy.$                                , org.scalatest._, events._, flatspec._
defined function report
defined function assertPassed
defined function passed
defined function test

25.1 Collections

When working with and organizing data, we primarily use collections from Scala’s standard library. One of the most fundamental operations that one needs to perform with a collection is to iterate over the elements. Like many other languages with first-class functions (e.g., Python, ML), the Scala library provides various iteration operations via higher-order functions. Higher-order functions are functions that take functions as parameters. The function parameters are often called callbacks, and for collections, they typically specify what the library client wants to do for each element. We have seen examples of these functions in class. In the following questions, we practice both writing such higher-order functions in a library and using them as a client.

25.1.1 Lists

First, we will implement functions that eliminate consecutive duplicates of list elements. If a list contains repeated elements they should be replaced with a single copy of the element. The order of the elements should not be changed. For example, the following List(1, 2, 2, 3, 3, 3) should be converted to List(1,2,3).

Exercise 25.1 (5 points) Write a function compressRec that implements this behavior. Implement the function by direct recursion (e.g., pattern match on l and call compressRec recursively). Do not call any List library methods.

Edit this cell:

def compressRec[A](l: List[A]): List[A] = l match {
  case Nil | _ :: Nil => 
    ???
  case h1 :: (t1 @ (h2 :: _)) => 
    ???
}
defined function compressRec

Notes

  • This exercise is from Ninety-Nine Scala Problems. Some sample solutions are given there, which you are welcome to view. However, we strongly recommend you attempt this exercise before looking there. The purpose of the exercise is to get some practice for the later part of this homework. Note that the solutions there do not satisfy the requirements here, as they use library functions. If at some point you feel like you need more practice with collections, this site is a good resource.

Tests

test(new AnyFlatSpec {
  val l1 = List(1, 2, 2, 3, 3, 3)
  val r1 = List(1, 2, 3)

  "compressRec" should "Test Case 1" in { assertResult( r1 ) { compressRec(l1) } }
}, 5)
Run starting. Expected test count is: 1
cmd2$Helper$$anon$1:
compressRec
- should Test Case 1 *** FAILED ***
  scala.NotImplementedError: an implementation is missing
  at scala.Predef$.$qmark$qmark$qmark(Predef.scala:345)
  at ammonite.$sess.cmd1$Helper.compressRec(cmd1.sc:5)
  at ammonite.$sess.cmd2$Helper$$anon$1.$anonfun$new$1(cmd2.sc:5)
  at org.scalatest.OutcomeOf.outcomeOf(OutcomeOf.scala:85)
  at org.scalatest.OutcomeOf.outcomeOf$(OutcomeOf.scala:83)
  at org.scalatest.OutcomeOf$.outcomeOf(OutcomeOf.scala:104)
  at org.scalatest.Transformer.apply(Transformer.scala:22)
  at org.scalatest.Transformer.apply(Transformer.scala:20)
  at org.scalatest.flatspec.AnyFlatSpecLike$$anon$5.apply(AnyFlatSpecLike.scala:1832)
  at org.scalatest.TestSuite.withFixture(TestSuite.scala:196)
  ...
Run completed in 52 milliseconds.
Total number of tests run: 1
Suites: completed 1, aborted 0
Tests: succeeded 0, failed 1, canceled 0, ignored 0, pending 0
*** 1 TEST FAILED ***
java.lang.AssertionError: assertion failed: an implementation is missing (compressRec should Test Case 1)
  scala.Predef$.assert(Predef.scala:280)
  ammonite.$sess.cmd0$Helper$$anon$1.apply(cmd0.sc:6)
  org.scalatest.WrapperCatchReporter.doApply(CatchReporter.scala:70)
  org.scalatest.CatchReporter.apply(CatchReporter.scala:36)
  org.scalatest.CatchReporter.apply$(CatchReporter.scala:34)
  org.scalatest.WrapperCatchReporter.apply(CatchReporter.scala:63)
  org.scalatest.Suite$.reportTestFailed(Suite.scala:1644)
  org.scalatest.SuperEngine.runTestImpl(Engine.scala:347)
  org.scalatest.flatspec.AnyFlatSpecLike.runTest(AnyFlatSpecLike.scala:1842)
  org.scalatest.flatspec.AnyFlatSpecLike.runTest$(AnyFlatSpecLike.scala:1824)
  org.scalatest.flatspec.AnyFlatSpec.runTest(AnyFlatSpec.scala:1686)
  org.scalatest.flatspec.AnyFlatSpecLike.$anonfun$runTests$1(AnyFlatSpecLike.scala:1900)
  org.scalatest.SuperEngine.$anonfun$runTestsInBranch$1(Engine.scala:413)
  scala.collection.immutable.List.foreach(List.scala:333)
  org.scalatest.SuperEngine.traverseSubNodes$1(Engine.scala:401)
  org.scalatest.SuperEngine.runTestsInBranch(Engine.scala:390)
  org.scalatest.SuperEngine.$anonfun$runTestsInBranch$1(Engine.scala:427)
  scala.collection.immutable.List.foreach(List.scala:333)
  org.scalatest.SuperEngine.traverseSubNodes$1(Engine.scala:401)
  org.scalatest.SuperEngine.runTestsInBranch(Engine.scala:396)
  org.scalatest.SuperEngine.runTestsImpl(Engine.scala:475)
  org.scalatest.flatspec.AnyFlatSpecLike.runTests(AnyFlatSpecLike.scala:1900)
  org.scalatest.flatspec.AnyFlatSpecLike.runTests$(AnyFlatSpecLike.scala:1899)
  org.scalatest.flatspec.AnyFlatSpec.runTests(AnyFlatSpec.scala:1686)
  org.scalatest.Suite.run(Suite.scala:1114)
  org.scalatest.Suite.run$(Suite.scala:1096)
  org.scalatest.flatspec.AnyFlatSpec.org$scalatest$flatspec$AnyFlatSpecLike$$super$run(AnyFlatSpec.scala:1686)
  org.scalatest.flatspec.AnyFlatSpecLike.$anonfun$run$1(AnyFlatSpecLike.scala:1945)
  org.scalatest.SuperEngine.runImpl(Engine.scala:535)
  org.scalatest.flatspec.AnyFlatSpecLike.run(AnyFlatSpecLike.scala:1945)
  org.scalatest.flatspec.AnyFlatSpecLike.run$(AnyFlatSpecLike.scala:1943)
  org.scalatest.flatspec.AnyFlatSpec.run(AnyFlatSpec.scala:1686)
  ammonite.$sess.cmd0$Helper.assertPassed(cmd0.sc:4)
  ammonite.$sess.cmd0$Helper.test(cmd0.sc:17)
  ammonite.$sess.cmd2$Helper.<init>(cmd2.sc:6)
  ammonite.$sess.cmd2$.<clinit>(cmd2.sc:7)

Exercise 25.2 (5 points) Write a different function compressFold that re-implements the behavior of compressRec using the foldRight method from the List library. The call to foldRight has been provided for you. Do not call compressFold recursively or any other List library methods.

Edit this cell:

def compressFold[A](l: List[A]): List[A] = l.foldRight(Nil: List[A]){ (h, acc) => 
  ???
}
defined function compressFold

Tests

test(new AnyFlatSpec {
  val l1 = List(1, 2, 2, 3, 3, 3)
  val r1 = List(1, 2, 3)

  "compressFold" should "Test Case 1" in { assertResult( r1 ) { compressFold(l1) } }
}, 5)
Run starting. Expected test count is: 1
cmd4$Helper$$anon$1:
compressFold
- should Test Case 1 *** FAILED ***
  scala.NotImplementedError: an implementation is missing
  at scala.Predef$.$qmark$qmark$qmark(Predef.scala:345)
  at ammonite.$sess.cmd3$Helper.$anonfun$compressFold$1(cmd3.sc:2)
  at scala.collection.immutable.List.foldRight(List.scala:352)
  at ammonite.$sess.cmd3$Helper.compressFold(cmd3.sc:1)
  at ammonite.$sess.cmd4$Helper$$anon$1.$anonfun$new$1(cmd4.sc:5)
  at org.scalatest.OutcomeOf.outcomeOf(OutcomeOf.scala:85)
  at org.scalatest.OutcomeOf.outcomeOf$(OutcomeOf.scala:83)
  at org.scalatest.OutcomeOf$.outcomeOf(OutcomeOf.scala:104)
  at org.scalatest.Transformer.apply(Transformer.scala:22)
  at org.scalatest.Transformer.apply(Transformer.scala:20)
  ...
Run completed in 1 millisecond.
Total number of tests run: 1
Suites: completed 1, aborted 0
Tests: succeeded 0, failed 1, canceled 0, ignored 0, pending 0
*** 1 TEST FAILED ***
java.lang.AssertionError: assertion failed: an implementation is missing (compressFold should Test Case 1)
  scala.Predef$.assert(Predef.scala:280)
  ammonite.$sess.cmd0$Helper$$anon$1.apply(cmd0.sc:6)
  org.scalatest.WrapperCatchReporter.doApply(CatchReporter.scala:70)
  org.scalatest.CatchReporter.apply(CatchReporter.scala:36)
  org.scalatest.CatchReporter.apply$(CatchReporter.scala:34)
  org.scalatest.WrapperCatchReporter.apply(CatchReporter.scala:63)
  org.scalatest.Suite$.reportTestFailed(Suite.scala:1644)
  org.scalatest.SuperEngine.runTestImpl(Engine.scala:347)
  org.scalatest.flatspec.AnyFlatSpecLike.runTest(AnyFlatSpecLike.scala:1842)
  org.scalatest.flatspec.AnyFlatSpecLike.runTest$(AnyFlatSpecLike.scala:1824)
  org.scalatest.flatspec.AnyFlatSpec.runTest(AnyFlatSpec.scala:1686)
  org.scalatest.flatspec.AnyFlatSpecLike.$anonfun$runTests$1(AnyFlatSpecLike.scala:1900)
  org.scalatest.SuperEngine.$anonfun$runTestsInBranch$1(Engine.scala:413)
  scala.collection.immutable.List.foreach(List.scala:333)
  org.scalatest.SuperEngine.traverseSubNodes$1(Engine.scala:401)
  org.scalatest.SuperEngine.runTestsInBranch(Engine.scala:390)
  org.scalatest.SuperEngine.$anonfun$runTestsInBranch$1(Engine.scala:427)
  scala.collection.immutable.List.foreach(List.scala:333)
  org.scalatest.SuperEngine.traverseSubNodes$1(Engine.scala:401)
  org.scalatest.SuperEngine.runTestsInBranch(Engine.scala:396)
  org.scalatest.SuperEngine.runTestsImpl(Engine.scala:475)
  org.scalatest.flatspec.AnyFlatSpecLike.runTests(AnyFlatSpecLike.scala:1900)
  org.scalatest.flatspec.AnyFlatSpecLike.runTests$(AnyFlatSpecLike.scala:1899)
  org.scalatest.flatspec.AnyFlatSpec.runTests(AnyFlatSpec.scala:1686)
  org.scalatest.Suite.run(Suite.scala:1114)
  org.scalatest.Suite.run$(Suite.scala:1096)
  org.scalatest.flatspec.AnyFlatSpec.org$scalatest$flatspec$AnyFlatSpecLike$$super$run(AnyFlatSpec.scala:1686)
  org.scalatest.flatspec.AnyFlatSpecLike.$anonfun$run$1(AnyFlatSpecLike.scala:1945)
  org.scalatest.SuperEngine.runImpl(Engine.scala:535)
  org.scalatest.flatspec.AnyFlatSpecLike.run(AnyFlatSpecLike.scala:1945)
  org.scalatest.flatspec.AnyFlatSpecLike.run$(AnyFlatSpecLike.scala:1943)
  org.scalatest.flatspec.AnyFlatSpec.run(AnyFlatSpec.scala:1686)
  ammonite.$sess.cmd0$Helper.assertPassed(cmd0.sc:4)
  ammonite.$sess.cmd0$Helper.test(cmd0.sc:17)
  ammonite.$sess.cmd4$Helper.<init>(cmd4.sc:6)
  ammonite.$sess.cmd4$.<clinit>(cmd4.sc:7)

Exercise 25.3 (5 points) Explain in 1–2 sentences the similarities and differences between your two implementations: compressRec and compressFold.

Edit this cell:

???

Exercise 25.4 (5 points) Implement a higher-order recursive function mapFirst that finds the first element of l: List[A] where f: A => Option[A] applied to it returns Some(a) for some value a. The function should replace that element with a and leave l the same everywhere else. For example,

mapFirst(List(1,2,-3,4,-5)) { i => if (i < 0) Some(-i) else None }

should result in List[Int] = List(1, 2, 3, 4, -5).

Edit this cell:

def mapFirst[A](l: List[A])(f: A => Option[A]): List[A] = l match {
  case Nil => 
    ???
  case h :: t => 
    ???
}
defined function mapFirst

Tests

test(new AnyFlatSpec {
  val l1 = List(1, 2, -3, 4, -5)
  val r1 = List(1, 2, 3, 4, -5)

  "mapFirst" should "Test Case 1" in { 
    assertResult(r1) {
      mapFirst(l1) { (i: Int) => if (i < 0) Some(-i) else None }
    }
  }
}, 5)
Run starting. Expected test count is: 1
cmd6$Helper$$anon$1:
mapFirst
- should Test Case 1 *** FAILED ***
  scala.NotImplementedError: an implementation is missing
  at scala.Predef$.$qmark$qmark$qmark(Predef.scala:345)
  at ammonite.$sess.cmd5$Helper.mapFirst(cmd5.sc:5)
  at ammonite.$sess.cmd6$Helper$$anon$1.$anonfun$new$1(cmd6.sc:7)
  at org.scalatest.OutcomeOf.outcomeOf(OutcomeOf.scala:85)
  at org.scalatest.OutcomeOf.outcomeOf$(OutcomeOf.scala:83)
  at org.scalatest.OutcomeOf$.outcomeOf(OutcomeOf.scala:104)
  at org.scalatest.Transformer.apply(Transformer.scala:22)
  at org.scalatest.Transformer.apply(Transformer.scala:20)
  at org.scalatest.flatspec.AnyFlatSpecLike$$anon$5.apply(AnyFlatSpecLike.scala:1832)
  at org.scalatest.TestSuite.withFixture(TestSuite.scala:196)
  ...
Run completed in 2 milliseconds.
Total number of tests run: 1
Suites: completed 1, aborted 0
Tests: succeeded 0, failed 1, canceled 0, ignored 0, pending 0
*** 1 TEST FAILED ***
java.lang.AssertionError: assertion failed: an implementation is missing (mapFirst should Test Case 1)
  scala.Predef$.assert(Predef.scala:280)
  ammonite.$sess.cmd0$Helper$$anon$1.apply(cmd0.sc:6)
  org.scalatest.WrapperCatchReporter.doApply(CatchReporter.scala:70)
  org.scalatest.CatchReporter.apply(CatchReporter.scala:36)
  org.scalatest.CatchReporter.apply$(CatchReporter.scala:34)
  org.scalatest.WrapperCatchReporter.apply(CatchReporter.scala:63)
  org.scalatest.Suite$.reportTestFailed(Suite.scala:1644)
  org.scalatest.SuperEngine.runTestImpl(Engine.scala:347)
  org.scalatest.flatspec.AnyFlatSpecLike.runTest(AnyFlatSpecLike.scala:1842)
  org.scalatest.flatspec.AnyFlatSpecLike.runTest$(AnyFlatSpecLike.scala:1824)
  org.scalatest.flatspec.AnyFlatSpec.runTest(AnyFlatSpec.scala:1686)
  org.scalatest.flatspec.AnyFlatSpecLike.$anonfun$runTests$1(AnyFlatSpecLike.scala:1900)
  org.scalatest.SuperEngine.$anonfun$runTestsInBranch$1(Engine.scala:413)
  scala.collection.immutable.List.foreach(List.scala:333)
  org.scalatest.SuperEngine.traverseSubNodes$1(Engine.scala:401)
  org.scalatest.SuperEngine.runTestsInBranch(Engine.scala:390)
  org.scalatest.SuperEngine.$anonfun$runTestsInBranch$1(Engine.scala:427)
  scala.collection.immutable.List.foreach(List.scala:333)
  org.scalatest.SuperEngine.traverseSubNodes$1(Engine.scala:401)
  org.scalatest.SuperEngine.runTestsInBranch(Engine.scala:396)
  org.scalatest.SuperEngine.runTestsImpl(Engine.scala:475)
  org.scalatest.flatspec.AnyFlatSpecLike.runTests(AnyFlatSpecLike.scala:1900)
  org.scalatest.flatspec.AnyFlatSpecLike.runTests$(AnyFlatSpecLike.scala:1899)
  org.scalatest.flatspec.AnyFlatSpec.runTests(AnyFlatSpec.scala:1686)
  org.scalatest.Suite.run(Suite.scala:1114)
  org.scalatest.Suite.run$(Suite.scala:1096)
  org.scalatest.flatspec.AnyFlatSpec.org$scalatest$flatspec$AnyFlatSpecLike$$super$run(AnyFlatSpec.scala:1686)
  org.scalatest.flatspec.AnyFlatSpecLike.$anonfun$run$1(AnyFlatSpecLike.scala:1945)
  org.scalatest.SuperEngine.runImpl(Engine.scala:535)
  org.scalatest.flatspec.AnyFlatSpecLike.run(AnyFlatSpecLike.scala:1945)
  org.scalatest.flatspec.AnyFlatSpecLike.run$(AnyFlatSpecLike.scala:1943)
  org.scalatest.flatspec.AnyFlatSpec.run(AnyFlatSpec.scala:1686)
  ammonite.$sess.cmd0$Helper.assertPassed(cmd0.sc:4)
  ammonite.$sess.cmd0$Helper.test(cmd0.sc:17)
  ammonite.$sess.cmd6$Helper.<init>(cmd6.sc:10)
  ammonite.$sess.cmd6$.<clinit>(cmd6.sc:7)

Exercise 25.5 (5 points) Write a function composeMap that sequentially applies a list of functions of type A => A to all the elements of a List[A]. For example, if we have a list of functions List(f1, f2, f3), and a list List(a, b), we want to output List(f3(f2(f1(a))), f3(f2(f1(b)))).

Edit this cell:

def composeMap[A](functions: List[A => A])(l: List[A]): List[A] =
  ???
defined function composeMap

Tests

test(new AnyFlatSpec {
  def plusOne(x: Int): Int = x + 1
  def square(x: Int): Int = x * x
  def timesThree(x: Int): Int = x * 3

  val l1 = List(1, 2, 3)
  val r1 = List(10, 37, 82)
  val fs: List[Int => Int] = List(plusOne, square, timesThree)

  "composeMap" should "Test Case 1" in { assertResult(r1) { composeMap(fs)(l1) } }
}, 5)
Run starting. Expected test count is: 1
cmd8$Helper$$anon$1:
composeMap
- should Test Case 1 *** FAILED ***
  scala.NotImplementedError: an implementation is missing
  at scala.Predef$.$qmark$qmark$qmark(Predef.scala:345)
  at ammonite.$sess.cmd7$Helper.composeMap(cmd7.sc:2)
  at ammonite.$sess.cmd8$Helper$$anon$1.$anonfun$new$1(cmd8.sc:10)
  at org.scalatest.OutcomeOf.outcomeOf(OutcomeOf.scala:85)
  at org.scalatest.OutcomeOf.outcomeOf$(OutcomeOf.scala:83)
  at org.scalatest.OutcomeOf$.outcomeOf(OutcomeOf.scala:104)
  at org.scalatest.Transformer.apply(Transformer.scala:22)
  at org.scalatest.Transformer.apply(Transformer.scala:20)
  at org.scalatest.flatspec.AnyFlatSpecLike$$anon$5.apply(AnyFlatSpecLike.scala:1832)
  at org.scalatest.TestSuite.withFixture(TestSuite.scala:196)
  ...
Run completed in 1 millisecond.
Total number of tests run: 1
Suites: completed 1, aborted 0
Tests: succeeded 0, failed 1, canceled 0, ignored 0, pending 0
*** 1 TEST FAILED ***
java.lang.AssertionError: assertion failed: an implementation is missing (composeMap should Test Case 1)
  scala.Predef$.assert(Predef.scala:280)
  ammonite.$sess.cmd0$Helper$$anon$1.apply(cmd0.sc:6)
  org.scalatest.WrapperCatchReporter.doApply(CatchReporter.scala:70)
  org.scalatest.CatchReporter.apply(CatchReporter.scala:36)
  org.scalatest.CatchReporter.apply$(CatchReporter.scala:34)
  org.scalatest.WrapperCatchReporter.apply(CatchReporter.scala:63)
  org.scalatest.Suite$.reportTestFailed(Suite.scala:1644)
  org.scalatest.SuperEngine.runTestImpl(Engine.scala:347)
  org.scalatest.flatspec.AnyFlatSpecLike.runTest(AnyFlatSpecLike.scala:1842)
  org.scalatest.flatspec.AnyFlatSpecLike.runTest$(AnyFlatSpecLike.scala:1824)
  org.scalatest.flatspec.AnyFlatSpec.runTest(AnyFlatSpec.scala:1686)
  org.scalatest.flatspec.AnyFlatSpecLike.$anonfun$runTests$1(AnyFlatSpecLike.scala:1900)
  org.scalatest.SuperEngine.$anonfun$runTestsInBranch$1(Engine.scala:413)
  scala.collection.immutable.List.foreach(List.scala:333)
  org.scalatest.SuperEngine.traverseSubNodes$1(Engine.scala:401)
  org.scalatest.SuperEngine.runTestsInBranch(Engine.scala:390)
  org.scalatest.SuperEngine.$anonfun$runTestsInBranch$1(Engine.scala:427)
  scala.collection.immutable.List.foreach(List.scala:333)
  org.scalatest.SuperEngine.traverseSubNodes$1(Engine.scala:401)
  org.scalatest.SuperEngine.runTestsInBranch(Engine.scala:396)
  org.scalatest.SuperEngine.runTestsImpl(Engine.scala:475)
  org.scalatest.flatspec.AnyFlatSpecLike.runTests(AnyFlatSpecLike.scala:1900)
  org.scalatest.flatspec.AnyFlatSpecLike.runTests$(AnyFlatSpecLike.scala:1899)
  org.scalatest.flatspec.AnyFlatSpec.runTests(AnyFlatSpec.scala:1686)
  org.scalatest.Suite.run(Suite.scala:1114)
  org.scalatest.Suite.run$(Suite.scala:1096)
  org.scalatest.flatspec.AnyFlatSpec.org$scalatest$flatspec$AnyFlatSpecLike$$super$run(AnyFlatSpec.scala:1686)
  org.scalatest.flatspec.AnyFlatSpecLike.$anonfun$run$1(AnyFlatSpecLike.scala:1945)
  org.scalatest.SuperEngine.runImpl(Engine.scala:535)
  org.scalatest.flatspec.AnyFlatSpecLike.run(AnyFlatSpecLike.scala:1945)
  org.scalatest.flatspec.AnyFlatSpecLike.run$(AnyFlatSpecLike.scala:1943)
  org.scalatest.flatspec.AnyFlatSpec.run(AnyFlatSpec.scala:1686)
  ammonite.$sess.cmd0$Helper.assertPassed(cmd0.sc:4)
  ammonite.$sess.cmd0$Helper.test(cmd0.sc:17)
  ammonite.$sess.cmd8$Helper.<init>(cmd8.sc:11)
  ammonite.$sess.cmd8$.<clinit>(cmd8.sc:7)

25.1.2 Maps

Recall the Map[A, B] data structure from class. Also, recall the higher-order function map. To avoid confusion we will use the upper case Map to refer to the type, and the lowercase map to refer to the higher-order function.

Exercise 25.6 (5 points) Implement a function mapValues that takes a Map[A,B] and a callback function f: B => C, that applies f to all the values in the Map. Your function should use the Scala collections map method. Do not use the standard library method mapValues on Map (however, note that the behavior of your function should be exactly the same as the mapValues standard library method).

Edit this cell:

def mapValues[A, B, C](m: Map[A, B])(f: B => C): Map[A, C] = 
  ???
defined function mapValues

Tests

test(new AnyFlatSpec {
  val m1 = Map("a" -> 1, "b" -> 2, "c" -> 3)
  val r1 = Map("a" -> 1, "b" -> 4, "c" -> 9)

  "mapValues" should "Test Case 1" in { 
    assertResult(r1) {
      mapValues(m1) { (i: Int) => i * i }
    }
  }
}, 5)
Run starting. Expected test count is: 1
cmd10$Helper$$anon$1:
mapValues
- should Test Case 1 *** FAILED ***
  scala.NotImplementedError: an implementation is missing
  at scala.Predef$.$qmark$qmark$qmark(Predef.scala:345)
  at ammonite.$sess.cmd9$Helper.mapValues(cmd9.sc:2)
  at ammonite.$sess.cmd10$Helper$$anon$1.$anonfun$new$1(cmd10.sc:7)
  at org.scalatest.OutcomeOf.outcomeOf(OutcomeOf.scala:85)
  at org.scalatest.OutcomeOf.outcomeOf$(OutcomeOf.scala:83)
  at org.scalatest.OutcomeOf$.outcomeOf(OutcomeOf.scala:104)
  at org.scalatest.Transformer.apply(Transformer.scala:22)
  at org.scalatest.Transformer.apply(Transformer.scala:20)
  at org.scalatest.flatspec.AnyFlatSpecLike$$anon$5.apply(AnyFlatSpecLike.scala:1832)
  at org.scalatest.TestSuite.withFixture(TestSuite.scala:196)
  ...
Run completed in 1 millisecond.
Total number of tests run: 1
Suites: completed 1, aborted 0
Tests: succeeded 0, failed 1, canceled 0, ignored 0, pending 0
*** 1 TEST FAILED ***
java.lang.AssertionError: assertion failed: an implementation is missing (mapValues should Test Case 1)
  scala.Predef$.assert(Predef.scala:280)
  ammonite.$sess.cmd0$Helper$$anon$1.apply(cmd0.sc:6)
  org.scalatest.WrapperCatchReporter.doApply(CatchReporter.scala:70)
  org.scalatest.CatchReporter.apply(CatchReporter.scala:36)
  org.scalatest.CatchReporter.apply$(CatchReporter.scala:34)
  org.scalatest.WrapperCatchReporter.apply(CatchReporter.scala:63)
  org.scalatest.Suite$.reportTestFailed(Suite.scala:1644)
  org.scalatest.SuperEngine.runTestImpl(Engine.scala:347)
  org.scalatest.flatspec.AnyFlatSpecLike.runTest(AnyFlatSpecLike.scala:1842)
  org.scalatest.flatspec.AnyFlatSpecLike.runTest$(AnyFlatSpecLike.scala:1824)
  org.scalatest.flatspec.AnyFlatSpec.runTest(AnyFlatSpec.scala:1686)
  org.scalatest.flatspec.AnyFlatSpecLike.$anonfun$runTests$1(AnyFlatSpecLike.scala:1900)
  org.scalatest.SuperEngine.$anonfun$runTestsInBranch$1(Engine.scala:413)
  scala.collection.immutable.List.foreach(List.scala:333)
  org.scalatest.SuperEngine.traverseSubNodes$1(Engine.scala:401)
  org.scalatest.SuperEngine.runTestsInBranch(Engine.scala:390)
  org.scalatest.SuperEngine.$anonfun$runTestsInBranch$1(Engine.scala:427)
  scala.collection.immutable.List.foreach(List.scala:333)
  org.scalatest.SuperEngine.traverseSubNodes$1(Engine.scala:401)
  org.scalatest.SuperEngine.runTestsInBranch(Engine.scala:396)
  org.scalatest.SuperEngine.runTestsImpl(Engine.scala:475)
  org.scalatest.flatspec.AnyFlatSpecLike.runTests(AnyFlatSpecLike.scala:1900)
  org.scalatest.flatspec.AnyFlatSpecLike.runTests$(AnyFlatSpecLike.scala:1899)
  org.scalatest.flatspec.AnyFlatSpec.runTests(AnyFlatSpec.scala:1686)
  org.scalatest.Suite.run(Suite.scala:1114)
  org.scalatest.Suite.run$(Suite.scala:1096)
  org.scalatest.flatspec.AnyFlatSpec.org$scalatest$flatspec$AnyFlatSpecLike$$super$run(AnyFlatSpec.scala:1686)
  org.scalatest.flatspec.AnyFlatSpecLike.$anonfun$run$1(AnyFlatSpecLike.scala:1945)
  org.scalatest.SuperEngine.runImpl(Engine.scala:535)
  org.scalatest.flatspec.AnyFlatSpecLike.run(AnyFlatSpecLike.scala:1945)
  org.scalatest.flatspec.AnyFlatSpecLike.run$(AnyFlatSpecLike.scala:1943)
  org.scalatest.flatspec.AnyFlatSpec.run(AnyFlatSpec.scala:1686)
  ammonite.$sess.cmd0$Helper.assertPassed(cmd0.sc:4)
  ammonite.$sess.cmd0$Helper.test(cmd0.sc:17)
  ammonite.$sess.cmd10$Helper.<init>(cmd10.sc:10)
  ammonite.$sess.cmd10$.<clinit>(cmd10.sc:7)

Exercise 25.7 (5 points) As we mentioned above, we just reimplemented mapValues using the map method from the standard library. Earlier, we implemented higher-order functions on Lists recursively. Could we have implemented mapValues on Maps recursively? If yes, give an example implementation. If no, explain why we cannot, and what makes Map different from List in this case.

Edit this cell:

???

25.1.3 Trees

Recall the binary tree data type:

sealed trait Tree
case object Empty extends Tree
case class Node(l: Tree, d: Int, r: Tree) extends Tree
defined trait Tree
defined object Empty
defined class Node

Exercise 25.8 (10 points) Implement a higher-order function foldLeft that performs an in-order traversal of the input t: Tree, calling the callback f starting with z to accumulate a result. For example, suppose the in-order traversal of the input tree t yields the sequence of data values: \(d_1,d_2,\dots,d_n\). Then, foldLeft(t)(z)(f) yields \(f(f(\dots(f(f(z,d_1),d_2))\dots d_{n-1}),d_n)\)

Edit this cell:

def foldLeft[A](t: Tree)(z: A)(f: (A, Int) => A): A = {
  def loop(acc: A, t: Tree): A = t match {
    case Empty => 
      ???
    case Node(l, d, r) => 
      ???
  }
  ???
}
defined function foldLeft

We have provided a test client sum that computes the sum of all of the data values in the tree using your foldLeft method, along with some helper functions to build trees more easily. Feel free to use them to write more test cases for your code.

// An example use of foldLeft
def sum(t: Tree): Int = foldLeft(t)(0){ (acc, d) => acc + d }

// In-order insertion into a binary search tree
def insert(t: Tree, n: Int): Tree = t match {
  case Empty => Node(Empty, n, Empty)
  case Node(l, d, r) =>
    if (n < d) Node(insert(l, n), d, r) else Node(l, d, insert(r, n))
}

// Create a tree from a list. An example use of the List.foldLeft method.
def treeFromList(l: List[Int]): Tree =
  l.foldLeft(Empty: Tree){ (acc, i) => insert(acc, i) }
defined function sum
defined function insert
defined function treeFromList

Tests

test(new AnyFlatSpec {
  val t1 = treeFromList(List(1, 2, 3))
  "foldLeft" should "Test Case 1" in { assertResult(6) { sum(t1) } }

  val l2 = List(3, 4, 8, 2, 1, 7, 10)
  val sortl2 = l2.sorted
  val t2 = treeFromList(l2)

  def rev(acc: List[Int], x: Int): List[Int] = x :: acc
  def prod(acc: Int, x: Int): Int = x * acc

  it should "Test Case 2" in {
    assertResult( sortl2.foldLeft(Nil: List[Int])(rev) ) {
      foldLeft(t2)(Nil: List[Int])(rev)
    }
  }

  it should "Test Case 3" in {
    assertResult( l2.foldLeft(1)(prod) ) {
      foldLeft(t2)(1)(prod)
    }
  }

}, 10)
Run starting. Expected test count is: 3
cmd14$Helper$$anon$1:
foldLeft
- should Test Case 1 *** FAILED ***
  scala.NotImplementedError: an implementation is missing
  at scala.Predef$.$qmark$qmark$qmark(Predef.scala:345)
  at ammonite.$sess.cmd12$Helper.foldLeft(cmd12.sc:8)
  at ammonite.$sess.cmd13$Helper.sum(cmd13.sc:1)
  at ammonite.$sess.cmd14$Helper$$anon$1.$anonfun$new$1(cmd14.sc:3)
  at org.scalatest.OutcomeOf.outcomeOf(OutcomeOf.scala:85)
  at org.scalatest.OutcomeOf.outcomeOf$(OutcomeOf.scala:83)
  at org.scalatest.OutcomeOf$.outcomeOf(OutcomeOf.scala:104)
  at org.scalatest.Transformer.apply(Transformer.scala:22)
  at org.scalatest.Transformer.apply(Transformer.scala:20)
  at org.scalatest.flatspec.AnyFlatSpecLike$$anon$5.apply(AnyFlatSpecLike.scala:1832)
  ...
- should Test Case 2 *** FAILED ***
  scala.NotImplementedError: an implementation is missing
  at scala.Predef$.$qmark$qmark$qmark(Predef.scala:345)
  at ammonite.$sess.cmd12$Helper.foldLeft(cmd12.sc:8)
  at ammonite.$sess.cmd14$Helper$$anon$1.$anonfun$new$2(cmd14.sc:14)
  at org.scalatest.OutcomeOf.outcomeOf(OutcomeOf.scala:85)
  at org.scalatest.OutcomeOf.outcomeOf$(OutcomeOf.scala:83)
  at org.scalatest.OutcomeOf$.outcomeOf(OutcomeOf.scala:104)
  at org.scalatest.Transformer.apply(Transformer.scala:22)
  at org.scalatest.Transformer.apply(Transformer.scala:20)
  at org.scalatest.flatspec.AnyFlatSpecLike$$anon$5.apply(AnyFlatSpecLike.scala:1832)
  at org.scalatest.TestSuite.withFixture(TestSuite.scala:196)
  ...
- should Test Case 3 *** FAILED ***
  scala.NotImplementedError: an implementation is missing
  at scala.Predef$.$qmark$qmark$qmark(Predef.scala:345)
  at ammonite.$sess.cmd12$Helper.foldLeft(cmd12.sc:8)
  at ammonite.$sess.cmd14$Helper$$anon$1.$anonfun$new$5(cmd14.sc:20)
  at org.scalatest.OutcomeOf.outcomeOf(OutcomeOf.scala:85)
  at org.scalatest.OutcomeOf.outcomeOf$(OutcomeOf.scala:83)
  at org.scalatest.OutcomeOf$.outcomeOf(OutcomeOf.scala:104)
  at org.scalatest.Transformer.apply(Transformer.scala:22)
  at org.scalatest.Transformer.apply(Transformer.scala:20)
  at org.scalatest.flatspec.AnyFlatSpecLike$$anon$5.apply(AnyFlatSpecLike.scala:1832)
  at org.scalatest.TestSuite.withFixture(TestSuite.scala:196)
  ...
Run completed in 5 milliseconds.
Total number of tests run: 3
Suites: completed 1, aborted 0
Tests: succeeded 0, failed 3, canceled 0, ignored 0, pending 0
*** 3 TESTS FAILED ***
java.lang.AssertionError: assertion failed: an implementation is missing (foldLeft should Test Case 1)
  scala.Predef$.assert(Predef.scala:280)
  ammonite.$sess.cmd0$Helper$$anon$1.apply(cmd0.sc:6)
  org.scalatest.WrapperCatchReporter.doApply(CatchReporter.scala:70)
  org.scalatest.CatchReporter.apply(CatchReporter.scala:36)
  org.scalatest.CatchReporter.apply$(CatchReporter.scala:34)
  org.scalatest.WrapperCatchReporter.apply(CatchReporter.scala:63)
  org.scalatest.Suite$.reportTestFailed(Suite.scala:1644)
  org.scalatest.SuperEngine.runTestImpl(Engine.scala:347)
  org.scalatest.flatspec.AnyFlatSpecLike.runTest(AnyFlatSpecLike.scala:1842)
  org.scalatest.flatspec.AnyFlatSpecLike.runTest$(AnyFlatSpecLike.scala:1824)
  org.scalatest.flatspec.AnyFlatSpec.runTest(AnyFlatSpec.scala:1686)
  org.scalatest.flatspec.AnyFlatSpecLike.$anonfun$runTests$1(AnyFlatSpecLike.scala:1900)
  org.scalatest.SuperEngine.$anonfun$runTestsInBranch$1(Engine.scala:413)
  scala.collection.immutable.List.foreach(List.scala:333)
  org.scalatest.SuperEngine.traverseSubNodes$1(Engine.scala:401)
  org.scalatest.SuperEngine.runTestsInBranch(Engine.scala:390)
  org.scalatest.SuperEngine.$anonfun$runTestsInBranch$1(Engine.scala:427)
  scala.collection.immutable.List.foreach(List.scala:333)
  org.scalatest.SuperEngine.traverseSubNodes$1(Engine.scala:401)
  org.scalatest.SuperEngine.runTestsInBranch(Engine.scala:396)
  org.scalatest.SuperEngine.runTestsImpl(Engine.scala:475)
  org.scalatest.flatspec.AnyFlatSpecLike.runTests(AnyFlatSpecLike.scala:1900)
  org.scalatest.flatspec.AnyFlatSpecLike.runTests$(AnyFlatSpecLike.scala:1899)
  org.scalatest.flatspec.AnyFlatSpec.runTests(AnyFlatSpec.scala:1686)
  org.scalatest.Suite.run(Suite.scala:1114)
  org.scalatest.Suite.run$(Suite.scala:1096)
  org.scalatest.flatspec.AnyFlatSpec.org$scalatest$flatspec$AnyFlatSpecLike$$super$run(AnyFlatSpec.scala:1686)
  org.scalatest.flatspec.AnyFlatSpecLike.$anonfun$run$1(AnyFlatSpecLike.scala:1945)
  org.scalatest.SuperEngine.runImpl(Engine.scala:535)
  org.scalatest.flatspec.AnyFlatSpecLike.run(AnyFlatSpecLike.scala:1945)
  org.scalatest.flatspec.AnyFlatSpecLike.run$(AnyFlatSpecLike.scala:1943)
  org.scalatest.flatspec.AnyFlatSpec.run(AnyFlatSpec.scala:1686)
  ammonite.$sess.cmd0$Helper.assertPassed(cmd0.sc:4)
  ammonite.$sess.cmd0$Helper.test(cmd0.sc:17)
  ammonite.$sess.cmd14$Helper.<init>(cmd14.sc:24)
  ammonite.$sess.cmd14$.<clinit>(cmd14.sc:7)

Exercise 25.9 (10 points) Using your foldLeft function, write a client function strictlyOrdered that checks if the data values of an in-order traversal of t are in strictly ascending order. For example, suppose the in-order traversal of the input tree t yields the sequence of data values: \(d_1,d_2,\dots,d_n\), the strictlyOrdered should return true iff \(d_1 < d_2 < \dots < d_n\).

Edit this cell:

def strictlyOrdered(t: Tree): Boolean = {
  val (b, _) = foldLeft(t)((true, None: Option[Int])) {
    ???
  }
  b
}
defined function strictlyOrdered

Tests

test(new AnyFlatSpec {
  "strictlyOrdered" should "Test Case 1" in { assert(!strictlyOrdered(treeFromList(List(1,1,2)))) }
  it should "Test Case 2" in { assert(strictlyOrdered(treeFromList(List(1,2)))) }
  it should "Test Case 3" in { assert(!strictlyOrdered(treeFromList(List(-1,0,1,1,2)))) }
  it should "Test Case 4" in { assert(!strictlyOrdered(treeFromList(List(2,1,2,3,4)))) }
  it should "Test Case 5" in { assert(strictlyOrdered(treeFromList(List(1,2,3,4,5)))) }
}, 10)
Run starting. Expected test count is: 5
cmd16$Helper$$anon$1:
strictlyOrdered
- should Test Case 1 *** FAILED ***
  scala.NotImplementedError: an implementation is missing
  at scala.Predef$.$qmark$qmark$qmark(Predef.scala:345)
  at ammonite.$sess.cmd15$Helper.strictlyOrdered(cmd15.sc:3)
  at ammonite.$sess.cmd16$Helper$$anon$1.$anonfun$new$1(cmd16.sc:2)
  at org.scalatest.OutcomeOf.outcomeOf(OutcomeOf.scala:85)
  at org.scalatest.OutcomeOf.outcomeOf$(OutcomeOf.scala:83)
  at org.scalatest.OutcomeOf$.outcomeOf(OutcomeOf.scala:104)
  at org.scalatest.Transformer.apply(Transformer.scala:22)
  at org.scalatest.Transformer.apply(Transformer.scala:20)
  at org.scalatest.flatspec.AnyFlatSpecLike$$anon$5.apply(AnyFlatSpecLike.scala:1832)
  at org.scalatest.TestSuite.withFixture(TestSuite.scala:196)
  ...
- should Test Case 2 *** FAILED ***
  scala.NotImplementedError: an implementation is missing
  at scala.Predef$.$qmark$qmark$qmark(Predef.scala:345)
  at ammonite.$sess.cmd15$Helper.strictlyOrdered(cmd15.sc:3)
  at ammonite.$sess.cmd16$Helper$$anon$1.$anonfun$new$2(cmd16.sc:3)
  at org.scalatest.OutcomeOf.outcomeOf(OutcomeOf.scala:85)
  at org.scalatest.OutcomeOf.outcomeOf$(OutcomeOf.scala:83)
  at org.scalatest.OutcomeOf$.outcomeOf(OutcomeOf.scala:104)
  at org.scalatest.Transformer.apply(Transformer.scala:22)
  at org.scalatest.Transformer.apply(Transformer.scala:20)
  at org.scalatest.flatspec.AnyFlatSpecLike$$anon$5.apply(AnyFlatSpecLike.scala:1832)
  at org.scalatest.TestSuite.withFixture(TestSuite.scala:196)
  ...
- should Test Case 3 *** FAILED ***
  scala.NotImplementedError: an implementation is missing
  at scala.Predef$.$qmark$qmark$qmark(Predef.scala:345)
  at ammonite.$sess.cmd15$Helper.strictlyOrdered(cmd15.sc:3)
  at ammonite.$sess.cmd16$Helper$$anon$1.$anonfun$new$3(cmd16.sc:4)
  at org.scalatest.OutcomeOf.outcomeOf(OutcomeOf.scala:85)
  at org.scalatest.OutcomeOf.outcomeOf$(OutcomeOf.scala:83)
  at org.scalatest.OutcomeOf$.outcomeOf(OutcomeOf.scala:104)
  at org.scalatest.Transformer.apply(Transformer.scala:22)
  at org.scalatest.Transformer.apply(Transformer.scala:20)
  at org.scalatest.flatspec.AnyFlatSpecLike$$anon$5.apply(AnyFlatSpecLike.scala:1832)
  at org.scalatest.TestSuite.withFixture(TestSuite.scala:196)
  ...
- should Test Case 4 *** FAILED ***
  scala.NotImplementedError: an implementation is missing
  at scala.Predef$.$qmark$qmark$qmark(Predef.scala:345)
  at ammonite.$sess.cmd15$Helper.strictlyOrdered(cmd15.sc:3)
  at ammonite.$sess.cmd16$Helper$$anon$1.$anonfun$new$4(cmd16.sc:5)
  at org.scalatest.OutcomeOf.outcomeOf(OutcomeOf.scala:85)
  at org.scalatest.OutcomeOf.outcomeOf$(OutcomeOf.scala:83)
  at org.scalatest.OutcomeOf$.outcomeOf(OutcomeOf.scala:104)
  at org.scalatest.Transformer.apply(Transformer.scala:22)
  at org.scalatest.Transformer.apply(Transformer.scala:20)
  at org.scalatest.flatspec.AnyFlatSpecLike$$anon$5.apply(AnyFlatSpecLike.scala:1832)
  at org.scalatest.TestSuite.withFixture(TestSuite.scala:196)
  ...
- should Test Case 5 *** FAILED ***
  scala.NotImplementedError: an implementation is missing
  at scala.Predef$.$qmark$qmark$qmark(Predef.scala:345)
  at ammonite.$sess.cmd15$Helper.strictlyOrdered(cmd15.sc:3)
  at ammonite.$sess.cmd16$Helper$$anon$1.$anonfun$new$5(cmd16.sc:6)
  at org.scalatest.OutcomeOf.outcomeOf(OutcomeOf.scala:85)
  at org.scalatest.OutcomeOf.outcomeOf$(OutcomeOf.scala:83)
  at org.scalatest.OutcomeOf$.outcomeOf(OutcomeOf.scala:104)
  at org.scalatest.Transformer.apply(Transformer.scala:22)
  at org.scalatest.Transformer.apply(Transformer.scala:20)
  at org.scalatest.flatspec.AnyFlatSpecLike$$anon$5.apply(AnyFlatSpecLike.scala:1832)
  at org.scalatest.TestSuite.withFixture(TestSuite.scala:196)
  ...
Run completed in 5 milliseconds.
Total number of tests run: 5
Suites: completed 1, aborted 0
Tests: succeeded 0, failed 5, canceled 0, ignored 0, pending 0
*** 5 TESTS FAILED ***
java.lang.AssertionError: assertion failed: an implementation is missing (strictlyOrdered should Test Case 1)
  scala.Predef$.assert(Predef.scala:280)
  ammonite.$sess.cmd0$Helper$$anon$1.apply(cmd0.sc:6)
  org.scalatest.WrapperCatchReporter.doApply(CatchReporter.scala:70)
  org.scalatest.CatchReporter.apply(CatchReporter.scala:36)
  org.scalatest.CatchReporter.apply$(CatchReporter.scala:34)
  org.scalatest.WrapperCatchReporter.apply(CatchReporter.scala:63)
  org.scalatest.Suite$.reportTestFailed(Suite.scala:1644)
  org.scalatest.SuperEngine.runTestImpl(Engine.scala:347)
  org.scalatest.flatspec.AnyFlatSpecLike.runTest(AnyFlatSpecLike.scala:1842)
  org.scalatest.flatspec.AnyFlatSpecLike.runTest$(AnyFlatSpecLike.scala:1824)
  org.scalatest.flatspec.AnyFlatSpec.runTest(AnyFlatSpec.scala:1686)
  org.scalatest.flatspec.AnyFlatSpecLike.$anonfun$runTests$1(AnyFlatSpecLike.scala:1900)
  org.scalatest.SuperEngine.$anonfun$runTestsInBranch$1(Engine.scala:413)
  scala.collection.immutable.List.foreach(List.scala:333)
  org.scalatest.SuperEngine.traverseSubNodes$1(Engine.scala:401)
  org.scalatest.SuperEngine.runTestsInBranch(Engine.scala:390)
  org.scalatest.SuperEngine.$anonfun$runTestsInBranch$1(Engine.scala:427)
  scala.collection.immutable.List.foreach(List.scala:333)
  org.scalatest.SuperEngine.traverseSubNodes$1(Engine.scala:401)
  org.scalatest.SuperEngine.runTestsInBranch(Engine.scala:396)
  org.scalatest.SuperEngine.runTestsImpl(Engine.scala:475)
  org.scalatest.flatspec.AnyFlatSpecLike.runTests(AnyFlatSpecLike.scala:1900)
  org.scalatest.flatspec.AnyFlatSpecLike.runTests$(AnyFlatSpecLike.scala:1899)
  org.scalatest.flatspec.AnyFlatSpec.runTests(AnyFlatSpec.scala:1686)
  org.scalatest.Suite.run(Suite.scala:1114)
  org.scalatest.Suite.run$(Suite.scala:1096)
  org.scalatest.flatspec.AnyFlatSpec.org$scalatest$flatspec$AnyFlatSpecLike$$super$run(AnyFlatSpec.scala:1686)
  org.scalatest.flatspec.AnyFlatSpecLike.$anonfun$run$1(AnyFlatSpecLike.scala:1945)
  org.scalatest.SuperEngine.runImpl(Engine.scala:535)
  org.scalatest.flatspec.AnyFlatSpecLike.run(AnyFlatSpecLike.scala:1945)
  org.scalatest.flatspec.AnyFlatSpecLike.run$(AnyFlatSpecLike.scala:1943)
  org.scalatest.flatspec.AnyFlatSpec.run(AnyFlatSpec.scala:1686)
  ammonite.$sess.cmd0$Helper.assertPassed(cmd0.sc:4)
  ammonite.$sess.cmd0$Helper.test(cmd0.sc:17)
  ammonite.$sess.cmd16$Helper.<init>(cmd16.sc:7)
  ammonite.$sess.cmd16$.<clinit>(cmd16.sc:7)

Now, we will write a higher-order function that uses our recent higher-order functions as a client.

Exercise 25.10 (5 points) Implement a function foldLeftTrees that take as input a lt: List[Tree], and applies a callback f to all of their nodes in-order (of both the List and the nested Trees) starting with initial value z to accumulate a result.

For example, calling foldLeftTrees on

val lt = 
  List(
    Node(Node(Empty, 1, Empty), 2, Node(Empty, 3, Empty)),
    Node(Node(Empty, 4, Empty), 5, Node(Empty, 6, Empty))
  )
lt: List[Node] = List(
  Node(
    l = Node(l = Empty, d = 1, r = Empty),
    d = 2,
    r = Node(l = Empty, d = 3, r = Empty)
  ),
  Node(
    l = Node(l = Empty, d = 4, r = Empty),
    d = 5,
    r = Node(l = Empty, d = 6, r = Empty)
  )
)

and a function that sums integers should return 21.

Use only foldLeft on Tree that you have defined above and foldLeft on List[Tree] provided in the Scala standard library.

Edit this cell:

def foldLeftTrees[B](lt: List[Tree])(z: B)(f: (B, Int) => B): B =
  ???
defined function foldLeftTrees

Tests

test(new AnyFlatSpec {
  def sum(trees: List[Tree]): Int = foldLeftTrees(trees)(0){ (acc, d) => acc + d }

  val l1 = List(1, 2, 3)
  val l2 = List(4, 5, 6)
  val t1 = treeFromList(l1)
  val t2 = treeFromList(l2)
  val lt1 = List(t1, t2)

  val l1l2 = l1 ::: l2

  "foldLeftTrees" should "Test Case 1" in { assertResult(21){ sum(lt1) } }

  it should "reverse and flatten" in {
    assertResult( l1l2.reverse ) { foldLeftTrees(lt1)(Nil: List[Int]){ (acc, i) => i :: acc } }
  }
}, 5)
Run starting. Expected test count is: 2
cmd19$Helper$$anon$1:
foldLeftTrees
- should Test Case 1 *** FAILED ***
  scala.NotImplementedError: an implementation is missing
  at scala.Predef$.$qmark$qmark$qmark(Predef.scala:345)
  at ammonite.$sess.cmd18$Helper.foldLeftTrees(cmd18.sc:2)
  at ammonite.$sess.cmd19$Helper$$anon$1.sum(cmd19.sc:2)
  at ammonite.$sess.cmd19$Helper$$anon$1.$anonfun$new$1(cmd19.sc:12)
  at org.scalatest.OutcomeOf.outcomeOf(OutcomeOf.scala:85)
  at org.scalatest.OutcomeOf.outcomeOf$(OutcomeOf.scala:83)
  at org.scalatest.OutcomeOf$.outcomeOf(OutcomeOf.scala:104)
  at org.scalatest.Transformer.apply(Transformer.scala:22)
  at org.scalatest.Transformer.apply(Transformer.scala:20)
  at org.scalatest.flatspec.AnyFlatSpecLike$$anon$5.apply(AnyFlatSpecLike.scala:1832)
  ...
- should reverse and flatten *** FAILED ***
  scala.NotImplementedError: an implementation is missing
  at scala.Predef$.$qmark$qmark$qmark(Predef.scala:345)
  at ammonite.$sess.cmd18$Helper.foldLeftTrees(cmd18.sc:2)
  at ammonite.$sess.cmd19$Helper$$anon$1.$anonfun$new$2(cmd19.sc:15)
  at org.scalatest.OutcomeOf.outcomeOf(OutcomeOf.scala:85)
  at org.scalatest.OutcomeOf.outcomeOf$(OutcomeOf.scala:83)
  at org.scalatest.OutcomeOf$.outcomeOf(OutcomeOf.scala:104)
  at org.scalatest.Transformer.apply(Transformer.scala:22)
  at org.scalatest.Transformer.apply(Transformer.scala:20)
  at org.scalatest.flatspec.AnyFlatSpecLike$$anon$5.apply(AnyFlatSpecLike.scala:1832)
  at org.scalatest.TestSuite.withFixture(TestSuite.scala:196)
  ...
Run completed in 3 milliseconds.
Total number of tests run: 2
Suites: completed 1, aborted 0
Tests: succeeded 0, failed 2, canceled 0, ignored 0, pending 0
*** 2 TESTS FAILED ***
java.lang.AssertionError: assertion failed: an implementation is missing (foldLeftTrees should Test Case 1)
  scala.Predef$.assert(Predef.scala:280)
  ammonite.$sess.cmd0$Helper$$anon$1.apply(cmd0.sc:6)
  org.scalatest.WrapperCatchReporter.doApply(CatchReporter.scala:70)
  org.scalatest.CatchReporter.apply(CatchReporter.scala:36)
  org.scalatest.CatchReporter.apply$(CatchReporter.scala:34)
  org.scalatest.WrapperCatchReporter.apply(CatchReporter.scala:63)
  org.scalatest.Suite$.reportTestFailed(Suite.scala:1644)
  org.scalatest.SuperEngine.runTestImpl(Engine.scala:347)
  org.scalatest.flatspec.AnyFlatSpecLike.runTest(AnyFlatSpecLike.scala:1842)
  org.scalatest.flatspec.AnyFlatSpecLike.runTest$(AnyFlatSpecLike.scala:1824)
  org.scalatest.flatspec.AnyFlatSpec.runTest(AnyFlatSpec.scala:1686)
  org.scalatest.flatspec.AnyFlatSpecLike.$anonfun$runTests$1(AnyFlatSpecLike.scala:1900)
  org.scalatest.SuperEngine.$anonfun$runTestsInBranch$1(Engine.scala:413)
  scala.collection.immutable.List.foreach(List.scala:333)
  org.scalatest.SuperEngine.traverseSubNodes$1(Engine.scala:401)
  org.scalatest.SuperEngine.runTestsInBranch(Engine.scala:390)
  org.scalatest.SuperEngine.$anonfun$runTestsInBranch$1(Engine.scala:427)
  scala.collection.immutable.List.foreach(List.scala:333)
  org.scalatest.SuperEngine.traverseSubNodes$1(Engine.scala:401)
  org.scalatest.SuperEngine.runTestsInBranch(Engine.scala:396)
  org.scalatest.SuperEngine.runTestsImpl(Engine.scala:475)
  org.scalatest.flatspec.AnyFlatSpecLike.runTests(AnyFlatSpecLike.scala:1900)
  org.scalatest.flatspec.AnyFlatSpecLike.runTests$(AnyFlatSpecLike.scala:1899)
  org.scalatest.flatspec.AnyFlatSpec.runTests(AnyFlatSpec.scala:1686)
  org.scalatest.Suite.run(Suite.scala:1114)
  org.scalatest.Suite.run$(Suite.scala:1096)
  org.scalatest.flatspec.AnyFlatSpec.org$scalatest$flatspec$AnyFlatSpecLike$$super$run(AnyFlatSpec.scala:1686)
  org.scalatest.flatspec.AnyFlatSpecLike.$anonfun$run$1(AnyFlatSpecLike.scala:1945)
  org.scalatest.SuperEngine.runImpl(Engine.scala:535)
  org.scalatest.flatspec.AnyFlatSpecLike.run(AnyFlatSpecLike.scala:1945)
  org.scalatest.flatspec.AnyFlatSpecLike.run$(AnyFlatSpecLike.scala:1943)
  org.scalatest.flatspec.AnyFlatSpec.run(AnyFlatSpec.scala:1686)
  ammonite.$sess.cmd0$Helper.assertPassed(cmd0.sc:4)
  ammonite.$sess.cmd0$Helper.test(cmd0.sc:17)
  ammonite.$sess.cmd19$Helper.<init>(cmd19.sc:17)
  ammonite.$sess.cmd19$.<clinit>(cmd19.sc:7)

25.2 flatMap

Exercise 25.11 (5 points) Recall the flatMap function from class on List. Write a new function flatMapNoRec that implements the same behavior without direct recursion; instead, use foldRight and :::.

Edit this cell:

def flatMapNoRec[A, B](l: List[A])(f: A => List[B]): List[B] = 
  ???
defined function flatMapNoRec

Tests

test(new AnyFlatSpec {
  def duplicate[A](l: List[A]) = flatMapNoRec(l) { a => List(a, a) }

  val l1 = List(1, 2, 3)
  val r1 = List(1, 1, 2, 2, 3, 3)

  "flatMapNoRec" should "Test Case 1" in { assertResult(r1) { duplicate(l1) } }
}, 5)
Run starting. Expected test count is: 1
cmd21$Helper$$anon$1:
flatMapNoRec
- should Test Case 1 *** FAILED ***
  scala.NotImplementedError: an implementation is missing
  at scala.Predef$.$qmark$qmark$qmark(Predef.scala:345)
  at ammonite.$sess.cmd20$Helper.flatMapNoRec(cmd20.sc:2)
  at ammonite.$sess.cmd21$Helper$$anon$1.duplicate(cmd21.sc:2)
  at ammonite.$sess.cmd21$Helper$$anon$1.$anonfun$new$1(cmd21.sc:7)
  at org.scalatest.OutcomeOf.outcomeOf(OutcomeOf.scala:85)
  at org.scalatest.OutcomeOf.outcomeOf$(OutcomeOf.scala:83)
  at org.scalatest.OutcomeOf$.outcomeOf(OutcomeOf.scala:104)
  at org.scalatest.Transformer.apply(Transformer.scala:22)
  at org.scalatest.Transformer.apply(Transformer.scala:20)
  at org.scalatest.flatspec.AnyFlatSpecLike$$anon$5.apply(AnyFlatSpecLike.scala:1832)
  ...
Run completed in 1 millisecond.
Total number of tests run: 1
Suites: completed 1, aborted 0
Tests: succeeded 0, failed 1, canceled 0, ignored 0, pending 0
*** 1 TEST FAILED ***
java.lang.AssertionError: assertion failed: an implementation is missing (flatMapNoRec should Test Case 1)
  scala.Predef$.assert(Predef.scala:280)
  ammonite.$sess.cmd0$Helper$$anon$1.apply(cmd0.sc:6)
  org.scalatest.WrapperCatchReporter.doApply(CatchReporter.scala:70)
  org.scalatest.CatchReporter.apply(CatchReporter.scala:36)
  org.scalatest.CatchReporter.apply$(CatchReporter.scala:34)
  org.scalatest.WrapperCatchReporter.apply(CatchReporter.scala:63)
  org.scalatest.Suite$.reportTestFailed(Suite.scala:1644)
  org.scalatest.SuperEngine.runTestImpl(Engine.scala:347)
  org.scalatest.flatspec.AnyFlatSpecLike.runTest(AnyFlatSpecLike.scala:1842)
  org.scalatest.flatspec.AnyFlatSpecLike.runTest$(AnyFlatSpecLike.scala:1824)
  org.scalatest.flatspec.AnyFlatSpec.runTest(AnyFlatSpec.scala:1686)
  org.scalatest.flatspec.AnyFlatSpecLike.$anonfun$runTests$1(AnyFlatSpecLike.scala:1900)
  org.scalatest.SuperEngine.$anonfun$runTestsInBranch$1(Engine.scala:413)
  scala.collection.immutable.List.foreach(List.scala:333)
  org.scalatest.SuperEngine.traverseSubNodes$1(Engine.scala:401)
  org.scalatest.SuperEngine.runTestsInBranch(Engine.scala:390)
  org.scalatest.SuperEngine.$anonfun$runTestsInBranch$1(Engine.scala:427)
  scala.collection.immutable.List.foreach(List.scala:333)
  org.scalatest.SuperEngine.traverseSubNodes$1(Engine.scala:401)
  org.scalatest.SuperEngine.runTestsInBranch(Engine.scala:396)
  org.scalatest.SuperEngine.runTestsImpl(Engine.scala:475)
  org.scalatest.flatspec.AnyFlatSpecLike.runTests(AnyFlatSpecLike.scala:1900)
  org.scalatest.flatspec.AnyFlatSpecLike.runTests$(AnyFlatSpecLike.scala:1899)
  org.scalatest.flatspec.AnyFlatSpec.runTests(AnyFlatSpec.scala:1686)
  org.scalatest.Suite.run(Suite.scala:1114)
  org.scalatest.Suite.run$(Suite.scala:1096)
  org.scalatest.flatspec.AnyFlatSpec.org$scalatest$flatspec$AnyFlatSpecLike$$super$run(AnyFlatSpec.scala:1686)
  org.scalatest.flatspec.AnyFlatSpecLike.$anonfun$run$1(AnyFlatSpecLike.scala:1945)
  org.scalatest.SuperEngine.runImpl(Engine.scala:535)
  org.scalatest.flatspec.AnyFlatSpecLike.run(AnyFlatSpecLike.scala:1945)
  org.scalatest.flatspec.AnyFlatSpecLike.run$(AnyFlatSpecLike.scala:1943)
  org.scalatest.flatspec.AnyFlatSpec.run(AnyFlatSpec.scala:1686)
  ammonite.$sess.cmd0$Helper.assertPassed(cmd0.sc:4)
  ammonite.$sess.cmd0$Helper.test(cmd0.sc:17)
  ammonite.$sess.cmd21$Helper.<init>(cmd21.sc:8)
  ammonite.$sess.cmd21$.<clinit>(cmd21.sc:7)

Now, we will try to use flatMap to do something useful.

Exercise 25.12 (5 points) Write a function getAllWords that takes in a List[String] of sentences and returns a List[String] of all the words in the sentences. For simplicity, our sentences will have no punctuation, and all words will be separated by a single space. For example, given the input List("I love 3155", "Anish is the best TA"), the getAllWords function should return List("I", "love", "3155", "Anish", "is", "the", "best", "TA").

Use the String method split to separate a sentence into its component words:

"Functions are values".split(" ").toList
res22: List[String] = List("Functions", "are", "values")

Edit this cell:

def getAllWords(sentences: List[String]): List[String] = 
  ???
defined function getAllWords

Tests

test(new AnyFlatSpec {
  val l1 = List("I love 3155", "Anish is the best TA")
  val r1 = List("I", "love", "3155", "Anish", "is", "the", "best", "TA")

  "getAllWords" should "Test Case 1" in { assertResult(r1) { getAllWords(l1) } }
}, 5)
Run starting. Expected test count is: 1
cmd24$Helper$$anon$1:
getAllWords
- should Test Case 1 *** FAILED ***
  scala.NotImplementedError: an implementation is missing
  at scala.Predef$.$qmark$qmark$qmark(Predef.scala:345)
  at ammonite.$sess.cmd23$Helper.getAllWords(cmd23.sc:2)
  at ammonite.$sess.cmd24$Helper$$anon$1.$anonfun$new$1(cmd24.sc:5)
  at org.scalatest.OutcomeOf.outcomeOf(OutcomeOf.scala:85)
  at org.scalatest.OutcomeOf.outcomeOf$(OutcomeOf.scala:83)
  at org.scalatest.OutcomeOf$.outcomeOf(OutcomeOf.scala:104)
  at org.scalatest.Transformer.apply(Transformer.scala:22)
  at org.scalatest.Transformer.apply(Transformer.scala:20)
  at org.scalatest.flatspec.AnyFlatSpecLike$$anon$5.apply(AnyFlatSpecLike.scala:1832)
  at org.scalatest.TestSuite.withFixture(TestSuite.scala:196)
  ...
Run completed in 1 millisecond.
Total number of tests run: 1
Suites: completed 1, aborted 0
Tests: succeeded 0, failed 1, canceled 0, ignored 0, pending 0
*** 1 TEST FAILED ***
java.lang.AssertionError: assertion failed: an implementation is missing (getAllWords should Test Case 1)
  scala.Predef$.assert(Predef.scala:280)
  ammonite.$sess.cmd0$Helper$$anon$1.apply(cmd0.sc:6)
  org.scalatest.WrapperCatchReporter.doApply(CatchReporter.scala:70)
  org.scalatest.CatchReporter.apply(CatchReporter.scala:36)
  org.scalatest.CatchReporter.apply$(CatchReporter.scala:34)
  org.scalatest.WrapperCatchReporter.apply(CatchReporter.scala:63)
  org.scalatest.Suite$.reportTestFailed(Suite.scala:1644)
  org.scalatest.SuperEngine.runTestImpl(Engine.scala:347)
  org.scalatest.flatspec.AnyFlatSpecLike.runTest(AnyFlatSpecLike.scala:1842)
  org.scalatest.flatspec.AnyFlatSpecLike.runTest$(AnyFlatSpecLike.scala:1824)
  org.scalatest.flatspec.AnyFlatSpec.runTest(AnyFlatSpec.scala:1686)
  org.scalatest.flatspec.AnyFlatSpecLike.$anonfun$runTests$1(AnyFlatSpecLike.scala:1900)
  org.scalatest.SuperEngine.$anonfun$runTestsInBranch$1(Engine.scala:413)
  scala.collection.immutable.List.foreach(List.scala:333)
  org.scalatest.SuperEngine.traverseSubNodes$1(Engine.scala:401)
  org.scalatest.SuperEngine.runTestsInBranch(Engine.scala:390)
  org.scalatest.SuperEngine.$anonfun$runTestsInBranch$1(Engine.scala:427)
  scala.collection.immutable.List.foreach(List.scala:333)
  org.scalatest.SuperEngine.traverseSubNodes$1(Engine.scala:401)
  org.scalatest.SuperEngine.runTestsInBranch(Engine.scala:396)
  org.scalatest.SuperEngine.runTestsImpl(Engine.scala:475)
  org.scalatest.flatspec.AnyFlatSpecLike.runTests(AnyFlatSpecLike.scala:1900)
  org.scalatest.flatspec.AnyFlatSpecLike.runTests$(AnyFlatSpecLike.scala:1899)
  org.scalatest.flatspec.AnyFlatSpec.runTests(AnyFlatSpec.scala:1686)
  org.scalatest.Suite.run(Suite.scala:1114)
  org.scalatest.Suite.run$(Suite.scala:1096)
  org.scalatest.flatspec.AnyFlatSpec.org$scalatest$flatspec$AnyFlatSpecLike$$super$run(AnyFlatSpec.scala:1686)
  org.scalatest.flatspec.AnyFlatSpecLike.$anonfun$run$1(AnyFlatSpecLike.scala:1945)
  org.scalatest.SuperEngine.runImpl(Engine.scala:535)
  org.scalatest.flatspec.AnyFlatSpecLike.run(AnyFlatSpecLike.scala:1945)
  org.scalatest.flatspec.AnyFlatSpecLike.run$(AnyFlatSpecLike.scala:1943)
  org.scalatest.flatspec.AnyFlatSpec.run(AnyFlatSpec.scala:1686)
  ammonite.$sess.cmd0$Helper.assertPassed(cmd0.sc:4)
  ammonite.$sess.cmd0$Helper.test(cmd0.sc:17)
  ammonite.$sess.cmd24$Helper.<init>(cmd24.sc:6)
  ammonite.$sess.cmd24$.<clinit>(cmd24.sc:7)