przerwa lub zwarcie fałdę w Scala

Question

NapisaĹ,em prosty przeszukiwanie w głąb w Scala z funkcji rekurencyjnej tak:

search(labyrinth, path, goal) 

gdzie labiryntowe jest określenie problemów (wykres czy inne), ścieżka to lista, która zawiera dotychczasową ścieżkę, a celem jest określenie stanu celu. Funkcja zwraca ścieżkę do celu jako listę i zero, jeśli nie można znaleźć żadnej ścieżki.

Funkcja zostanie rozwinięta, np. znajduje wszystkie odpowiednie następne węzły (kandydatów), a następnie musi rekurencyjnie nazywać siebie.

zrobić to przez

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

Należy pamiętać, że pominięto kilka unescessary szczegóły. Wszystko do tej pory działa dobrze. Ale gdy rozwiązanie znajdzie się w wywołaniu foldLeft, to rozwiązanie zostanie po prostu skopiowane przez część else instrukcji if. Czy istnieje sposób na uniknięcie tego przez złamanie foldLeft, a może za pomocą innej funkcji zamiast foldLeft? Właściwie mógłbym prawdopodobnie napisać wersję foldLeft, która zrywa się, gdy sam "not Nil" zostanie zwrócony. Ale czy jest tam jeden interfejs API?

Answer 1

Nie jestem pewien, czy rozumiem chęć zwarcia pętli. Czy to jest kosztowne, aby powtórzyć kandydatów? Czy lista kandydatów jest potencjalnie duża?

Może użyć „znaleźć” sposób:

candidates.find { c => 
    Nil != search(labyrinth, c :: path, goal) 
} match { 
    case Some(c) => c :: path 
    case None => Nil 
} 

Jeśli potencjał głębokość przestrzeni poszukiwań jest duża, można przelać swój stack (okucia, biorąc pod uwagę to imię miejscu). Ale jest to temat na inny post.

Dla chichotów, tutaj jest faktyczna działająca implementacja. Musiałem wprowadzić lokalną zmienną zmienną (fullPath) głównie z lenistwa, ale jestem pewien, że mógłbyś to zrobić.

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

Lubię Mitch Blevins rozwiązanie, gdyż jest to idealne dopasowanie do algorytmu. Możesz być zainteresowany my own solution na inny problem z labiryntem.