Showing posts with label kata. Show all posts
Showing posts with label kata. Show all posts

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)
 }
}