Briser ou court-circuiter un pli dans Scala

Question

J'ai écrit une simple recherche en profondeur d'abord à Scala avec une fonction récursive comme ça:

search(labyrinth, path, goal) 

où labyrinthe est une spécification du problème (comme graphique ou autre), path est une liste qui contient le chemin parcouru jusqu'à présent et l'objectif est une spécification de l'état du but. La fonction renvoie un chemin vers le but sous la forme Liste et Nul si aucun chemin ne peut être trouvé.

La fonction se développe, par ex. trouve tous les prochains noeuds appropriés (candidats) et doit ensuite s'appeler récursivement.

Je le fais par

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

S'il vous plaît noter que j'ai omis quelques détails unescessary. Tout fonctionne bien jusqu'à présent. Mais une fois qu'une solution est trouvée dans l'appel foldLeft, cette solution est simplement copiée par la partie else de l'instruction if. Y at-il un moyen d'éviter cela en cassant foldLeft ou peut-être en utilisant une fonction différente au lieu de foldLeft? En fait, je pourrais probablement écrire une version de foldLeft qui se casse une fois que "not Nil" est retourné moi-même. Mais y a-t-il un dans l'API?

Answer 1

Je ne suis pas sûr de comprendre le désir de court-circuiter la boucle. Est-ce coûteux de parcourir les candidats? La liste des candidats est-elle potentiellement importante?

Peut-être que vous pouvez utiliser la méthode « trouver »:

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

Si la profondeur de l'espace potentiel de recherche est grande, vous pourrait déborder votre pile (montage, étant donné ce nom du site). Mais, c'est un sujet pour un autre poste.

Pour les fous rires, voici une implémentation exécutable réelle. J'ai dû introduire une variable locale mutable (fullPath) principalement par paresse, mais je suis sûr que vous pourriez les retirer.

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

J'aime solution Mitch Blevins, car il est un match parfait pour votre algorithme. Vous pouvez être intéressé par my own solution à un autre problème de labyrinthe.