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
The purpose of this assignment is to warm-up with Scala.
The primary learning goals of this assignment are to build intuition for the following:
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.
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.
???
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
.
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) =
.run(None, Args(new Reporter {
suitedef 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)
}
"add 2 + 2 == 4" in {
it should // 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)
}
}
"add 3 + 4 == 7" in {
it should ???
}
}
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)
???
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
.
Edit this cell:
val absSuite = new AnyFlatSpec {
"abs" should "abs(2) == 2" in {
assert(abs(2) == 2)
}
"abs(-2) == 2" in {
it should assert(abs(-2) == 2)
}
"abs(0) == 0" in {
it should assert(abs(0) === 0)
}
"???1" in {
it should ???
}
}
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
.
???
if
- expression and the Boolean literals (i.e., true
or false
).Edit this cell:
val xorSuite = new AnyFlatSpec {
"xor" should "!xor(true, true)" in {
assert(!xor(true, true))
}
"xor(true, false)" in {
it should assert(xor(true, false))
}
"???1" in {
it should ???
}
"???2" in {
it should ???
}
}
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)
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)
???
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.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.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).List
API functions including filter
, map
, foldLeft
, foldRight
, etc. Plenty of time to learn them properly later on.var
given the above restrictions.(Int, Int)
.List[(Int, Int)]
.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)
var
:var resultList = List(1, 2, 3)
val elt = 42
= resultList :+ elt resultList
resultList: List[Int] = List(1, 2, 3, 42)
elt: Int = 42
var
:var resultList = List(1, 2, 3)
val elt = 42
= resultList ::: List(elt) resultList
resultList: List[Int] = List(1, 2, 3, 42)
elt: Int = 42
var
:var resultList = List(1, 2, 3)
val elt = 42
= elt :: resultList resultList
resultList: List[Int] = List(42, 1, 2, 3)
elt: Int = 42
:::
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.test(new AnyFlatSpec {
"filterPairsByBound" should "test1" in {
val lst1 = List((1,1), (-1,1), (1,-1))
assertResult( List((1,1)) ){ filterPairsByBound(lst1,1) }
}
"test2" in {
it should val lst2 = List((1,2), (2,1), (1,0), (0,1), (1,1))
assertResult( lst2 ){ filterPairsByBound(lst2,1) }
}
"test3" in {
it should val lst3 = List((1,5), (5,1))
assertResult( Nil ){ filterPairsByBound(lst3,1) }
}
"test4" in {
it should val lst4 = List((2,5), (1,2), (-5,-4), (4,1))
assertResult( List((1,2), (-5,-4)) ){ filterPairsByBound(lst4,1) }
}
"test5" in {
it should 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) }
}
"test6" in {
it should 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 ::: List(newElement) // This takes O(length of newList).
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.
???
test(new AnyFlatSpec {
"filterPairsByBoundLinearTime" should "test1" in {
val lst1 = List((1,1), (-1,1), (1,-1))
assertResult( List((1,1)) ){ filterPairsByBoundLinearTime(lst1,1) }
}
"test2" in {
it should val lst2 = List((1,2), (2,1), (1,0), (0,1), (1,1))
assertResult( lst2 ){ filterPairsByBoundLinearTime(lst2,1) }
}
"test3" in {
it should val lst3 = List((1,5), (5,1))
assertResult( Nil ){ filterPairsByBoundLinearTime(lst3,1) }
}
"test4" in {
it should val lst4 = List((2,5), (1,2), (-5,-4), (4,1))
assertResult( List((1,2), (-5,-4)) ){ filterPairsByBoundLinearTime(lst4,1) }
}
"test5" in {
it should 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) }
}
"test6" in {
it should 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)
If you are a University of Colorado Boulder student, we use Gradescope for assignment submission. In summary,
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.