如何在FP中使用Scala实现广度优先搜索 [英] How to implement breadth first search in Scala with FP

问题描述

我想知道如何在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 =>队列+ = s} 
} 
} 
找到
} 
  

尽管我只使用局部可变性（一个 var 和一个可变的 Queue ），但它并不是纯粹的功能。

我想出了另一个版本：

  case class State [ S]（q：Queue [S]，cur：S）
 
 def update [S]（f：S => Seq [S]）（s：State [S]）： S] = {
 val（i，q2）= sqdequeue 
 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）：选项[S] = {
 val s =循环（State [S]（Queue [S]（）。enqueue（init），init） ，（s：State [S]）=> sqisEmpty || finalS（s.cur））
 Some（s.cur）
} 
 
 def loop [A ]（a：A，f：A => A，cond：A =>布尔）：A = 
 if（cond（a））else循环（f（a），f，cond）
  

两种解决方案都有更好的方法吗？
是否可以使用cats / scalaz去除一些样板文件？

解决方案

函数式编程的一个好处是你可以利用懒惰来区分数据结构与搜索部分的遍历。这使得非常可重用的单一职责代码：

$ $ p $ import scala.collection.immutable.Queue

def节点]（节点：节点，f：节点=>队列[节点]）：Stream [Node] = {
def recurse（q：Queue [Node]）：Stream [Node] = { b $ b 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） 或使用 Stream 类，在您的树的懒惰宽度优先平铺 Stream 上进行有用的临时查询。

I'm wondering how to implement a Breadth-first search in Scala, using functional programing.

Here is my first, impure, code :

  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
  }

Although I use only local mutability (a var and a mutable Queue), it's not purely functional.

I come up with another version :

  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)

Is there a better way for both solutions ? Is it possible to use cats/scalaz to remove some boilerplate ?

解决方案

One nice thing about functional programming is you can take advantage of laziness to separate the traversal of your data structure from the searching part. This makes for very reusable, single responsibility code:

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

Now you can do a BFS by breadth_first_traverse(root, f) find (_ == 16) or use any other function in the Stream class to do useful ad hoc "queries" on a lazy breadth-first flattened Stream of your tree.

这篇关于如何在FP中使用Scala实现广度优先搜索的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！