A good way to reuse a function leads to Scala

Question

Let me clarify my question with an example. This is the standard exponentiation algorithm written with tail recursion in Scala:

def power(x: Double, y: Int): Double = { def sqr(z: Double): Double = z * z def loop(xx: Double, yy: Int): Double = if (yy == 0) xx else if (yy % 2 == 0) sqr(loop(xx, yy / 2)) else loop(xx * x, yy - 1) loop(1.0, y) } 

Here, the sqr method is used to square the loop result. It doesn't seem like a good idea to define a special function for such a simple operation. But we cannot only write loop(..) * loop(..) instead, since it doubles the calculations.

We can also write it with val and without the sqr function:

 def power(x: Double, y: Int): Double = { def loop(xx: Double, yy: Int): Double = if (yy == 0) xx else if (yy % 2 == 0) { val s = loop(xx, yy / 2); s * s } else loop(xx * x, yy - 1) loop(1.0, y) } 

I can’t say that it looks better than the sqr option, since it uses a state variable . The first case is more functional, the second way more Scala - friendly.

In any case, my question is how to deal with situations when you need the result of a postprocess function? Maybe Scala has other ways to achieve this?

Answer 1

You can use the “straight tube”. I have this idea from here: Intermediate variable cache in a single line file .

So,

 val s = loop(xx, yy / 2); s * s 

can be rewritten in

 loop(xx, yy / 2) |> (s => s * s) 

using an implicit conversion like this

 implicit class PipedObject[A](value: A) { def |>[B](f: A => B): B = f(value) } 

---

As Peter pointed out: using an implicit value class

 object PipedObjectContainer { implicit class PipedObject[A](val value: A) extends AnyVal { def |>[B](f: A => B): B = f(value) } } 

to be used in this way

 import PipedObjectContainer._ loop(xx, yy / 2) |> (s => s * s) 

better since it doesn't need a temporary instance (requires Scala> = 2.10).

Answer 2

You use the law that

 x^(2n) = x^n * x^n 

But this is the same as

 x^n * x^n = (x*x)^n 

Therefore, to avoid squaring after recursion, the value in the case when y is equal should be as shown below in the code list.

Thus, a tail call will be possible. Here is the complete code (without knowing Scala, I hope I get the syntax by analogy):

 def power(x: Double, y: Int): Double = { def loop(xx: Double, acc: Double, yy: Int): Double = if (yy == 0) acc else if (yy % 2 == 0) loop(xx*xx, acc, yy / 2) else loop(xx, acc * xx, yy - 1) loop(x, 1.0, y) } 

Here it is in Haskell:

 power2 xn = loop x 1 n where loop xa 0 = a loop xan = if odd n then loop x (a*x) (n-1) else loop (x*x) a (n `quot` 2) 

Answer 3

In my comment, I pointed out that your implementations cannot be optimized using the tail, because in the case where yy % 2 == 0 , there is a recursive call that is not in the tail position. Thus, for large input, this can overflow the stack.

A common solution is your function trampoline, replacing recursive calls with data that can be mapped to "post-processing", such as sqr . The result is then evaluated by the interpreter, which executes the return values, storing them on the heap, and not on the stack.

The Scalaz library provides data type and interpreter implementations.

 import scalaz.Free.Trampoline, scalaz.Trampoline._ def sqr(z: Double): Double = z * z def power(x: Double, y: Int): Double = { def loop(xx: Double, yy: Int): Trampoline[Double] = if (yy == 0) done(xx) else if (yy % 2 == 0) suspend(loop(xx, yy / 2)) map sqr else suspend(loop(xx * x, yy - 1)) loop(1.0, y).run } 

However, there is significant success. In this particular case, I would use the Igno solution to avoid having to call sqr at all. But the technique described above can be useful when you cannot do such an optimization for your algorithm.

Answer 4

In this particular case

• No need for utility functions
• No stupid piping / implications needed

• You need only one standalone recursive call at the end - always give tail recursion

   def power(x: Double, y: Int): Double = if (y == 0) x else { val evenPower = y % 2 == 0 power(if (evenPower) x * x else x, if (evenPower) y / 2 else y - 1) }