如何使用FP在Scala中实现广度优先搜索

Question

我想知道如何使用功能编程在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
  }

虽然我只使用局部可变性(a 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去除一些样板？

Answer 1

关于函数式编程的一个好处是你可以利用懒惰将数据结构的遍历与搜索部分分开.这使得可重复使用的单一责任代码:

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)或者使用Stream类中的任何其他函数来Stream对你的树上的懒惰广度进行有用的临时"查询" .

Answer 2

基于 Karl Bielefeldt 给出的答案，这是另一种解决方案（不涉及任何队列，仅使用 Streams）。

def bfs[T](s: Stream[T], f: T => Stream[T]): Stream[T] = {
    if (s.isEmpty) s
    else s.head #:: bfs(s.tail append f(s.head), f)
}