2

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. :)

Improve this question
3
  • I'm not familiar with scala so I cannot adjust your code. For converting this closer to a functional style, the while loop should probably be converted to a tail-recursive function. Of course, if scala doesn't have tail-call optimizations, then that solution is debatable. Commented Feb 19, 2010 at 21:16
  • It could be solved with an unfold function, but Scala doesn't have one. Perhaps Scalaz do. Commented Feb 20, 2010 at 15:03
  • @Daniel : Can you please post that solution here? Commented Feb 20, 2010 at 16:08

4 Answers 4

Reset to default
3

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)) } }
Improve this answer
Sign up to request clarification or add additional context in comments.

Comments

3

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.

Improve this answer

1 Comment

+1 but don't you need to specify result type for recursive function?
3

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)) } }
Improve this answer

4 Comments

+1, Wow! This unfold seems like a very useful function. I wonder why standard library doesn't provide it.
@Rahul Pretty much all of Scalaz is very useful, but it is also very abstract, and much concerned with correctness. It tends heavily to Haskell, and, that I think, is the reason such function don't find their way into Scala std library. Odersky is very much concerned that Scala does not seem daunting and strange to newcomers, and if Scala code often resorted to the likes found in Scalaz, it definitely would feel that way. Be honest, if you didn't know what that code is supposed to do, how easily would you understand it without previous knowledge of unfold?
No, probably not. But same goes for the functions like foldLeft and flatMap too. I didn't know what they were for until I actually studied about them.
@Rahul Well, it's not a clearly defined line -- it isn't even a clearly defined subject! -- and I, myself, constantly complain about the lack of unfold in the standard library. Be as it may, if you enjoyed it, then you should pay attention to Scalaz. This is the least of it.
2

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)
Improve this answer

Comments

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.