什么时候在Scala中使用ST monad？

Question

Scalaz提供了对有状态计算的很好的抽象:ST monad.

ST monad允许以功能形式捕获副作用计算.

在Haskell中,我想,使用这样的monad是有效实现某些命令式算法的唯一方法.

但是在Scala中,如果需要,我可以简单地使用可变数据结构.

我发现,使用Scalaz的功能概念带来了计算开销.例如,请参阅此问题.因此,如果期望的目标是效率的提高,那么使用ST monad从功能实现切换到功能实现似乎是不合理的.

我问的是:

• 什么时候使用ST monad是合理的？
• 在哪些情况下你使用它,它似乎是一个很好的选择？

Answer 1

正如唐斯图尔特正确指出的那样,你似乎在寻找ST monad而不是州monad.所以我的答案就是这个.

ST monad用于允许Haskell中的局部可变性,其中通常不允许可变性.例如,如果要编写命令sum功能,则使用ST monad.使用scalaz的这种函数的一个例子是(取自这里):

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)
  })

显然在scala我们也可以写:

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
}

这仍然是引用透明的,因为没有可变状态逃避函数的范围.在Haskell中它用于这些情况,因为我们根本就没有var.

那么我们为什么要在scala中使用ST呢？如果你想处理一个可变结构(比如一个数组)并想要保证,这个可变结构不会逃避计算的范围,但必须首先变成一个不可变的结构,你可以使用ST.在scalaz中你有STArray这样的情况,这些情况将ImmutableArray在ST monad运行时变成.一个很好的例子是scalaz中的二进制排序示例.值得一读的还有来自RúnarBjarnason的ST monad博客文章.