Thursday, December 10, 2009

Prime Factors Kata in Scala

After practicing the Prime Factors Kata in Ruby a couple of days, I tried the same exercise in Scala.

Except the fact that practicing Katas is a wonderful tool to learn your IDE and optimize your workflow, I think Katas are also great to learn programming languages. You just don't have to think about your programming-problem, you can just think about your language.
Its been a while since I played around with Scala, so i started my daily Kata in Scala to refresh my skills.

The fact that Scala is not just an object oriented language but also a functional language, led me to a complete different solution of the prime factors kata as in Java or Ruby. I took the immutable List of Scala instead of a mutable Array, so I had to build the algorithm in a recursive manner.
Ok, enough talk. Here is my first solution:

// PrimeFactorsTest.scala
import org.junit.Test;
import org.junit.Assert._;
import org.hamcrest.CoreMatchers._;


class PrimeFactorsTest {
 @Test
 def shouldFactorNumbers = {
  Map(
   1  -> Nil,
   2  -> List(2),
   3  -> List(3),
   4  -> List(2,2),
   5  -> List(5),
   6  -> List(2,3),
   7  -> List(7),
   8  -> List(2,2,2),
   9  -> List(3,3),
   10 -> List(2,5),
   (2*2*5*7*13) -> List(2,2,5,7,13)
   
  ).foreach{ case (n, factors) => 
   assertThat(PrimeFactors.of(n), is(equalTo(factors)))
  }
 }
}
// PrimeFactors.scala
object PrimeFactors {

 def of(n:Int) : List[Int] = tryFactor(2, n)
 
 private def tryFactor(divider: Int, n: Int) : List[Int] = 
  if (n > 1) 
   takeIfFactorElseTryNext(divider, n) 
  else 
   Nil
 
 private def takeIfFactorElseTryNext(divider: Int, n: Int) : List[Int] = 
  if (n % divider == 0) 
   divider :: takeIfFactorElseTryNext(divider, n/divider) 
  else 
   tryFactor(divider+1, n)
}

EDIT:
A few days later, I came to a slightly better solution. I now use a nested function tryFactor to do the recursion. It's nested because in a different context it makes absolutly no sense.
As in my first solution I used object instead of class to create the singleton object PrimeFactors. Again it is not written in tail-recursive style, but Scala obviously optimizes it.

// PrimeFactors.scala
object PrimeFactors {
 
 def of(n:Int) = {
  def tryFactor(n:Int, divider:Int) : List[Int]  =
   if (n == 1) Nil
   else if (n % divider == 0) divider :: tryFactor(n/divider, divider) 
   else tryFactor(n, divider+1)
  
  tryFactor(n, 2)
 }
}