scala - 使用 State Monad 在 Scala 中进行功能广度优先搜索

Question

我正在尝试在 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 ()
}   

请您就以下方面提出建议:-

1. searchNode 函数中出队时的状态转换是否应该是 BfsState 本身的成员？
2. 如何使此代码更高效/简洁/可读？

Answer 1

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

其次，我建议在这件事上不要使用 State。 State(像大多数 monad 一样)是关于组合的。当你有很多东西都需要访问同一个全局状态时，它很有用。在这种情况下，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 的内部类是否有意义？只是一个建议。