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