CODEWITHSUNDEEP
scalaimmutability
Noel M
Noel M

Reputation: 16116

Why are the Scala libraries implemented with mutable state?

Why are some methods in Scala's standard libraries implemented with mutable state?

For instance, the find method as part of scala.Iterator class is implemented as

def find(p: A => Boolean): Option[A] = {
  var res: Option[A] = None
  while (res.isEmpty && hasNext) {
    val e = next()
    if (p(e)) res = Some(e)
  }
  res
}

Which could have been implemented as a @tailrec'd method, perhaps something like

def findNew(p: A => Boolean): Option[A] = {

  @tailrec
  def findRec(e: A): Option[A] = {
    if (p(e)) Some(e)
    else {
      if (hasNext) findRec(next())
      else None
    }
  }

  if (hasNext) findRec(next())
  else None
}

Now I suppose one argument could be the use of mutable state and a while loop could be more efficient, which is understandably very important in library code, but is that really the case over a @tailrec'd method?

Upvotes: 2

Views: 280

Answers (3)

Rex Kerr
Rex Kerr

Reputation: 167891

Scala is not designed for functional purity but for broadly useful capability. Part of this includes trying to have the most efficient implementations of basic library routines (certainly not universally true, but it often is).

As such, if you have two possible interfaces:

trait Iterator[A] { def next: A }
trait FunctionalIterator[A] { def next: (A, FunctionalIterator[A]) }

and the second one is awkward and slower, it's quite sensible to choose the first.

When a functionally pure implementation is superior for the bulk of use cases, you'll typically find the functionally pure one.

And when it comes to simply using a while loop vs. recursion, either one is easy enough to maintain so it's really up to the preferences of the coder. Note that find would have to be marked final in the tailrec case, so while preserves more flexibility:

trait Foo {
  def next: Int
  def foo: Int = {
    var a = next
    while (a < 0) a = next
    a
  }
}

defined trait Foo


trait Bar {
  def next: Int
  @tailrec def bar: Int = {
    val a = next
    if (a < 0) bar else a
  }
}

<console>:10: error: could not optimize @tailrec annotated method bar:
it is neither private nor final so can be overridden
             @tailrec def bar: Int = {
                          ^

There are ways to get around this (nested methods, final, redirect to private method, etc.), but it tends to adds boilerplate to the point where the while is syntactically more compact.

Upvotes: 0

axel22
axel22

Reputation: 32335

In this case the tailrec quite possibly has the same performance as the while loop. I would say that in this case the while loop solution is shorter and more concise.

But, iterators are a mutable abstraction anyway, so the gain of having a tail recursive method to avoid that var, which is local to that short code snippet, is questionable.

Upvotes: 3

Alois Cochard
Alois Cochard

Reputation: 9862

There is no harm in having a mutable state as long as he is not shared.

In your example there is no way the mutable var could be accessed from outside, so it's not possible that this mutable variable change due to a side effect.

It's always good to enforce immutability as much as possible, but when performance matter there is nothing wrong in having some mutability as long as it's constrained in a safe way.

NOTE: Iterator is a data-structure which is not side-effect free and this could lead to some weird behavior, but this is an other story and in no way the reason for designing a method in such way. You'll find method like that in immutable data-structure too.

Upvotes: 4

Related Questions