Yann Moisan Yann Moisan - 3 years ago 146
Scala Question

How to implement breadth first search in Scala with FP

I'm wondering how to implement a Breadth-first search in Scala, using functional programing.

Here is my first, impure, code :

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
}


Although I use only local mutability (a
var
and a mutable
Queue
), it's not purely functional.

I come up with another version :

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)


Is there a better way for both solutions ?
Is it possible to use cats/scalaz to remove some boilerplate ?

Answer Source

One nice thing about functional programming is you can take advantage of laziness to separate the traversal of your data structure from the searching part. This makes for very reusable, single responsibility code:

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))
}

Now you can do a BFS by breadth_first_traverse(root, f) find (_ == 16) or use any other function in the Stream class to do useful ad hoc "queries" on a lazy breadth-first flattened Stream of your tree.

Recommended from our users: Dynamic Network Monitoring from WhatsUp Gold from IPSwitch. Free Download