Jak wdrożyć szerokie pierwsze wyszukiwanie w Scali z FP

Question

Zastanawiam się, jak wdrożyć Breadth-first search w Scala, za pomocą funkcjonalnego programowania.

Oto moja pierwsza, nieczyste, kod:

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 
    } 

Chociaż używam tylko lokalną zmienność (a var i zmienny Queue), to nie jest czysto funkcjonalne.

wymyślić innej wersji:

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) 

Czy istnieje lepszy sposób dla obu rozwiązań? Czy możliwe jest użycie kotów/skalazu w celu usunięcia jakiejś płytki?

Answer 1

Jedną dobrą rzeczą w programowaniu funkcjonalnym jest możliwość wykorzystania lenistwa do oddzielenia przejścia struktury danych od części przeszukiwania. To sprawia, że ​​bardzo wielokrotnego użytku, jednym kodem odpowiedzialności:

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

Teraz można zrobić BFS przez breadth_first_traverse(root, f) find (_ == 16) lub używać innych funkcji w klasie Stream robić pożyteczne „zapytań” ad hoc na leniwe wszerz spłaszczone Stream twojego drzewa.

Answer 2

To niesprawdzone, ale myślę, że prace:

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

Sztuką jest zachować nast co pozostaje do sprawdzenia, a jeśli bieżący element nie jest mecz, nazywamy się z resztki tego, co musieliśmy sprawdzić z dziećmi tego węzła dołączonymi

Answer 3

Bazując na odpowiedzi udzielonej przez Karla Bielefeldta, oto inne rozwiązanie.

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