Scalaで幅広いファーストサーチを実装する方法

Question

機能プログラミングを使用してScalaにBreadth-first searchを実装する方法を知りたいと思います。私は地元の可変性（varと可変Queue）を使用していますが、それは純粋に機能していないのです

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 
    } 

：

は、ここで私の最初の、不純な、コードです。私は別のバージョンを考え出す

：

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) 

は、両方のソリューションのためのより良い方法はありますか？ cat/scalazを使用して定型文を削除することはできますか？

Answer 1

関数型プログラミングに関する素晴らしい点の1つは、データ構造の探索を探索部分から切り離すために怠惰を利用できることです。これは非常に再利用可能な、単一責任のコードになり：

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

今、あなたはbreadth_first_traverse(root, f) find (_ == 16)でBFSを行うか、怠惰な幅優先に関する有用なアドホック「クエリ」を行うためにStreamクラスの他の関数を使用することができますStreamを平坦化あなたの木の。

Answer 2

これはテストされていないですが、私はうまくいくと思う：トリックは現在の要素が一致しない場合は、確認されないままで何の配列を維持し、することです

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

、と自分自身を呼び出しますこのノードの子ノードでチェックしなければならなかったものが残りました

Answer 3

Karl Bielefeldtの答えに基づいて構築してください。別の解決策があります。

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