When to use the ST monad in Scala?

Question

Scalaz offers a nice abstraction over stateful computations: The ST monad.

The ST monad allows capturing a side-effecting computation in a functional form.

In Haskell, I suppose, using such a monad is the only way to implement some imperative algorithms efficiently.

But in Scala I can simply use mutable data-structures if necessary.

What I found out is, that using functional concepts from Scalaz comes with a computational overhead. See for example this question. Thus it does not seem reasonable to switch from a functional implementation to a functional implementation using the ST monad, if the desired goal is a gain in efficiency.

What I'm asking is thus:

When is it reasonable to use the ST monad?
In which situations did you use it and it appeared to be a good choice?

"In Haskell, I suppose, using such a monad is the only way to implement some imperative algorithms efficiently." -- that's incorrect. The state monad is a simple, purely functional monad, but for native hardware support for memory effects you use the ST monad. For arbitrary side effects, the IO monad. Perhaps you're looking for the ST monad in Scala? — Don Stewart
@DonStewart You're right. I always found the naming confusing. — ziggystar

drexin drexin · Accepted Answer · 2013-10-29T12:01:01

As Don Stewart correctly pointed out, you seem to be looking for the ST monad and not the state monad. So my answer will be about that.

The ST monad is used to allow local mutability in Haskell where usually no mutability is allowed. For example if you want to write an imperative sum function, you would use the ST monad. An example of such a function with scalaz would be (taken from here):

def sumST[S, A](as: List[A])(implicit A: Numeric[A]): ST[S, A] =
  for { n <- newVar(A.zero)
        _ <- as.traverseU(a => n.mod(A.plus(_, a)))
        m <- n.read } yield m

def sum[A : Numeric](as: List[A]): A =
  runST(new Forall[({type λ[S] = ST[S, A]})#λ] {
    def apply[S] = sumST[S, A](as)
  })

Obviously in scala we could also just write:

def sum[A](xs: List[A])(implicit N: Numeric[A]) = {
  var sum = N.zero
  val it = xs.iterator
  while (it.hasNext) {
    sum = N.plus(sum, it.next)
  }
  sum
}

This would still be referentially transparent, as no mutable state escapes the scope of the function. In Haskell it is used in these cases, because we simply can't have a var.

So why should we use ST in scala? If you want to work on a mutable structure (like an array) and want to guarantee, that this mutable structure will not escape the scope of the computation, but has to be turned into an immutable one first, you can use ST. In scalaz you have the STArray for such cases, which will be turned into an ImmutableArray when the ST monad is being run. A good example for this is the binary sort example in scalaz. Worth reading is also the blog article on ST monad from Rúnar Bjarnason.

When to use the ST monad in Scala?

1 Answers