How to implement the first width search in Scala using FP

Question

I am wondering how to implement a width search in Scala using functional programming.

Here is my first, unclean 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 variability (a var and mutable Queue ), it is not purely functional.

I came up with a different 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) = sqdequeue 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]) => sqisEmpty || 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? Can cats / scalps be used to remove some patterns?

Answer 1

One good thing about functional programming is that you can use laziness to separate the crawl of your data structure from the search part. This makes a 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 make BFS using breadth_first_traverse(root, f) find (_ == 16) or use any other function in the Stream class to make useful ad hoc “queries” on lazy widths, first flattened by the Stream your tree.

Answer 2

This is not verified, but I think it works:

  def bfs[S](init: S, f: S => Seq[S], finalS: S => Boolean): Option[S] = { def bfshelper(q: Seq[S], f: S => Seq[S], finalS: S => Boolean): Option[S] = q match { case Seq() => None case h +: t if finalS(h) => Some(h) case h +: t => bfshelper(t ++ f(h), f, finalS) } bfshelper(Seq(init), f, finalS) } 

the trick is to save the Seq of what else you need to check, and if the current element does not match, call yourself the rest of what we needed to check with the children of this node appended

Answer 3

Based on Karl Bielefeld's answer, here is another solution.

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