Break or shortcircuit a fold in Scala

Question

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?

Answer 1

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)

}

Answer 2

I like Mitch Blevins solution, as it is a perfect match for your algorithm. You may be interested in my own solution to another maze problem.