How to make this code more functional ?

Question

Hi

I am a newbie in functional programming. I just tried solving the following problem :

[ a rough specification ]

e.g.1:
dividend : {3,5,9}
divisor : {2,2}
radix = 10
ans (remainder) : {7}

Procedure :
dividend = 3*10^2+5*10^1+9*10^0 = 359
similarly, divisor = 22
so 359 % 22 = 7

e.g.2:
dividend : {555,555,555,555,555,555,555,555,555,555}
divisor: {112,112,112,112,112,112,112,112,112,112}
radix = 1000
ans (remainder) : {107,107,107,107,107,107,107,107,107,107}

My solution to this problem is :

object Tornedo {
  def main(args: Array[String]) {
    val radix: BigInt = 1000
    def buildNum(segs: BigInt*) = (BigInt(0) /: segs.toList) { _ * radix + _ }
    val dividend = buildNum(555,555,555,555,555,555,555,555,555,555)
    val divisor = buildNum(112,112,112,112,112,112,112,112,112,112)
    var remainder = dividend % divisor
    var rem = List[BigInt]()
    while(remainder > 0) {
      rem = (remainder % radix) :: rem
      remainder /= radix
    }
    println(rem)
  }
}

Although I am pretty satisfied with this code I'd like to know how to eliminate the while loop & two mutable variables and make this code more functional.

Any help would be greatly appreciated.

Thanks. :)

Answer 1

Tail recursive solution in Scala 2.8:

def reradix(value: BigInt, radix: BigInt, digits:List[BigInt] = Nil): List[BigInt] = {
  if (remainder==0) digits
  else reradix(value/radix ,radix ,(value % radix) :: digits)
}

The idea is generally to convert a while into a recursive solution where you keep track of your solution along the way (so it can be tail recursive, as it is here). If you instead used

(value % radix) :: reradix(value/radix, radix)

you would also compute the solution, but it would not be tail recursive so the partial answers would get pushed onto the stack. With default parameters, adding a final parameter that allows you to store the accumulating answer and use tail recursion is syntactically nice, as you can just call reradix(remainder,radix) and get the Nil passed in for free.

Answer 2

This tail recursive function remove your two mutable var and the loop:

object Tornedo {
  def main(args: Array[String]) {
    val radix: BigInt = 1000
    def buildNum(segs: BigInt*) = (BigInt(0) /: segs.toList) { _ * radix + _ }
    val dividend = buildNum(555,555,555,555,555,555,555,555,555,555)
    val divisor = buildNum(112,112,112,112,112,112,112,112,112,112)
    def breakup(n: BigInt, segs: List[BigInt]): List[BigInt] = 
      if (n == 0) segs else breakup(n / radix, n % radix :: segs)
    println(breakup(dividend % divisor, Nil))
  }
}

Answer 3

I think it's quite expensive way to solve the problem, but very intuitive one IMHO:

scala> Stream.iterate(255)(_ / 10).takeWhile(_ > 0).map(_ % 10).reverse
res6: scala.collection.immutable.Stream[Int] = Stream(2, 5, 5)

Answer 4

Rahul, as I said, there isn't an unfold function in Scala. There is one in Scalaz, so I'm gonna show the solution using that one. The solution below is simply adapting Patrick's answer to use unfold instead of recursion.

import scalaz.Scalaz._

object Tornedo {
  def main(args: Array[String]) {
    val radix: BigInt = 1000
    def buildNum(segs: BigInt*) = (BigInt(0) /: segs.toList) { _ * radix + _ }
    val dividend = buildNum(555,555,555,555,555,555,555,555,555,555)
    val divisor = buildNum(112,112,112,112,112,112,112,112,112,112)
    val unfoldingFunction = (n: BigInt) => 
      if (n == 0) None else Some((n % radix, n / radix))
    println((dividend % divisor).unfold[List, BigInt](unfoldingFunction))
  }
}