在Scala中折断或短路折叠

Question

我在Scala中编写了一个简单的深度优先搜索,具有这样的递归函数:

search(labyrinth, path, goal)

迷宫是问题的规范(如图或其他),path是一个列表,它保存到目前为止所采用的路径,目标是目标状态的规范.如果找不到路径,该函数将返回作为List的目标路径和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)

}