gpt4 book ai didi

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

转载 作者:行者123 更新时间:2023-12-02 00:05:33 25 4
gpt4 key购买 nike

我用 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 内部有吗?

最佳答案

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

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

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)

}

关于scala - 中断或短路 Scala 中的折叠,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/1595427/

25 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com