2016-12-27 7 views
6

機能プログラミングを使用してScalaにBreadth-first searchを実装する方法を知りたいと思います。私は地元の可変性(varと可変Queue)を使用していますが、それは純粋に機能していないのですScalaで幅広いファーストサーチを実装する方法

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を使用して定型文を削除することはできますか?

+0

'Queue'の代わりに(不変の)' List'を使うだけです。 'State'を取り除く - ' cur'は常に待ち行列の先頭です。ツリーの下降時に 'List'を渡してください。 – Dima

+1

'List'はキューではなくスタックではありませんか? –

+0

まあ、あなたはあなたがそれからデータを引っ張っていくところによって決まります。代わりに不変の 'Queue'を使うことができます。これはもう少し効率的ですが、リストベースでもあります。または、最後の要素に一定時間アクセスするために 'IndexedSeq'のようなものです。 – Dima

答えて

6

関数型プログラミングに関する素晴らしい点の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を平坦化あなたの木の。

+0

好奇心の念から、このケースでは 'Iterator'に' Stream'を使う利点がありますか? –

+1

パフォーマンスの違いをどのように比較するのか分かりません。私は 'Iterators'が変更可能で実装が簡潔ではないので' Streams'を選択しました。 –

+0

このコードの 'f'はどうなっていますか? –

1

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

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

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

0

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) 
} 
関連する問題