I have written a simple depth-first search in Scala with a recursive function like that:
search(labyrinth, path, goal)
where labyrinth is a specification of the problem (as graph or whatever), path is a list that holds the path taken so far and goal is a specification of the goal state. The function returns a path to the goal as a List and Nil if no path can be found.
The function expands, e.g. finds all suitable next nodes (candidates) and then has to recursively call itself.
I do this by
candidates.foldLeft(Nil){
(solution, next) =>
if( solution == Nil )
search( labyrinth, next :: path, goal )
else
solution
}
Please note that I have omitted some unescessary details. Everything is working fine so far. But once a solution is found inside the foldLeft call, this solution gets simply copied by the else part of the if-statement. Is there a way to avoid this by breaking the foldLeft or maybe by using a different function instead of foldLeft? Actually I could probably write a version of foldLeft which breaks once "not Nil" is returned myself. But is there one inside the API?
I'm not sure I understand the desire to short-circuit the loop. Is it expensive to iterate through the candidates? Is the candidates list potentially large?
Maybe you could use the "find" method:
candidates.find { c =>
Nil != search( labyrinth, c :: path, goal )
} match {
case Some(c) => c :: path
case None => Nil
}
If the potential depth of the search space is large, you could overflow your stack (fitting, given this site name). But, that is a topic for another post.
For giggles, here is an actual runnable implementation. I had to introduce a local mutable variable (fullPath) mostly out of laziness, but I'm sure you could take those out.
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)
}
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With