Rompere o corto circuito una piega a Scala

Question

Ho scritto una semplice ricerca in profondità in Scala con una funzione ricorsiva del genere:

search(labyrinth, path, goal) 

dove labirinto è una specifica del problema (come grafico o qualsiasi altra cosa), percorso è una lista che contiene il percorso intrapreso finora e l'obiettivo è una specifica dello stato obiettivo. La funzione restituisce un percorso verso l'obiettivo come List e Nil se non è possibile trovare alcun percorso.

La funzione si espande, ad es. trova tutti i nodi successivi adatti (candidati) e quindi deve ricorsivamente chiamarsi.

Faccio questo

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

prega di notare che ho omesso alcuni particolari unescessary. Tutto sta funzionando bene finora. Ma una volta trovata una soluzione all'interno della chiamata foldLeft, questa soluzione viene semplicemente copiata dalla parte else dell'istruzione if. C'è un modo per evitare questo rompendo la piega sinistra o forse utilizzando una funzione diversa invece di foldLeft? In realtà probabilmente potrei scrivere una versione di foldLeft che si interrompe una volta che "not Nil" viene restituito da solo. Ma ce n'è uno all'interno dell'API?

Answer 1

Non sono sicuro di capire il desiderio di cortocircuitare il circuito. È costoso iterare attraverso i candidati? I candidati sono potenzialmente grandi?

Forse si potrebbe utilizzare il metodo "trovare":

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

Se il potenziale di profondità dello spazio di ricerca è di grandi dimensioni, si potrebbe traboccare il vostro stack (montaggio, dato questo nome del sito). Ma questo è un argomento per un altro post.

Per giggles, ecco un'implementazione eseguibile reale. Ho dovuto introdurre una variabile mutabile locale (fullPath) per lo più per pigrizia, ma sono sicuro che potresti portarli fuori.

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

mi piace Mitch Blevins soluzione, in quanto è un partner perfetto per il vostro algoritmo. Potresti essere interessato a my own solution a un altro problema di labirinto.