How to implement breadth first search in Scala with FP

Building upon the answer given by Karl Bielefeldt, here's another solution (that doesn't involve any queue and just uses 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)
}

This is untested, but i think 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 keep a Seq of what remains to be checked, and, if the current element isn't a match, call ourselves with the remains of what we had to check with the children of this node appended

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.