使用状态单子在Scala中实现功能广度优先搜索

Question

使用状态单子在Scala中实现功能广度优先搜索

scalafunctional-programmingbreadth-first-searchstate-monad

3

我正在尝试使用Scala实现一个功能性的广度优先搜索算法，用于计算无权图中给定节点与所有其他节点之间的距离。我已经使用了State Monad，并将其签名定义为：

case class State[S,A](run:S => (A,S))

其它函数，例如map、flatMap、sequence、modify等等与标准的State Monad内部所包含的类似。

以下是代码：

case class Node(label: Int)

case class BfsState(q: Queue[Node], nodesList: List[Node], discovered: Set[Node], distanceFromSrc: Map[Node, Int]) {
  val isTerminated = q.isEmpty
}

case class Graph(adjList: Map[Node, List[Node]]) {
  def bfs(src: Node): (List[Node], Map[Node, Int]) = {
    val initialBfsState = BfsState(Queue(src), List(src), Set(src), Map(src -> 0))
    val output = bfsComp(initialBfsState)
    (output.nodesList,output.distanceFromSrc)
  }

  @tailrec
  private def bfsComp(currState:BfsState): BfsState = {
     if (currState.isTerminated) currState
     else bfsComp(searchNode.run(currState)._2)
  }

  private def searchNode: State[BfsState, Unit] = for {
    node <- State[BfsState, Node](s => {
      val (n, newQ) = s.q.dequeue
      (n, s.copy(q = newQ))
    })
    s <- get
    _ <- sequence(adjList(node).filter(!s.discovered(_)).map(n => {
      modify[BfsState](s => {
        s.copy(s.q.enqueue(n), n :: s.nodesList, s.discovered + n, s.distanceFromSrc + (n -> (s.distanceFromSrc(node) + 1)))
      })
    }))
  } yield ()
}

请问：

searchNode函数中出队列时状态转移应该是BfsState的成员吗？
如何使这段代码更高效、简洁和易读？

- Aarsh Shah

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- HTNW · Accepted Answer

首先，我建议将与bfs相关的所有private def移动到bfs本身中。这是仅用于实现其他方法的方法的惯例。

其次，我建议在此情况下根本不使用State。类似大多数单子的State是关于组成的，当您有许多需要访问相同全局状态的东西时它就会很有用。在这种情况下，BfsState专门针对bfs，可能永远不会在其他地方使用（也许将该类移动到bfs中是个好主意），并且State本身总是run，因此外部世界从未看到它。（在许多情况下，这很好，但是在这里，State的范围太小，无法发挥作用。）将searchNode逻辑提取到bfsComp中将更加干净。

第三，我不明白为什么您需要同时使用nodesList和discovered，当您可以在完成计算后调用_.toList来获取discovered的列表。不过，在我的重新实现中保留了它，以防您没有显示更多的代码。

def bfsComp(old: BfsState): BfsState = {
  if(old.q.isEmpty) old // You don't need isTerminated, I think
  else {
    val (currNode, newQ) = old.q.dequeue
    val newState = old.copy(q = newQ)
    adjList(curNode)
      .filterNot(s.discovered) // Set[T] <: T => Boolean and filterNot means you don't need to write !s.discovered(_)
      .foldLeft(newState) { case (BfsState(q, nodes, discovered, distance), adjNode) =>
        BfsState(
          q.enqueue(adjNode),
          adjNode :: nodes,
          discovered + adjNode,
          distance + (adjNode -> (distance(currNode) + 1)
        )
      }
  }
}

def bfs(src: Node): (List[Node], Map[Node, Int]) = {
  // I suggest moving BfsState and bfsComp into this method
  val output = bfsComp(BfsState(Queue(src), List(src), Set(src), Map(src -> 0)))
  (output.nodesList, output.distanceFromSrc)
  // Could get rid of nodesList and say output.discovered.toList
}

如果您认为在这里使用State有充分的理由，以下是我的想法。

您使用了def searchNode。使用State的重点在于它是纯净且不可变的，因此应该是一个val，否则每次使用都需要重新构建相同的State。

您写道：

node <- State[BfsState, Node](s => {
  val (n, newQ) = s.q.dequeue
  (n, s.copy(q = newQ))
})

首先，Scala的语法设计得非常巧妙，你不需要在匿名函数周围同时使用()和{}：

node <- State[BfsState, Node] { s =>
  // ...
}

其次，我觉得这看起来不太对劲。使用for-syntax的好处之一是匿名函数对您隐藏，并且缩进最小化。我会把它写出来。

oldState <- get
(node, newQ) = oldState.q.dequeue
newState = oldState.copy(q = newQ)

注：将Node作为Graph的内部类是否有意义？仅供参考。