7

Scalaz は、ステートフルな計算に対して優れた抽象化を提供します: ST モナド。

ST モナドを使用すると、副作用のある計算を関数形式でキャプチャできます。

Haskell では、そのようなモナドを使用することが、いくつかの命令型アルゴリズムを効率的に実装する唯一の方法だと思います。

しかし、Scala では、必要に応じて変更可能なデータ構造を簡単に使用できます。

私が見つけたのは、Scalaz の関数型の概念を使用すると、計算のオーバーヘッドが発生するということです。たとえば、この質問を参照してください。したがって、望ましい目標が効率の向上である場合、STモナドを使用して関数実装から関数実装に切り替えることは合理的ではないようです。

私が求めているのはこうです：

  • ST モナドを使用するのが合理的なのはいつですか?
  • どのような状況でそれを使用し、それが良い選択だと思われましたか?
4

1 に答える 1

11

Don Stewart が正しく指摘したように、状態モナドではなく ST モナドを探しているようです。だから私の答えはそれについてです。

ST モナドは、Haskell でローカルな可変性を許可するために使用されますが、通常は可変性が許可されていません。たとえば、命令型sum関数を書きたい場合は、ST モナドを使用します。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 にはfor があり、ST モナドが実行STArrayされているときに に変わります。ImmutableArrayこれの良い例は scalaz のバイナリソートの例です。Rúnar Bjarnasonの ST モナドに関するブログ記事も読む価値があります。

于 2013-10-29T12:01:01.470 に答える