Me pregunto cómo implementar unBúsqueda de amplitud en Scala, utilizando programación funcional.

Aquí está mi primer código impuro:

  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
  }

Aunque solo uso mutabilidad local (unvar y una mutableQueue), no es puramente funcional.

Se me ocurre otra versión:

  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)

¿Hay una mejor manera para ambas soluciones? ¿Es posible usar gatos / scalaz para eliminar algunas repeticiones?