1

Vector[Boolean]これは、一定時間のルックアップのためにドラッグする必要がある、純粋に機能的な DFS ルーチンです。Stateモナドを使ってもっと簡潔で分かりやすくする方法はありますか? このような具体的な質問で申し訳ありません。このモナドについて、Haskell と Scala の例を含む多くの投稿を読みましたが、まだ理解できません。

object Digraph {
  def apply(n: Int) = new Digraph(n, Vector.fill(n)(List.empty[Int]))
}

class Digraph private (val n: Int, val adj: Vector[List[Int]])  {
  def addEdge(u: Int, v: Int) = new Digraph(n, adj.updated(u, v :: adj(u)))

  def postOrder(s: Int) = {
    def _postOrder(s: Int, ordered: List[Int], visited: Vector[Boolean]): (List[Int], Vector[Boolean]) = {
      val newVisited = visited.updated(s, true)
      val toVisit = adj(s).filter(!newVisited(_))
      val init = (ordered, newVisited)
      val reachable = toVisit.foldLeft(init){(acc, v) => _postOrder(v, acc._1, acc._2)}
      (s::reachable._1, reachable._2)
    }

    _postOrder(s, List[Int](), Vector.fill(n)(false))
  }
}
4

1 に答える 1

2

これは（私が思うに）以下を使用した同等の実装ですscalaz.State：

class Digraph private (val n: Int, val adj: Vector[List[Int]])  {

  def addEdge(u: Int, v: Int) = new Digraph(n, adj.updated(u, v :: adj(u)))

  def postOrder(s: Int): (List[Int], Vector[Boolean]) = {
    type S[A] = State[Vector[Boolean], A]

    def _postOrder(s: Int, ordered: List[Int]): S[List[Int]] =
      for {
        visited   <- init[Vector[Boolean]]
        newVisited = visited.updated(s, true)
        toVisit    = adj(s).filterNot(newVisited)
        _         <- put(newVisited)
        reachable <- toVisit.foldLeftM(ordered){(acc, v) => _postOrder(v, acc)}
      }
      yield s::reachable

    val (a, b) = _postOrder(s, List[Int]()).run(Vector.fill(n)(false))}
    (b, a)
  }
}

残念ながら、使用Stateには Scala で型のボイラープレートが少し必要であり、型コンストラクターを部分的に適用する簡単な方法がありません。型エイリアスSは、これを少し軽減するのに役立ちます。全体として、オリジナルよりもこの実装を選択するかどうかはわかりませんが、おそらく改善される可能性があります。

于 2013-10-17T09:48:44.843 に答える