scala - 中断或短路 Scala 中的折叠

Question

我用 Scala 编写了一个简单的深度优先搜索，其中包含这样的递归函数:

search(labyrinth, path, goal)

其中 labyrinth 是问题的说明(如图表或其他形式)，path 是保存到目前为止所采取路径的列表，goal 是目标状态的说明。该函数以列表形式返回到达目标的路径，如果找不到路径则返回 Nil。

功能扩展，例如找到所有合适的下一个节点(候选)，然后必须递归调用自身。

我这样做

candidates.foldLeft(Nil){ 
  (solution, next) => 
    if( solution == Nil ) 
      search( labyrinth, next :: path, goal ) 
    else 
      solution 
}

请注意，我省略了一些不必要的细节。到目前为止一切都运行良好。但是，一旦在 FoldLeft 调用中找到解决方案，该解决方案就会被 if 语句的 else 部分简单地复制。有没有办法通过破坏foldLeft或者使用不同的函数而不是foldLeft来避免这种情况？实际上，我可能可以编写一个 FoldLeft 版本，一旦我自己返回“not Nil”，它就会中断。但是 API 内部有吗？

Answer 1

我不确定我是否理解短路循环的愿望。迭代候选人的成本是否昂贵？候选人名单可能很大吗？

也许你可以使用“查找”方法:

candidates.find { c =>
  Nil != search( labyrinth, c :: path, goal )
} match {
  case Some(c) => c :: path
  case None => Nil
}

如果搜索空间的潜在深度很大，您可能会溢出堆栈(鉴于此站点名称，很合适)。但是，这是另一篇文章的主题。

为了咯咯笑，这里是一个实际的可运行实现。我不得不引入一个本地可变变量(fullPath)，主要是出于懒惰，但我相信你可以把它们去掉。

object App extends Application {

    // This impl searches for a specific factor in a large int
    type SolutionNode = Int
    case class SearchDomain(number: Int) {
        def childNodes(l: List[Int]): List[Int] = {
            val num = if (l.isEmpty) number else l.head
            if (num > 2) {
                (2 to (num - 1)) find {
                    n => (num % n)==0
                } match {
                    case Some(i) => List(i, num / i)
                    case None => List()
                }
            }
            else List()
        }
    }
    type DesiredResult = Int


    def search ( labyrinth: SearchDomain, path: List[SolutionNode], goal: DesiredResult ): List[SolutionNode] = {

        if ( !path.isEmpty && path.head == goal ) return path
        if ( path.isEmpty ) return search(labyrinth, List(labyrinth.number), goal)

        val candidates: List[SolutionNode] = labyrinth.childNodes(path)
        var fullPath: List[SolutionNode] = List()
        candidates.find { c =>
            fullPath = search( labyrinth, c :: path, goal )
            !fullPath.isEmpty
        } match {
            case Some(c) => fullPath
            case None => Nil
        }
    }

    // Is 5 a factor of 800000000?
    val res = search(SearchDomain(800000000), Nil, 5)
    println(res)

}