scala - 国家Monad在Scala中进行功能广度优先搜索

我正在尝试在Scala中实现功能性广度优先搜索，以计算给定节点与未加权图中的所有其他节点之间的距离。我为此使用了State Monad，签名为:-

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

map ，flatMap，序列，修改等其他功能与标准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本身的成员？

如何使此代码更具性能/简洁/可读性？

最佳答案

首先，我建议将与private def相关的所有bfs移到bfs本身。这是仅用于实现另一个方法的约定。

其次，我建议您不要为此使用State。 State(与大多数monads一样)与合成有关。当您有许多事物都需要访问同一全局状态时，此功能很有用。在这种情况下，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语法的好处之一是匿名函数对您是隐藏的，并且缩进最少。我就写出来

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

脚注:将Node设为Graph的内部类是否有意义？只是一个建议。