Разрыв или короткое замыкание в слое Scala

Я написал простой поиск по глубине в Scala с такой рекурсивной функцией:

search(labyrinth, path, goal)

где лабиринт - это спецификация проблемы (как граф или что-то еще), путь - это список, который содержит путь, принятый до сих пор, а цель - спецификация состояния цели. Функция возвращает путь к цели как List и Nil, если путь не найден.

Функция расширяется, например. находит все подходящие следующие узлы (кандидаты), а затем должен рекурсивно называть себя.

Я делаю это с помощью

candidates.foldLeft(Nil){ 
  (solution, next) => 
    if( solution == Nil ) 
      search( labyrinth, next :: path, goal ) 
    else 
      solution 
}

Обратите внимание, что я пропустил некоторые ненужные данные. Пока все работает нормально. Но как только решение найдено внутри вызова foldLeft, это решение просто копируется другой частью if-statement. Есть ли способ избежать этого, разбив foldLeft или, возможно, используя другую функцию вместо foldLeft? На самом деле я, вероятно, мог бы написать версию foldLeft, которая ломается один раз "не нил" возвращается сам. Но есть ли внутри API?

Ответ 1

Я не уверен, что понимаю стремление к короткому замыканию цикла. Стоит ли дорого перебирать кандидатов? Является ли список кандидатов потенциально большим?

Возможно, вы можете использовать метод "find":

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)

}

Ответ 2

Мне нравится решение Mitch Blevins, так как оно идеально подходит для вашего алгоритма. Вы можете быть заинтересованы в моем собственном решении в другую проблему с лабиринтом.