7  Exercise: Expressions and Data Types

\(\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}} \)

The purpose of this assignment is to warm-up with Scala.

Learning Goals

The primary learning goals of this assignment are to build intuition for the following:

  • thinking in terms of types, values, and expressions; and
  • imperative iteration.

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. In Scala, it is also an expression that throws a NotImplementedError exception. 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.

7.1 Type Checking

In the following, I have left off the return type of function g. The body of g is well-typed if we can come up with a valid return type. In this question, we will reason for ourselves that g is indeed well-typed.

def g(x: Int) = /*e1*/({
  // env1
  val (a, b) = /*e2*/(
    // env2
    (1, (x, 3))
  )
  /*e3*/(
    // env3
    if (x == 0) (b, 1) else (b, a + 2)
  )
})
defined function g

We have added parentheses around 3 key sub-expressions of the body of g (e.g., /*e1*/(\(\ldots\))) and noted that there are corresponding environments (e.g., // env1 for each sub-expression).

Exercise 7.1 (2 points) What is the type environment env1? Briefly explain.

Use either format shown in Section 4.1.1 (e.g., \([ x_1 : \tau_1, \ldots, x_n : \tau_n ]\)).

???

Exercise 7.2 (2 points) What is the type environment env2? Briefly explain.

???

Exercise 7.3 (10 points) Derive the type of expression e2.

Showing the type for each sub-expression of e2; stop when you reach literals or variable uses.

???

Notes

Use the format shown in Section 3.2.1. . Here’s such a derivation for the type of the expression (1 + 2) + (3 + 4).

(1 + 2) + (3 + 4): Int
- if 1 + 2: Int
  - if 1: Int
  - if 2: Int
- if 3 + 4: Int
  - if 3: Int
  - if 4: Int

Exercise 7.4 (2 points) What is the type environment env3? Briefly explain.

???

Exercise 7.5 (2 points) Derive the type of expression e3. {.unnumbered}

???

Exercise 7.6 (9 points) Confirm your derivations by adding type assertions to each sub-expression of g and adding the return type of g.

That is, replace sub-expressions \(e\) of g with expressions \(e\) : \(\tau\). You may need to add some parentheses—( \(e\) : \(\tau\) )—to preserve the syntactic structure. Skip adding typing assertions for literals and variable uses.

Edit this cell:

def g(x: Int) = /*e1*/({
  // env1
  val (a, b) = /*e2*/(
    // env2
    (1, (x, 3))
  )
  /*e3*/(
    // env3
    if (x == 0) (b, 1) else (b, a + 2)
  )
})
defined function g

???

Hint: There are 8 sub-expressions that are not literals nor variable uses that need typing assertions (i.e., \(e\) : \(\tau\)), plus 1 more annotation for the return type of g.

7.2 Unit Testing

When starting to program in the large, it is useful to use a testing framework to manage tests and integrate with IDEs. One that is commonly used in Scala is ScalaTest.

While it is somewhat overkill for testing small exercises like the ones to come, we practice here writing tests using ScalaTest.

To load the ScalaTest library, run the following cell:

// RUN this cell FIRST before testing
import $ivy.`org.scalatest::scalatest:3.2.19`, org.scalatest._, events._, flatspec._
def report(suite: Suite) = suite.execute(stats = true)
def assertPassed(suite: Suite) =
  suite.run(None, Args(new Reporter {
    def apply(e: Event) = e match {
      case e @ (_: TestFailed) => assert(false, s"${e.message} (${e.testName})")
      case _ => ()
    }
  }))
def test(suite: Suite) = {
  report(suite)
  assertPassed(suite)
}
import $ivy.$                                , org.scalatest._, events._, flatspec._
defined function report
defined function assertPassed
defined function test

Exercise 7.7 (3 points) Unit Test plus. For this question, edit the next two code cells to fix the implementation of plus and add the appropriate assertion for the third test case "add (3,4) == 7".

Our goal is unit test the following complicated function (that we’ve gotten wrong!):

def plus(n: Int, m: Int): Int =
  ???
defined function plus

To use ScalaTest, we create “Spec” objects using ScalaTest methods like should that define an embedded domain-specific language (DSL) for defining tests:

val plusSuite = new AnyFlatSpec {
  // Define a *subject* to test (e.g., "plus").
  // After `should`, name a test (e.g, "add (1, 1) == 2").
  // After `in`, specify assertions (e.g., `assert(plus(1,1) == 2))
  "plus" should "add 1 + 1 == 2" in {
    // Specify assertions here.
    assert(plus(1,1) == 2)
  }

  it should "add 2 + 2 == 4" in {
    // It is convenient to distinguish the expected result from the code that
    // you're testing, which affects the error messages when the test fails.
    assertResult(2 + 2) {
      plus(2,2)
    }
  }

  it should "add 3 + 4 == 7"  in {
    ???
  }
}
report(plusSuite)
Run starting. Expected test count is: 3
cmd4$Helper$$anon$1:
plus
- should add 1 + 1 == 2 *** FAILED ***
  scala.NotImplementedError: an implementation is missing
  at scala.Predef$.$qmark$qmark$qmark(Predef.scala:345)
  at ammonite.$sess.cmd3$Helper.plus(cmd3.sc:2)
  at ammonite.$sess.cmd4$Helper$$anon$1.$anonfun$new$1(cmd4.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)
  ...
- should add 2 + 2 == 4 *** FAILED ***
  scala.NotImplementedError: an implementation is missing
  at scala.Predef$.$qmark$qmark$qmark(Predef.scala:345)
  at ammonite.$sess.cmd3$Helper.plus(cmd3.sc:2)
  at ammonite.$sess.cmd4$Helper$$anon$1.$anonfun$new$2(cmd4.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 add 3 + 4 == 7 *** FAILED ***
  scala.NotImplementedError: an implementation is missing
  at scala.Predef$.$qmark$qmark$qmark(Predef.scala:345)
  at ammonite.$sess.cmd4$Helper$$anon$1.$anonfun$new$3(cmd4.sc:19)
  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)
  at org.scalatest.TestSuite.withFixture$(TestSuite.scala:195)
  ...
Run completed in 71 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 ***
plusSuite: AnyFlatSpec = cmd4$Helper$$anon$1
assertPassed(plusSuite)
java.lang.AssertionError: assertion failed: an implementation is missing (plus should add 1 + 1 == 2)
  scala.Predef$.assert(Predef.scala:280)
  ammonite.$sess.cmd2$Helper$$anon$1.apply(cmd2.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.cmd2$Helper.assertPassed(cmd2.sc:4)
  ammonite.$sess.cmd5$Helper.<init>(cmd5.sc:1)
  ammonite.$sess.cmd5$.<clinit>(cmd5.sc:7)

???

7.3 Run-Time Library

Most languages come with a standard library with support for things like data structures, mathematical operators, string processing, etc. Standard library functions may be implemented in the object language (perhaps for portability) or the meta language (perhaps for implementation efficiency).

For this question, we will implement some library functions in Scala, our meta language, that we can imagine will be part of the run-time for our object language interpreter. In actuality, the main purpose of this exercise is to warm-up with Scala programming.

Exercise 7.8 (4 points) Write and test a function abs {.unnumbered}

Edit this cell:

def abs(n: Double): Double = 
  ???
defined function abs

that returns the absolute value of n. This a function that takes a value of type Double and returns a value of type Double. This function corresponds to the JavaScript library function Math.abs.

Notes

  • Do not use any Scala library functions.

Tests

Edit this cell:

val absSuite = new AnyFlatSpec {
  "abs" should "abs(2) == 2" in {
     assert(abs(2) == 2)
  }
  it should "abs(-2) == 2" in {
     assert(abs(-2) == 2)
  }
  it should "abs(0) == 0" in {
     assert(abs(0) === 0)
  }
  it should "???1" in {
    ???
  }
}
report(absSuite)
Run starting. Expected test count is: 4
cmd7$Helper$$anon$1:
abs
- should abs(2) == 2 *** FAILED ***
  scala.NotImplementedError: an implementation is missing
  at scala.Predef$.$qmark$qmark$qmark(Predef.scala:345)
  at ammonite.$sess.cmd6$Helper.abs(cmd6.sc:2)
  at ammonite.$sess.cmd7$Helper$$anon$1.$anonfun$new$1(cmd7.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 abs(-2) == 2 *** FAILED ***
  scala.NotImplementedError: an implementation is missing
  at scala.Predef$.$qmark$qmark$qmark(Predef.scala:345)
  at ammonite.$sess.cmd6$Helper.abs(cmd6.sc:2)
  at ammonite.$sess.cmd7$Helper$$anon$1.$anonfun$new$2(cmd7.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)
  ...
- should abs(0) == 0 *** FAILED ***
  scala.NotImplementedError: an implementation is missing
  at scala.Predef$.$qmark$qmark$qmark(Predef.scala:345)
  at ammonite.$sess.cmd6$Helper.abs(cmd6.sc:2)
  at ammonite.$sess.cmd7$Helper$$anon$1.$anonfun$new$3(cmd7.sc:9)
  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 ???1 *** FAILED ***
  scala.NotImplementedError: an implementation is missing
  at scala.Predef$.$qmark$qmark$qmark(Predef.scala:345)
  at ammonite.$sess.cmd7$Helper$$anon$1.$anonfun$new$4(cmd7.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)
  at org.scalatest.TestSuite.withFixture(TestSuite.scala:196)
  at org.scalatest.TestSuite.withFixture$(TestSuite.scala:195)
  ...
Run completed in 3 milliseconds.
Total number of tests run: 4
Suites: completed 1, aborted 0
Tests: succeeded 0, failed 4, canceled 0, ignored 0, pending 0
*** 4 TESTS FAILED ***
absSuite: AnyFlatSpec = cmd7$Helper$$anon$1
assertPassed(absSuite)
java.lang.AssertionError: assertion failed: an implementation is missing (abs should abs(2) == 2)
  scala.Predef$.assert(Predef.scala:280)
  ammonite.$sess.cmd2$Helper$$anon$1.apply(cmd2.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.cmd2$Helper.assertPassed(cmd2.sc:4)
  ammonite.$sess.cmd8$Helper.<init>(cmd8.sc:1)
  ammonite.$sess.cmd8$.<clinit>(cmd8.sc:7)

???

Exercise 7.9 (4 points) Write and test a function xor

Edit this cell:

def xor(a: Boolean, b: Boolean): Boolean = 
  ???
defined function xor

that returns the exclusive-or of a and b. The exclusive-or returns true if and only if exactly one of a or b is true.

???

Notes

  • For practice, do not use the Boolean operators. Instead, only use the if- expression and the Boolean literals (i.e., true or false).

Tests

Edit this cell:

val xorSuite = new AnyFlatSpec {
  "xor" should "!xor(true, true)" in {
    assert(!xor(true, true))
  }
  it should "xor(true, false)" in {
    assert(xor(true, false))
  }
  it should "???1" in {
    ???
  }
  it should "???2" in {
    ???
  }
}
report(xorSuite)
Run starting. Expected test count is: 4
cmd10$Helper$$anon$1:
xor
- should !xor(true, true) *** FAILED ***
  scala.NotImplementedError: an implementation is missing
  at scala.Predef$.$qmark$qmark$qmark(Predef.scala:345)
  at ammonite.$sess.cmd9$Helper.xor(cmd9.sc:2)
  at ammonite.$sess.cmd10$Helper$$anon$1.$anonfun$new$1(cmd10.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 xor(true, false) *** FAILED ***
  scala.NotImplementedError: an implementation is missing
  at scala.Predef$.$qmark$qmark$qmark(Predef.scala:345)
  at ammonite.$sess.cmd9$Helper.xor(cmd9.sc:2)
  at ammonite.$sess.cmd10$Helper$$anon$1.$anonfun$new$2(cmd10.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)
  ...
- should ???1 *** FAILED ***
  scala.NotImplementedError: an implementation is missing
  at scala.Predef$.$qmark$qmark$qmark(Predef.scala:345)
  at ammonite.$sess.cmd10$Helper$$anon$1.$anonfun$new$3(cmd10.sc:9)
  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)
  at org.scalatest.TestSuite.withFixture$(TestSuite.scala:195)
  ...
- should ???2 *** FAILED ***
  scala.NotImplementedError: an implementation is missing
  at scala.Predef$.$qmark$qmark$qmark(Predef.scala:345)
  at ammonite.$sess.cmd10$Helper$$anon$1.$anonfun$new$4(cmd10.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)
  at org.scalatest.TestSuite.withFixture(TestSuite.scala:196)
  at org.scalatest.TestSuite.withFixture$(TestSuite.scala:195)
  ...
Run completed in 4 milliseconds.
Total number of tests run: 4
Suites: completed 1, aborted 0
Tests: succeeded 0, failed 4, canceled 0, ignored 0, pending 0
*** 4 TESTS FAILED ***
xorSuite: AnyFlatSpec = cmd10$Helper$$anon$1
assertPassed(xorSuite)
java.lang.AssertionError: assertion failed: an implementation is missing (xor should !xor(true, true))
  scala.Predef$.assert(Predef.scala:280)
  ammonite.$sess.cmd2$Helper$$anon$1.apply(cmd2.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.cmd2$Helper.assertPassed(cmd2.sc:4)
  ammonite.$sess.cmd11$Helper.<init>(cmd11.sc:1)
  ammonite.$sess.cmd11$.<clinit>(cmd11.sc:7)

7.4 Imperative Iteration and Complexity

Exercise 7.10 (5 points) Write a function filterPairsByBound.

Edit this cell:

def filterPairsByBound(list: List[(Int, Int)], k: Int): List[(Int, Int)] = {
  ???
}
defined function filterPairsByBound

that given a list of pairs of integers, for example,

val input1_l = List( (1, 5), (2, 7), (15, 14), (18, 19), (14, 28), (0,0), (35, 24) )
input1_l: List[(Int, Int)] = List(
  (1, 5),
  (2, 7),
  (15, 14),
  (18, 19),
  (14, 28),
  (0, 0),
  (35, 24)
)

output a list consisting of just those pairs \((n_1, n_2)\) in the original list wherein \(|n_1 - n_2| \leq k\) where \(k\) is an integer given as input. Ensure that the order of the elements in the output list is the same as that in the input list.

For the list input1, the expected output, with k == 1, the expected output is as follows:

val input1_k = 1
val output1 = List( (15,14), (18,19), (0,0) )
assert(filterPairsByBound(input1_l, input1_k) == output1)
scala.NotImplementedError: an implementation is missing
  scala.Predef$.$qmark$qmark$qmark(Predef.scala:345)
  ammonite.$sess.cmd12$Helper.filterPairsByBound(cmd12.sc:2)
  ammonite.$sess.cmd14$Helper.<init>(cmd14.sc:3)
  ammonite.$sess.cmd14$.<clinit>(cmd14.sc:7)

With k == 4, the expected output is as follows:

val input2_k = 4
val output2 = List( (1, 5), (15, 14), (18, 19), (0,0) )
assert(filterPairsByBound(input1_l, input2_k) == output2)
scala.NotImplementedError: an implementation is missing
  scala.Predef$.$qmark$qmark$qmark(Predef.scala:345)
  ammonite.$sess.cmd12$Helper.filterPairsByBound(cmd12.sc:2)
  ammonite.$sess.cmd15$Helper.<init>(cmd15.sc:3)
  ammonite.$sess.cmd15$.<clinit>(cmd15.sc:7)

???

Notes

  • Your function must be called filterPairsByBound with two arguments: (1) a list of pairs of integers, and (2) the \(k\) value. It must return a list of pairs of integers.
  • You can use for-loops (or foreach) and the following operators for concatenating elements to a list:
    • ::: appends two lists together.
    • :: puts an element on the front of a list.
  • You can use the List API method reverse. You may also use the Int abs method to obtain the absolute value of an integer (or use your abs function above).
  • You should not use any other List API functions including filter, map, foldLeft, foldRight, etc. Plenty of time to learn them properly later on.
  • Do not try to convert your list to an array or vector so that you can mutate it.
  • If you are unable to solve the problem without violating the restrictions or unsure, ask us.
  • You will need to use var given the above restrictions.

Hints

  • In Scala, pairs of integers have the type (Int, Int).
  • A list containing pairs of integers has the type List[(Int, Int)].
  • Recall from the notes, here is how one iterates over the elements of a list in Scala:
val list = List(1, 2, 3)

for (elt <- list) {
  // do stuff with elt
  println(elt)
}
1
2
3
list: List[Int] = List(1, 2, 3)
  • Append an element to the end of a list and update a var:
var resultList = List(1, 2, 3)
val elt = 42

resultList = resultList :+ elt
  • Or, append an element to the end of a list using list concatenation and update a var:
var resultList = List(1, 2, 3)
val elt = 42

resultList = resultList ::: List(elt)
  • Prepend an element and update a var:
var resultList = List(1, 2, 3)
val elt = 42

resultList = elt :: resultList
  • Warning: The ::: or other operations appending operations take linear \(O(n)\) time where \(n\) is the length of the (left) list. Thus, we will often try to avoid using these operations, but it is ok to use it for this particular part.

Tests

test(new AnyFlatSpec {
  "filterPairsByBound" should "test1" in {
    val lst1 = List((1,1), (-1,1), (1,-1))
    assertResult( List((1,1)) ){ filterPairsByBound(lst1,1) }
   }

  it should "test2" in {
    val lst2 = List((1,2), (2,1), (1,0), (0,1), (1,1))
    assertResult( lst2 ){ filterPairsByBound(lst2,1) }
  }

  it should "test3" in {
    val lst3 = List((1,5), (5,1))
    assertResult( Nil ){ filterPairsByBound(lst3,1) }
  }

  it should "test4" in {
    val lst4 = List((2,5), (1,2), (-5,-4), (4,1))
    assertResult( List((1,2), (-5,-4)) ){ filterPairsByBound(lst4,1) }
  }

  it should "test5" in {
    val lst5 = List( (1, 5), (2, 7), (15, 14), (18, 19), (14, 28), (0,0), (35, 24) )
    assertResult( List((1, 5), (15, 14), (18, 19), (0,0)) ){ filterPairsByBound(lst5,4) }
  }

  it should "test6" in {
    val lst6 = List((1, 2), (2, 1), (1,0), (0,1), (1,1))
    assertResult( List((1,1)) ){ filterPairsByBound(lst6,0) }
  }
})
Run starting. Expected test count is: 6
cmd20$Helper$$anon$1:
filterPairsByBound
- should test1 *** FAILED ***
  scala.NotImplementedError: an implementation is missing
  at scala.Predef$.$qmark$qmark$qmark(Predef.scala:345)
  at ammonite.$sess.cmd12$Helper.filterPairsByBound(cmd12.sc:2)
  at ammonite.$sess.cmd20$Helper$$anon$1.$anonfun$new$1(cmd20.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 test2 *** FAILED ***
  scala.NotImplementedError: an implementation is missing
  at scala.Predef$.$qmark$qmark$qmark(Predef.scala:345)
  at ammonite.$sess.cmd12$Helper.filterPairsByBound(cmd12.sc:2)
  at ammonite.$sess.cmd20$Helper$$anon$1.$anonfun$new$2(cmd20.sc:9)
  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 test3 *** FAILED ***
  scala.NotImplementedError: an implementation is missing
  at scala.Predef$.$qmark$qmark$qmark(Predef.scala:345)
  at ammonite.$sess.cmd12$Helper.filterPairsByBound(cmd12.sc:2)
  at ammonite.$sess.cmd20$Helper$$anon$1.$anonfun$new$3(cmd20.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 test4 *** FAILED ***
  scala.NotImplementedError: an implementation is missing
  at scala.Predef$.$qmark$qmark$qmark(Predef.scala:345)
  at ammonite.$sess.cmd12$Helper.filterPairsByBound(cmd12.sc:2)
  at ammonite.$sess.cmd20$Helper$$anon$1.$anonfun$new$4(cmd20.sc:19)
  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 test5 *** FAILED ***
  scala.NotImplementedError: an implementation is missing
  at scala.Predef$.$qmark$qmark$qmark(Predef.scala:345)
  at ammonite.$sess.cmd12$Helper.filterPairsByBound(cmd12.sc:2)
  at ammonite.$sess.cmd20$Helper$$anon$1.$anonfun$new$5(cmd20.sc:24)
  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 test6 *** FAILED ***
  scala.NotImplementedError: an implementation is missing
  at scala.Predef$.$qmark$qmark$qmark(Predef.scala:345)
  at ammonite.$sess.cmd12$Helper.filterPairsByBound(cmd12.sc:2)
  at ammonite.$sess.cmd20$Helper$$anon$1.$anonfun$new$6(cmd20.sc:29)
  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: 6
Suites: completed 1, aborted 0
Tests: succeeded 0, failed 6, canceled 0, ignored 0, pending 0
*** 6 TESTS FAILED ***
java.lang.AssertionError: assertion failed: an implementation is missing (filterPairsByBound should test1)
  scala.Predef$.assert(Predef.scala:280)
  ammonite.$sess.cmd2$Helper$$anon$1.apply(cmd2.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.cmd2$Helper.assertPassed(cmd2.sc:4)
  ammonite.$sess.cmd2$Helper.test(cmd2.sc:12)
  ammonite.$sess.cmd20$Helper.<init>(cmd20.sc:1)
  ammonite.$sess.cmd20$.<clinit>(cmd20.sc:7)

Exercise 7.11 (7 points) Write a function filterPairsByBoundLinearTime

Edit this cell:

def filterPairsByBoundLinearTime(list: List[(Int, Int)], k: Int): List[(Int, Int)] = {
  ???
}
defined function filterPairsByBoundLinearTime

If you followed the hint and ignored the linear-time warning in the previous part Exercise 7.10, then you would have used the ::: operation to append an element to the end of a list at each step.

for (... <- list) {
  // iterate over a loop
  ...
  newList = newList ::: List(newElement) // This takes O(length of newList).
}

Each ::: operation requires a full list traversal to find the end of newList and then append to it. The overall algorithm thus requires \(O(n^2)\) time where is the length of the original list (also the number of loop iterations).

To illustrate, cut-and-paste and then run this code in a new test cell. Just remember to delete that cell before you submit. It will take a long time to run.

// Create a list of 1,000,000 pairs
val longTestList = (1 to 1000000).map(x => (x, x - 1)).toList
// Run the function you wrote
filterPairsByBound(longTestList, 1)
// This will take a long time to finish.

In this problem, we wish to implement a function filterPairsByBoundLinearTime that solves the exact same problem as the previous part Exercise 7.10 but takes time linear in the size of the input list.

To do so, we would like you to use the :: (read “cons”) operator on a list that prepends an element to the front of a list, instead of :+ or ::: that appends to the back of a list.

You will want to use the List reverse API method:

val list = List(1, 2, 5, 6, 7, 8)
val r = list.reverse
list: List[Int] = List(1, 2, 5, 6, 7, 8)
r: List[Int] = List(8, 7, 6, 5, 2, 1)

The r has the reverse of list, and it works in linear time in the length of list.

The restrictions remain the same as the previous part Exercise 7.10, but we would like you to focus on ensuring that your solution runs in linear time.

???

Tests

test(new AnyFlatSpec {
  "filterPairsByBoundLinearTime" should "test1" in {
    val lst1 = List((1,1), (-1,1), (1,-1))
    assertResult( List((1,1)) ){ filterPairsByBoundLinearTime(lst1,1) }
   }

  it should "test2" in {
    val lst2 = List((1,2), (2,1), (1,0), (0,1), (1,1))
    assertResult( lst2 ){ filterPairsByBoundLinearTime(lst2,1) }
  }

  it should "test3" in {
    val lst3 = List((1,5), (5,1))
    assertResult( Nil ){ filterPairsByBoundLinearTime(lst3,1) }
  }

  it should "test4" in {
    val lst4 = List((2,5), (1,2), (-5,-4), (4,1))
    assertResult( List((1,2), (-5,-4)) ){ filterPairsByBoundLinearTime(lst4,1) }
  }

  it should "test5" in {
    val lst5 = List( (1, 5), (2, 7), (15, 14), (18, 19), (14, 28), (0,0), (35, 24) )
    assertResult( List((1, 5), (15, 14), (18, 19), (0,0)) ){ filterPairsByBoundLinearTime(lst5,4) }
  }

  it should "test6" in {
    val lst6 = List((1, 2), (2, 1), (1,0), (0,1), (1,1))
    assertResult( List((1,1)) ){ filterPairsByBoundLinearTime(lst6,0) }
  }
})
Run starting. Expected test count is: 6
cmd23$Helper$$anon$1:
filterPairsByBoundLinearTime
- should test1 *** FAILED ***
  scala.NotImplementedError: an implementation is missing
  at scala.Predef$.$qmark$qmark$qmark(Predef.scala:345)
  at ammonite.$sess.cmd21$Helper.filterPairsByBoundLinearTime(cmd21.sc:2)
  at ammonite.$sess.cmd23$Helper$$anon$1.$anonfun$new$1(cmd23.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 test2 *** FAILED ***
  scala.NotImplementedError: an implementation is missing
  at scala.Predef$.$qmark$qmark$qmark(Predef.scala:345)
  at ammonite.$sess.cmd21$Helper.filterPairsByBoundLinearTime(cmd21.sc:2)
  at ammonite.$sess.cmd23$Helper$$anon$1.$anonfun$new$2(cmd23.sc:9)
  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 test3 *** FAILED ***
  scala.NotImplementedError: an implementation is missing
  at scala.Predef$.$qmark$qmark$qmark(Predef.scala:345)
  at ammonite.$sess.cmd21$Helper.filterPairsByBoundLinearTime(cmd21.sc:2)
  at ammonite.$sess.cmd23$Helper$$anon$1.$anonfun$new$3(cmd23.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 test4 *** FAILED ***
  scala.NotImplementedError: an implementation is missing
  at scala.Predef$.$qmark$qmark$qmark(Predef.scala:345)
  at ammonite.$sess.cmd21$Helper.filterPairsByBoundLinearTime(cmd21.sc:2)
  at ammonite.$sess.cmd23$Helper$$anon$1.$anonfun$new$4(cmd23.sc:19)
  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 test5 *** FAILED ***
  scala.NotImplementedError: an implementation is missing
  at scala.Predef$.$qmark$qmark$qmark(Predef.scala:345)
  at ammonite.$sess.cmd21$Helper.filterPairsByBoundLinearTime(cmd21.sc:2)
  at ammonite.$sess.cmd23$Helper$$anon$1.$anonfun$new$5(cmd23.sc:24)
  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 test6 *** FAILED ***
  scala.NotImplementedError: an implementation is missing
  at scala.Predef$.$qmark$qmark$qmark(Predef.scala:345)
  at ammonite.$sess.cmd21$Helper.filterPairsByBoundLinearTime(cmd21.sc:2)
  at ammonite.$sess.cmd23$Helper$$anon$1.$anonfun$new$6(cmd23.sc:29)
  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: 6
Suites: completed 1, aborted 0
Tests: succeeded 0, failed 6, canceled 0, ignored 0, pending 0
*** 6 TESTS FAILED ***
java.lang.AssertionError: assertion failed: an implementation is missing (filterPairsByBoundLinearTime should test1)
  scala.Predef$.assert(Predef.scala:280)
  ammonite.$sess.cmd2$Helper$$anon$1.apply(cmd2.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.cmd2$Helper.assertPassed(cmd2.sc:4)
  ammonite.$sess.cmd2$Helper.test(cmd2.sc:12)
  ammonite.$sess.cmd23$Helper.<init>(cmd23.sc:1)
  ammonite.$sess.cmd23$.<clinit>(cmd23.sc:7)

Submission

Submission Instructions

If you are a University of Colorado Boulder student, we use Gradescope for assignment submission. In summary,

GitHub and Gradescope

We use GitHub Classroom for assignment distribution, which gives you a private GitHub repository to work on your assignment. While using GitHub is perhaps overkill for this assignment, it does give you the ability to version and save incremental progress on GitHub (lest your laptop fails) and makes it easier to get help from the course staff. It will also become particularly useful when more files are involved, and it is never too early to get used to the workflow professional software engineers use with Git.

To use use GitHub and Gradescope,

You need to have a GitHub identity and must have your full name in your GitHub profile in case we need to associate you with your submissions.