Homework 3

The purpose of this homework is to practice higher order functions. You cannot use any mutation—no var, no arrays, no Java collections, no mutable Scala collections. No loops. No Scala library functions other than head, tail, isEmpty, ::

Starting with this homework, we will use the sbt project structure. (sbt is the “simple build tool”, the default build tool for Scala.) Submit files with the following directory structure:

cs152 (or whereever you store your git repo)
  hw3
    src
      main
        scala
          hw3.scala (in the default package)
      test
        scala
          MyTestSuite.scala (in the default package)      

If you use IntelliJ, you get this by making a Scala project with sbt (which is the default choice). Be sure to set the location to ~/cs152/hw3 (or whereever you store your git repo).

If you use Eclipse, you need to first install sbt (which is a good idea anyway). Then run

cd cs152 # (or whereever you store your git repo)
echo hw3 | sbt new sbt/scala-seed.g8
cd hw3
sed -i -e 's/Hello/hw3/' build.sbt
rm -rf src/*/scala/example
echo 'addSbtPlugin("com.typesafe.sbteclipse" % "sbteclipse-plugin" % "5.2.4")' > project/plugins.sbt
sbt eclipse

In Eclipse, select File -> Import ... -> General -> Existing Projects into Workspace and navigate to the cs152/hw3 directory.

You don't need to use IntelliJ or Eclipse. You can just use sbt and make a project with

echo hw3 | sbt new sbt/scala-seed.g8

Then you can use any text editor. To run your test cases, simply run

sbt test

in the cs152/hw3 directory.

We will use ScalaTest with the “FunSuite” style which is pretty much like JUnit. Tests look like this:

import org.scalatest.FunSuite

class SetSuite extends FunSuite {

  test("An empty Set should have size 0") {
    assert(Set.empty.size == 0)
  }

  test("Invoking head on an empty Set should produce NoSuchElementException") {
    assertThrows[NoSuchElementException] {
      Set.empty.head
    }
  }
}

IMPORTANT: Be sure to edit your .gitignore file so that you don't upload a lot of unnecessary stuff into your repo! Add these patterns to .gitignore:

.*
*.class
*.jar
**/target/streams/**
**/target/*/resolution-cache/**
**/project/project/**
**/project/target/**

Run

git add --dry-run hw3

to see which files Git would add, and only run git add once you are satisfied that list is clean.

Here is your assignment. Place all functions into an object hw3.

1. Write a function compose that yields the Int => Int function obtained by composing two Int => Int functions (i.e. applies the second function, then the first). Here is a test case:

   test("Composing +1 and *2") {
     assert(hw3.compose(_ + 1, _ * 2)(3) == 7)
   }
   

   Note the order—it's like in math, where (g ∘ f)(x) = g(f(x))
2. Write a function flip that, given an (Int, Int) => Int function, yields an (Int, Int) => Int function with the arguments flipped. Test case:

   test("Flipping args in -") {
     assert(hw3.flip(_ - _)(3, 4) == 1)
     assert(hw3.flip(_ - _)(4, 3) == -1)
   }

3. Write a function zip that accepts two List[Int] and an (Int, Int) => Int function, and that returns a list of results of evaluating the function on corresponding elements. If one list is longer than the other, append the unmatched tail. Test case:

   test("First list longer") {
     assert(hw3.zip(List(1, 2, 3, 4), List(4, 5, 6), _ + _) == List(5, 7, 9, 4))
   }

4. Write a function combineNeighbors that accepts a List[Int] and an (Int, Int) => Int function. Return a List[Int] with the result of combining neighboring elements with the given function. If the list is odd, append the last element. Test case:

   test("Multiplying neighbors, odd length") {
     assert(hw3.combineNeighbors(List(1, 2, 3, 4, 5), _ * _) == List(2, 12, 5))
   }
   

5. Write a function iterateN that takes a starting Int value x, a function f of type Int => Int, and an integer n, and produces a list of length n containing x, f(x), f(f(x)), f(f(f(x))), and so on. Test case:

   test("Iterating * 2 five times") {
     assert(hw3.iterateN(1, _ * 2, 5) == List(1, 2, 4, 8, 16))
   }

6. Write a function iterateWhile that takes a starting Int value x, a function f of type Int => Int, and a function p of type Int => Bool, and produces a list containing x, f(x), f(f(x)), f(f(f(x))), and so on, as long as p returns true for the function values. Test case:

   test("Iterating + 1 while less than 10") {
     assert(hw3.iterateWhile(0, _ + 1, _ < 10) == List(0, 1, 2, 3, 4, 5, 6, 7, 8, 9))
   }
   

7. Write a function iterateUntil that takes a starting Double value x, a function f of type Double => Double, and a function p of type (Double, Double) => Bool, and produces a list containing x, f(x), f(f(x)), f(f(f(x))), and so on, as long as p returns false for the last two function values. Test case:

   test("computing sqrt(2)") {
     assert(hw3.iterateUntil(2, x => (x + 2 / x) / 2, (x, y) => math.abs(x - y) < 1E-8) == List(2.0, 1.5, 1.4166666666666665, 1.4142156862745097, 1.4142135623746899))
   }
   

8. Write a function reduceWithDefault that works like reduce from Lecture 4, except that it has a default for an empty list. Combine the default with the first element, then the result with the second element, and so on. Test case:

   test("Reducing sum with default 0") {
     assert(hw3.reduceWithDefault(0, (1 to 100).toList, _ + _) == 5050)
   }
   

9. Write a function otherReduceWithDefault that works like otherReduce from Lecture 4 Lab Step 4, except that it has a default for an empty list. Combine the last element with the default, then the penultimate list element with the result, and so on. Test case:

   test("Reducing difference with default -1") {
     assert(hw3.otherReduceWithDefault(-1, (1 to 5).toList, _ - _) == 4)
   }

   Unfortunately, I switched the names from Lecture 4. The reduceWithDefault is a left reduction, which was called otherReduce in Lecture 4. otherReduceWithDefault is a right reduction, which was called reduce in Lecture 4. Sorry about that.

10. Write a function both that receives two Int => Boolean functions and returns an Int => Boolean function that returns true when both input functions return true. Test case:

    test("Small and odd") {
      assert(hw3.both(x => x < 10, x => x % 2 == 1)(3))
      assert(!hw3.both(x => x < 10, x => x % 2 == 1)(4))
      assert(!hw3.both(x => x < 10, x => x % 2 == 1)(11))
    }

11. Write a function any that receives a List[Int => Boolean] and returns an Int => Boolean function that returns true when any functions in the list return true. Test case:

    test("Small, odd, or really large") {
      assert(!hw3.any(List(x => x < 10, x => x % 2 == 1, x => x > 1000000))(300))
    }

12. Write one or more test suites that test all your functions to your satisfaction. To make sure that your test classes don't conflict with the grader's, start all suite names with My, such as MyTestSuite or MyComposeSuite.

To test that the grader will be able to run your project, clone your repo into /tmp/cs152, change to the hw3 directory, and run sbt test.