Scala Lists – Why Appending Has O(n) Time Complexity

There's one thing that you can do concisely and efficiently in Java that you can't in Scala: enumerations. For everything else, even for constructs that are slow in Scala's library, you can get efficient versions working in Scala.

So, for the most part, you don't need to add Java to your code. Even for code that uses enumeration in Java, there's often a solution in Scala that is adequate or good -- I place the exception on enumerations that have extra methods and whose int constant values are used.

As for what to watch out for, here are some things.

• If you use the enrich my library pattern, always convert to a class. For example:

  // WRONG -- the implementation uses reflection when calling "isWord"
  implicit def toIsWord(s: String) = new { def isWord = s matches "[A-Za-z]+" }
  
  // RIGHT
  class IsWord(s: String) { def isWord = s matches "[A-Za-z]+" }
  implicit def toIsWord(s: String): IsWord = new IsWord(s)
  

• Be wary of collection methods -- because they are polymorphic for the most part, JVM does not optimize them. You need not avoid them, but pay attention to it on critical sections. Be aware that for in Scala is implemented through method calls and anonymous classes.

• If using a Java class, such as String, Array or AnyVal classes that correspond to Java primitives, prefer the methods provided by Java when alternatives exist. For example, use length on String and Array instead of size.

• Avoid careless use of implicit conversions, as you can find yourself using conversions by mistake instead of by design.

• Extend classes instead of traits. For example, if you are extending Function1, extend AbstractFunction1 instead.

• Use -optimise and specialization to get most of Scala.

• Understand what is happening: javap is your friend, and so are a bunch of Scala flags that show what's going on.

• Scala idioms are designed to improve correctness and make the code more concise and maintainable. They are not designed for speed, so if you need to use null instead of Option in a critical path, do so! There's a reason why Scala is multi-paradigm.

• Remember that the true measure of performance is running code. See this question for an example of what may happen if you ignore that rule.

Scala doesn't require an explicit return type on all functions, just recursive ones. The reason for that is that Scala's type inference algorithm is (something close to) a simple scan from beginning to end that is incapable of lookahead.

This means that a function like this:

def fortuneCookieJoke(message: String) = message + " in bed."

doesn't need a return type, since the Scala compiler can clearly see, without using logic variables or looking at anything other than the method's parameters, that the return type must be String.

On the other hand, a function like this:

def mapInts(f: (Int) => Int, l: List[Int]) = l match {
  case Nil => Nil
  case x :: xs => f(x) :: mapInts(f, xs)
}

will cause a compile-time error, because the Scala compiler cannot see, without using either lookahead or logic variables, exactly what the type of mapInts is. The most it could say, if it were smart enough, is that the return type is a supertype of List[Nothing], since Nil is of that type. That doesn't give it anywhere near enough information to accurately determine the return type of mapInts.

Please note that this is specific to Scala, and that there are other statically typed languages (most of the Miranda/Haskell/Clean family, most of the ML family, and a few scattered others) that use much more comprehensive and capable type inference algorithms than Scala uses. Also, be aware that this is not entirely Scala's fault; nominal subtyping and whole-module type inference are fundamentally at odds with each other, and the designers of Scala chose to favor the former over the latter for the sake of Java compatibility, while the "purer" statically typed functional languages were mostly designed with the opposite choice in mind.