Saturday, November 19, 2011

Functional Style Programming Workshop: Solutions

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)

Solution in Scala:
def stringsWithLength(strings: List[String]) = strings map {
  string => (string, string.length)
}
Function stringsWithLength() takes a list of strings and creates a new list by applying conversion from a string to a tuple of the same string and its length to every string of the parameter list using map() method of lists.


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.

Solution is Scala:
def stringsTotalLength(strings: List[String]) = (strings map {_.length}).sum
Function stringsTotalLength() takes a list of strings and creates a new list by applying length() method to every string of the parameter list using map() method of lists, and then calculating sum of all lengths in that new list using sum() method.

However, there is one more solutions worth to mention:
def totalStringsLength(strings: List[String]) = strings.foldLeft(0) {
  (sum, string) => sum + string.length
}
This one is a bit more complicated. No new list is created, but sum of string lengths is calculated directly using the parameter list.

The first solution is shorter and simpler. But it takes about 26 microseconds on my computer to process the example strings. While the second solution takes only about 7 microseconds.


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.

Solution in Scala:
def isPerfectNumber(number: Int) = ((1 to number) filter {
  number % _ == 0
}).sum == number * 2
Function isPerfectNumber() takes a number and checks if it's a perfect one. To find all factors of the given number a range from 1 to the number is filtered. Then all the found factors are summed and the sum is checked to be twice as big as the number itself.

Here is a list of perfect numbers: 6, 28, 496, 8128…


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.

Here is implementation using classic recursion:
def factorial(number: Int): Int = {
  if (number <= 1)
    1
  else
    factorial(number - 1) * number
}
And here is tail recursion implementation:
def factorial(number: Int) = {
  @annotation.tailrec
  def factorial(number: Int, result: Int): Int = {
    if (number <= 1)
      result
    else
      factorial(number - 1, result * number)
  }

  factorial(number, 1)
}
In classic recursion case a result of a recursive call of the function to itself is modified.

In tail recursion case a result of a recursive call must not be modified and must be returned right away. Instead of modifying result of the function, the result can be passed as a parameter, because parameters can be modified.

However, the implemented tail recursive function has an additional parameter, while this parameter should not be available to a function user. To hide this additional parameter from users the tail recursive function is embedded into other function.


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.

Solution in Scala:

Here is a recursive Fibonacci function implementation:
def fibonacci(number: Int): Int = {
  if (number <= 0)
    0
  else if (number == 1)
    1
  else
    fibonacci(number - 1) + fibonacci(number - 2)
}
And here is a solution implementing memoization:
def fibonacci(number: Int) = {
  def fibonacci(number: Int): List[Int] = {
    if (number <= 0)
      List(0)
    else if (number == 1)
      1 :: fibonacci(0)
    else {
      val previousResult = fibonacci(number - 1)
      (previousResult.head + previousResult.tail.head) :: previousResult
    }
  }

  fibonacci(number).head
}
Instead of calculation Fibonacci function starting from a given number, the solution starts it from 0 constructing cache of Fibonacci function results in a list returned as a result of the solution internal function. List is immutable collection in Scala.

When prepending a list with a new element, a new list is pointing to that new element, now the first element of the new list, the first element points to the old list first element, and the whole old list is still intact. Both the old and the new lists share the same memory. Adding a new element before a list head is very time and memory effective.

Calculation of Fibonacci function for number 40 using classic recursion takes about 1.25 second on my computer. While solution with memoization takes just about 62 microseconds. It's about 20 thousand times faster.

However, tail recursion takes about 3 microseconds. It's about 20 times even more faster.
def fibonacci(number: Int) = {
  @annotation.tailrec
  def fibonacci(number: Int, prevResult: Int, beforePrevResult: Int): Int = {
    if (number <= 0)
      0
    else if (number == 1)
      prevResult
    else
      fibonacci(number - 1, prevResult + beforePrevResult, prevResult)
  }

  fibonacci(number, 1, 0)
}

No comments:

Post a Comment