Functional Programming

Here's a file to be completed: Lab3.scala and DDS.scala, and here's a test driver: lab3Tests.scala.

1.     Problem

Recall that the composition of two functions—f and g-- is h(x) = f(g(x)). Of course the range of g must be a subset of the domain of f. Implement a generic compose combinator.

2.     Problem

Use recursion and your solution to problem 1 to implement the self-composition iterator combinator:

def selfIter[T](f: T=>T, n: Int) = f composed with itself n times.

Test your function with:

def inc(x: Double) = x + 1

def double(x: Double) = 2 * x

Note:

selfIter(f, 0)= id where id(x) = x.

3.     Problem

Write a function called countPass that counts the number of elements in an array of elements of type T that pass a test of type T=>Boolean.

4.     Problem

A. Most traditional-style recursive functions have similar implementations. For example:

def tri(n: Int): Int  = if (n == 0) 0 else n + tri(n – 1)
def fact(n: Int): Int = if (n == 0) 1 else n * fact(n – 1)

Formalize this similarity by implementing a combinator that takes two inputs and returns a recursive function:

def makeRecur(baseVal: Int, combiner: (Int, Int)=>Int): Int=>Int = ???

B. Use your combinator to implement the tri and fact functions above.

5.     Problem

A. Most traditional-style iterative functions have similar implementations. For example:

def tri(n: Int): Int  = {
   var result = 0
   for(i <- 1 to n) result = result + i
   result
}

def fact(n: Int): Int  = {
   var result = 1
   for(i <- 1 to n) result = result * i
   result
}

Formalize this similarity by implementing a combinator that takes two inputs and returns an iterative function:

def makeIter(baseVal: Int, combiner: (Int, Int)=>Int): Int=>Int = ???

B. Use your combinator to implement the tri and fact functions above.

6.     Problem

Some programmers like to handle errors by throwing exceptions, others like to return the optional value, None. Implement a combinator called deOptionize that takes a unary, option-returning function, f, as input and converts it into a non-option returning function g that handles errors by throwing exceptions.

Use your combinator to convert the following function:

def parseDigits(digits: String): Option[Int] = 
   if (digits.matches("[0-9]*")) Some(digits.toInt) else None

7.     Problem

A unit tester tests an arbitrary function f: T => S by applying it to a list of inputs, one at a time, comparing each output to the expected output, then returns the number of errors detected. For example:

def cube(n: Int) = n * n * n

unitTest(cube, Array((1, 1), (2, 8), (3, 9), (4, 64), (5, 124)))

                                                  //> res1: Int = 2

Notes:

·       The first input to the unit tester is the function to be tested: cube.

·       The second input to the unit tester is a partial graph of the desired function.

·       Recall that the graph of a function g is the set of all pairs of the form (x, g(x)).

·       Although the implementation of cube is correct, the unit tester found two errors. This was due to the fact that the specified expected values were incorrect.

Implement and test unitTest.

8.     Problem: Discrete Dynamical Systems

Complete all problems at the bottom of Discrete Dynamical Systems.