I - Functional Programming - Do 1, 2, 5 to 10

To begin:

• In Eclipse create a Scala project called FunctionLab.
• Add a worksheet to this project called session
• Add a Scala interpreter to this project

In the session worksheets define and test the following functions. Your implementations should be as concise as possible.

To end:

• Export session.sc to your file system and send it to the grader by the deadline.

1. Problem

Re-implement compose so that it's as generic as possible. (I.e., it will compose and two "compatible" functions.)

2. Problem

Implement the self-composition iterator function:

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

Test your function with:

definc(x: Double) = x + 1

defdouble(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 (Objects as functions)

Objects can be represented by message dispatcher functions:

defdispatch(msg: String): String = {execute msg}

A constructor creates "objects":

defmakeAccount(initBalance: Double = 0.0) = {

   var balance = initBalance

   var delegate: (String)=>String = (y: String) => "error"

   def dispatch(msg: String)(amt: Double): String = {...}

   dispatch _

}

Here's how the constructor is used:

val savings = makeAccount(100)

val checking = makeAccount(200)

println(savings("withdraw")(30))  // prints $70

println(checking("withdraw")(30)) // prints $170

println(checking("transfer")(30)) // prints error

Complete and test makeAccount.

5. Problem: Control Loop

Find a tail recursive implementation of controlLoop.

6. Problem: Population Growth

A pond of amoebas reproduces asexually until the pond's carrying capacity is reached. More specifically, the initial population of one doubles every week until it exceeds 105. Use your controlLoop function to compute the size of the final population.

7. Problem: Finding Roots of Functions

Newton devised an algorithm for approximating the roots of an arbitrary differential function, f, by iterating:

guess = guess - f(guess)/f'(guess)

Recall that f'(x) is the limit as delta approaches zero of:

(f(x + delta) - f(x))/delta

Use Newton's method and your controlLoop to complete:

defsolve(f: Double=>Double) = r where |f(r)| <= delta

8. Problem: Approximating Square Roots

Use your solve function to complete:

defsquareRoot(x: Double) = solve(???)

9. Problem: Approximating Cube Roots

Use your solve function to complete:

defcubeRoot(x: Double) = solve(???)

10. Problem: Approximating Nth Roots

Use your solve function to complete:

defnthRoot(x: Double, n: Int) = r where |rn - x | <= delta

II - List Processing - Do 6, 7 and 8

To begin:

• In Eclipse create a Scala project called ListLab.
• Add a worksheet to this project called session
• Add a Scala interpreter to this project

In the session worksheet define and test the following functions.

For each function implement four versions:

• Iterative version
• Recursive version
• Tail-recursive version (this should be different from the previous version)
• map-filter-reduce version

All of your implementations should be as generic as possible.

To end:

• Export session.sc to your file system and send it to the grader by the deadline.

1. Problem

Write a function that computes the sum of cubes of all odd numbers occurring in a list of integers.

2. Problem

Write a function that computes the sum of numbers in a list of lists of numbers:

sumOfSums(List(List 1, 2, 3), List(4, 5, 6)) = 21

3. Problem

Write a function that returns the depth of a list of nested lists:

depth(List(List(List 1, 2, List(3)))) = 4

4. Problem

Write a function that computes the average of a list of doubles

5. Problem

Write a function that returns the largest element of a list of comparables.

6. Problem

Write a function that returns the number of elements in a list that satisfy a given predicate. (The predicate is a parameter of type T=>Boolean.)

7. Problem

Write a function that returns true if all elements in a list satisfy a given predicate.

8. Problem

Write a function that returns true if any element in a list satisfies a given predicate.

9. Problem

Write a function that reverses the elements in a list.

10. Problem

Write a function that returns true if a given list of comparables is sorted.

11. Problem: My Map

If the List.map function didn't exist, how would you define it?

12. Problem: Take, Drop and Zip

If take, drop, and zip didn't exist for lists, how would you define them?

13. Problem: Streams

A stream is like a list except that it is constructed using the lazy version of cons:

scala>  val s1 = 1 #:: 2 #:: 3 #:: Stream.Empty

s1: scala.collection.immutable.Stream[Int] = Stream(1, ?)

scala> s1.head

res0: Int = 1

scala> s1.tail.head

res1: Int = 2

Create the following streams

• An infinitely long stream of 1's
• The stream of all non-negative integers
• The stream of all non-negative even integers
• The stream of all squares of integers

14. Problem: Proplog and Logic Programming

A logic program consists of a set of rules and facts:

Conclusion if Condition1 and Condition2 and ...

A fact is simply a conclusion without conditions.

15. Problem

Find an iterative implementation of solve

16. Problem

Find a non-recursive, non-iterative implementation of solve that uses map. filter, and reduce.

III - Recursion - Do 5, 6, 9 and 10

To begin:

• In Eclipse create a Scala project called RecursionLab.
• Add a worksheet to this project called recursionSession
• Add a Scala interpreter to this project

In the session worksheet defines and test the following functions. Your implementations should be recursive.

To end:

• Export session.sc to your file system and send it to the grader by the deadline.

Enter the following definitions into the beginning of your session:

def inc(n: Int) = n + 1

def dec(n: Int) = n - 1

1. Problem

Re-define the function:

add(n: Int, m: Int) = n + m

Your definition should only use recursion, inc, and dec.

2. Problem

Re-define the function:

mul(n: Int, m: Int) = n * m

Your definition should only use recursion, add, inc, and dec.

3. Problem

Re-define the function:

exp2(m: Int) = pow(2, m) // = 2^m

Your definition should only use recursion, add, mul, inc, and dec.

4. Problem

Define the hyper-exponentiation function:

hyperExp(m: Int) = exp(exp(... (exp(1)) ...)) // n-times

Your definition should only use recursion, exp2, add, mul, inc, and dec.

Notes:

• This will probably cause a stack overflow each time it's called.
• hyperExp(0) = 2

5. Problem

Re-implement all of the above functions as tail recursions. Does that improve the stack overflow problem? What about the computation time, is that improved?

6. Problem

At age six Friedrich Gauss discovered an algorithm for tri that uses O(1) space and time! What is it?

7. Problem

Reimplement and test the repl procedure in Calculator.scala without using iteration. Your solution should avoid stack overflow errors.

8. Problem

Implement the following functions using only the solutions for #5.

hyper2Exp(m: Int) = hyperExp(hyperExp(... hyperExp(0)...)) // m-times

hyper3Exp(m: Int) = hyper2Exp(hyper2Exp(... hyper2Exp(0)...)) // m-times

ackermann(N, m) = hyperNExp(m)

9. Problem

Find a recursive and tail recursive implementations of the Fibonacci function.

10. Problem

Find a recursive implementation of:

choose(n, m) = # of ways to choose m things from n

Note: n and m are non-negative integers.

Hint: Pick a special item from the set. Call it x. Then add the number of choices containing x and the number that don't.

11. Problem

Assume two teams, A and B are playing a tournament. The first team that wins k games wins. Assume the probability that either team wins one game is 0.5. Find a recursive implementation of:

probability(n, m) = the probability A wins the tournament assuming A must win n more games and B must win m more games.

Attachment:- Assignment.rar