1

这是纯函数式 DFS 例程，它必须拖着Vector[Boolean]进行恒定时间查找。State有没有办法使用monad使它更简洁和易于理解？抱歉这么具体的问题，我已经阅读了一堆关于这个 monad 的帖子，其中包含 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 回答