在Scala中折断或短路折叠

发布时间：2020-12-16 08:52:45 所属栏目：安全来源：网络整理

导读：我在 Scala中编写了一个简单的深度优先搜索,它具有这样的递归函数： search(labyrinth,path,goal) 迷宫是问题的规范(如图或其他),path是一个列表,它保存到目前为止所采用的路径,目标是目标状态的规范.如果没有找到路径,该函数将返回作为List的目标路径和Nil.

我在 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中有一个吗？

解决方法

我不确定我是否理解将回路短路的愿望.迭代候选人是否代价高昂？候选人名单可能很大吗？

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

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

}

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!