Me pregunto cómo implementar una Búsqueda de amplitud primero en Scala, usando 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 uso solo mutabilidad local (un var y un mutable Queue), 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?

10
Yann Moisan 27 dic. 2016 a las 17:52

3 respuestas

La mejor respuesta

Una cosa buena acerca de la programación funcional es que puede aprovechar la pereza para separar el recorrido de su estructura de datos de la parte de búsqueda. Esto hace que el código de responsabilidad única sea muy reutilizable:

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

Ahora puede hacer un BFS con breadth_first_traverse(root, f) find (_ == 16) o usar cualquier otra función en Stream para hacer" consultas "ad hoc útiles en una perezosa amplitud de primer plano Stream de su árbol.

10
Karl Bielefeldt 25 jul. 2017 a las 22:24

Esto no ha sido probado, pero creo que funciona:

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

El truco es mantener una Seq de lo que queda por comprobar y, si el elemento actual no coincide, llamarnos con los restos de lo que tuvimos que verificar con los hijos de este nodo adjuntos

1
The Archetypal Paul 27 dic. 2016 a las 16:45

Sobre la base de la respuesta dada por Karl Bielefeldt, aquí hay otra solución (que no involucra ninguna cola y solo usa 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)
}
4
Angad Singh 11 abr. 2018 a las 21:25