CODEWITHSUNDEEP
scalarecursionpattern-matchingimplicitimplicit-conversion
agilesteel
agilesteel

Reputation: 16859

Why do I get an infinite loop when using implicit conversions?

Context

object Fibonacci {
  final val Threshold = 30

  def fibonacci(n: Int)(implicit implementation: Fibonacci): Int = implementation match {
    case f: functional.type if n > Threshold => fibonacci(n)(imperativeWithLoop) 
    case f: imperativeWithRecursion.type => f(n)
    case f: imperativeWithLoop.type => f(n)
    case f: functional.type => f(n)
  }

  sealed abstract class Fibonacci extends (Int => Int)

  object functional extends Fibonacci {
    def apply(n: Int): Int =
      if (n <= 1) n else apply(n - 1) + apply(n - 2)
  }

  object imperativeWithRecursion extends Fibonacci {
    def apply(n: Int) = {
      @scala.annotation.tailrec
      def recursion(i: Int, f1: Int, f2: Int): Int =
        if (i == n) f2 else recursion(i + 1, f2, f1 + f2)

      if (n <= 1) n else recursion(1, 0, 1)
    }
  }

  implicit object imperativeWithLoop extends Fibonacci {
    def apply(n: Int) = {
      def loop = {
        var res = 0
        var f1 = 0
        var f2 = 1
        for (i <- 2 to n) {
          res = f1 + f2
          f1 = f2
          f2 = res
        }
        res
      }

      if (n <= 1) n else loop
    }
  }
}

Example

object Main extends App { // or REPL
  import Fibonacci._
  println(fibonacci(6)(imperativeWithRecursion)) // 8
  println(fibonacci(6)(imperativeWithLoop)) // 8
  println(fibonacci(6)(functional)) // 8
  println(fibonacci(6)) // 8
  println(fibonacci(40)(functional)) // 102334155
}

Explanation I was playing with Scala and ended up with this code. It compiles and runs, but...

Questions:

1) Is there any difference (readbility, performance, known bugs, anything) between

case f: functional.type => f(n)

and

case `functional` => functional(n)

This is supposed to be more of a discussion, so I'm not only interested in facts. Any opinion is welcomed.

2) Look at the first line of the fibonacci method. Here it is:

case f: functional.type if n > Threshold => fibonacci(n)(imperativeWithLoop)

If I leave the 2nd parameter list (imperativeWithLoop) out, the code compiles but enters an infinite loop when I run it. Does anyone know why? The default implementation imperativeWithLoop is known to the compiler (no errors are produced). So why doesn't it get implicitly invoked? (I assume it doesn't)

Upvotes: 2

Views: 530

Answers (1)

Daniel C. Sobral
Daniel C. Sobral

Reputation: 297265

Regarding the first question, there are small differences, but none that matter here. But it would be better if you uppercased the objects, in which case you could write this:

case Functional => Functional(n)

Regarding the second question, if you leave out imperativeWithLoop, it will select the implicit Fibonacci closest in scope -- implementation (which has already be found to be equal to funcional). So it will call itself with the exact same parameters as it had called before, and, therefore, enter an infinite loop.

Upvotes: 3

Related Questions