Friday, November 4, 2011

Functional Style Programming Workshop

Sysart Hotspot 2011 featuring Venkat Subramaniam on Desing Patterns in Modern JVM Languages and Programming in Functional Style Workshop was a real pleasure to say the least.

I hope Venkat Subramaniam won't mind if I describe the workshop tasks here.

All tasks should be solved using functional style programming. Only immutable data are allowed. No iterations.

Programming languages supporting functional style programmings are Groovy, Scala, Clojure and many others…

1. Using map() or a similar function create a function transforming a list of strings into a list of tuples where the first element of tuple is a string from the input list, and the second element is the string length.

Example: Given a list of names: "John", "Jack", "Jill", "Sam", "William". The function should transform it into list of tuples: ("John", 4), ("Jack", 4), ("Jill", 4), ("Sam", 3), ("William", 7)

2. Create a function accepting a list of strings and calculating total number of characters in all strings of the list.

Example: Given a list of names: "John", "Jack", "Jill", "Sam", "William". The function result should be 22.

3. Create a function checking if a given number is a perfect one. Sum of all factors (including 1 and the number itself) of a perfect number is exactly twice as more as the number itself.

Example: Given 6. Factors of 6 (result of 6 divided by factor has no remainder) are 1, 2, 3, and 6. Sum of all factors is 12. It is exactly 2 * 6. So, 6 is a perfect number.

Example: Given 15. Factors of 15 are 1, 3, 5, and 15. Sum of all factors is 24. 2 * 15 is 30, but not 24. So, 15 is not a perfect number.

NOTE: The following task is probably Scala specific.

4. Create a function calculating factorial using recursion. Then modify this function to use tail recursion. Use @scala.annotation.tailrec before the function declaration to make sure the implemented recursion is actually a tail recursion.

Scala compiler replaces tail recursion with iteration while generating byte code to save on time and space.

5. Create a recursive function calculating Fibonacci number. While this function calculates result for some number it repeatedly recalculates Fibonacci number for lower numbers. To improve the calculation speed use memoization. Use cache inside the function to save already calculated Fibonacci numbers. Do not calculate Fibonacci number for the same number more than once. And use immutable data structure for cache.

Also create a function to measure other function execution time and use it to see the speed improvement.

Solutions are available here.

Don't be shy to put your solutions into comments.



  2. sherman: #1 - perfect! #2 - there is more concise solution #3 - can be done much better

  3. 1. Solution using Groovy:
    ["John", "Jack", "Jill", "Sam", "William"].collect { [(it): it.length()]}

    2. Solution using Groovy:
    ["John", "Jack", "Jill", "Sam", "William"].sum(0, {it.length()})

    3. Solution using groovy:
    def isIdeal = { n ->
    (1..n).inject(0, {a, b ->
    if (n % b == 0) a + b
    else a
    }) == 2 * n

    Using Scala:
    def isIdeal(n: Int) = (1 to n).reduceLeft((a, b) =>
    n % b match {
    case 0 => a + b
    case _ => a
    }) == 2 * n

    5. Solution using Scala:
    def fibWrapper(n: Int): Int = {
    val initialCache: Map[Int, Int] = Map(-1 -> 0, 0 -> 0, 1 -> 1)
    def fibonacci(i: Int, n: Int, cache: Map[Int, Int]): Int = {
    if (i < n) {
    val left = cache.get(i - 2).get
    val right = cache.get(i - 1).get
    fibonacci(i + 1, n, cache + ((i, left + right)))
    } else {
    cache.get(n - 2).get + cache.get(n - 1).get
    fibonacci(2, n, initialCache)