我想知道如何实现 Breadth-first search在 Scala 中,使用函数式编程。
这是我的第一个不纯代码:
def bfs[S](init: S, f: S => Seq[S], finalS: S => Boolean): Option[S] = {
val queue = collection.mutable.Queue[S]()
queue += init
var found: Option[S] = None
while (!queue.isEmpty && found.isEmpty) {
val next = queue.dequeue()
if (finalS(next)) {
found = Some(next)
} else {
f(next).foreach { s => queue += s }
}
}
found
}
尽管我只使用了局部可变性(一个
var
和一个可变的 Queue
),但它并不是纯粹的功能性的。我想出了另一个版本:
case class State[S](q: Queue[S], cur: S)
def update[S](f: S => Seq[S])(s: State[S]) : State[S] = {
val (i, q2) = s.q.dequeue
val q3 = f(i).foldLeft(q2) { case (acc, i) => acc.enqueue(i)}
State(q3, i)
}
def bfs2[S](init: S, f: S => Seq[S], finalS: S => Boolean): Option[S] = {
val s = loop(State[S](Queue[S]().enqueue(init), init), update(f) _, (s: State[S]) => s.q.isEmpty || finalS(s.cur))
Some(s.cur)
}
def loop[A](a: A, f: A => A, cond: A => Boolean) : A =
if (cond(a)) a else loop(f(a), f, cond)
这两种解决方案有更好的方法吗?
是否可以使用 cat/scalaz 删除一些样板?
最佳答案
函数式编程的一个好处是您可以利用惰性将数据结构的遍历与搜索部分分开。这使得非常可重用的单一责任代码:
import scala.collection.immutable.Queue
def breadth_first_traverse[Node](node: Node, f: Node => Queue[Node]): Stream[Node] = {
def recurse(q: Queue[Node]): Stream[Node] = {
if (q.isEmpty) {
Stream.Empty
} else {
val (node, tail) = q.dequeue
node #:: recurse(tail ++ f(node))
}
}
node #:: recurse(Queue.empty ++ f(node))
}
现在你可以通过
breadth_first_traverse(root, f) find (_ == 16)
做一个 BFS或使用 Stream 中的任何其他函数类对懒惰的广度优先展平进行有用的临时“查询”Stream
你的树。
关于scala - 如何使用 FP 在 Scala 中实现广度优先搜索,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/41347337/