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

Ok so there are a lot of interpretations here, your question lacks some degrees of specificity.

I will try to point out all assumptions as I go along.

---

Existing Function: (First assumptions: Type signatures)

type Labyrinth // Not particularly important to logic

type Position // The grid "position" of the path

def search(labyrinth: Labyrinth, path: List[Position], goal: Position): List[Position]

---

The function expands, e.g. finds all suitable next nodes (candidates) and then has to recursively call itself.

Assumption: the following code is within the search function

def search(labyrinth: Labyrinth, path: List[Position], goal: Position): List[Position] = {
    ...
    return candidates.foldLeft(Nil){ 
        (solution, next) => 
            if( solution == Nil ) 
                search( labyrinth, next :: path, goal ) 
            else 
                solution 
    }
}

---

Please note that I have omitted some unescessary details.

If my assumptions have been correct, then perhaps, but I still had to deduce some things.

Never assume the necessity of implementation details when asking for assistance on implementation, specificity makes answering questions far simpler.

---

Is there a way to avoid this by breaking the foldLeft or maybe by using a different function instead of foldLeft?

Why not use recursion?

def search(labyrinth: Labyrinth, path: List[Position], goal: Position): List[Position] = {
    ...
    val candidates: List[Position] = ... // However you calculate those

    def resultPathOpt(candidates: List[position]): Option[List[Position]] = {
        candidates match {
                // No candidates
            case Nil => None
                // At least one candidate
            case firstCandidate :: restOfCandidates => {
                    // Search
                search(labyrinth, firstCandidate :: path, goal) match {
                        // Search didn't pan out, no more candidates, done
                    case Nil if restOfCandidates.isEmpty => None
                        // Search didn't pan out, try other candidates
                    case Nil => resultPathOpt(restOfCandidates)
                        // Search panned out, done
                    case validPath => Some(validPath)
                }
        }
    }

    val maybeValidResult: Option[List[Position]] = resultPathOpt(candidates)

    maybeValidResult.getOrElse(List.empty)
}

Now as soon as we find a "valid" path, note there is no check for this in the logic I have provided, so I am not quite sure if this would ever end as you have implemented it and as I have implemented this, but the concepts are still valid.

Answer 2

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 3

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.