Abandonner tôt dans un pli

Quelle est la meilleure façon de terminer un pli tôt? Comme exemple simplifié, imaginez que je veuille résumer les nombres dans une liste, mais si je rencontre quelque chose à quoi je ne m’attends pas (disons un nombre impair), je souhaiterais peut-être terminer. Ceci est une première approximation

 def sumEvenNumbers(nums: Iterable[Int]): Option[Int] = { nums.foldLeft (Some(0): Option[Int]) { case (Some(s), n) if n % 2 == 0 => Some(s + n) case _ => None } } 

Cependant, cette solution est assez moche (comme si, si je faisais un .foreach et un retour – ce serait beaucoup plus propre et plus clair) et le pire de tous, elle traverserait l’intégrale même si elle rencontrait un nombre non pair. .

Alors, quelle serait la meilleure façon d’écrire un tel pli, qui se termine tôt? Dois-je simplement écrire ceci de manière récursive, ou y a-t-il une manière plus acceptée?

Mon premier choix serait généralement d’utiliser la récursivité. Il est modérément moins compact, potentiellement plus rapide (certainement pas plus lent), et une terminaison précoce peut rendre la logique plus claire. Dans ce cas, vous avez besoin de définitions nestedes, ce qui est un peu gênant:

 def sumEvenNumbers(nums: Iterable[Int]) = { def sumEven(it: Iterator[Int], n: Int): Option[Int] = { if (it.hasNext) { val x = it.next if ((x % 2) == 0) sumEven(it, n+x) else None } else Some(n) } sumEven(nums.iterator, 0) } 

Mon second choix serait d’utiliser return , car il conserve tout le rest intact et vous n’avez besoin que d’envelopper le pli dans un def pour que vous ayez quelque chose à retourner – dans ce cas, vous avez déjà une méthode, alors:

 def sumEvenNumbers(nums: Iterable[Int]): Option[Int] = { Some(nums.foldLeft(0){ (n,x) => if ((n % 2) != 0) return None n+x }) } 

ce qui dans ce cas particulier est beaucoup plus compact que la récursivité (bien que nous ayons été particulièrement malchanceux avec la récursivité car nous avons dû effectuer une transformation itérable / iterator). Le stream de contrôle instable est quelque chose à éviter lorsque tout le rest est égal, mais ce n’est pas le cas ici. Pas de mal à l’utiliser dans les cas où c’est précieux.

Si je le faisais souvent et que je le voulais au milieu d’une méthode quelque part (donc je ne pouvais pas simplement utiliser return), j’utiliserais probablement la gestion des exceptions pour générer un stream de contrôle non local. C’est, après tout, ce qui est bon et la gestion des erreurs n’est pas la seule fois utile. La seule astuce consiste à éviter de générer une trace de stack (ce qui est très lent), et c’est facile car le trait NoStackTrace et son trait enfant ControlThrowable font déjà pour vous. Scala l’utilise déjà en interne (en fait, c’est comme ça qu’il implémente le retour de l’intérieur du pli!). Faisons le nôtre (ne peut pas être nested, même si on peut corriger cela):

 import scala.util.control.ControlThrowable case class Returned[A](value: A) extends ControlThrowable {} def shortcut[A](a: => A) = try { a } catch { case Returned(v) => v } def sumEvenNumbers(nums: Iterable[Int]) = shortcut{ Option(nums.foldLeft(0){ (n,x) => if ((x % 2) != 0) throw Returned(None) n+x }) } 

Ici, bien sûr, utiliser return est préférable, mais notez que vous pouvez placer un shortcut n’importe où, et pas seulement encapsuler une méthode entière.

La prochaine étape pour moi serait de réimplémenter le pli (soit moi-même, soit pour trouver une bibliothèque qui le fait) afin qu’il puisse signaler une terminaison précoce. Les deux manières naturelles de le faire sont de ne pas propager la valeur mais une Option contenant la valeur, où None signifie la fin; ou pour utiliser une deuxième fonction d’indicateur signalant l’achèvement. Le pli paresseux Scalaz montré par Kim Stebel couvre déjà le premier cas, donc je vais montrer le second (avec une implémentation mutable):

 def foldOrFail[A,B](it: Iterable[A])(zero: B)(fail: A => Boolean)(f: (B,A) => B): Option[B] = { val ii = it.iterator var b = zero while (ii.hasNext) { val x = ii.next if (fail(x)) return None b = f(b,x) } Some(b) } def sumEvenNumbers(nums: Iterable[Int]) = foldOrFail(nums)(0)(_ % 2 != 0)(_ + _) 

(Si vous implémentez la résiliation par récursivité, retour, paresse, etc., à vous de choisir.)

Je pense que cela couvre les principales variantes raisonnables; Il y a aussi d’autres options, mais je ne sais pas pourquoi on les utiliserait dans ce cas. ( Iterator lui-même fonctionnerait bien s’il avait un findOrPrevious , mais ce n’est pas le cas, et le travail supplémentaire nécessaire pour le faire manuellement en fait une option idiote à utiliser ici.)

Le scénario que vous décrivez (quitter certaines conditions indésirables) semble être un bon exemple d’utilisation de la méthode takeWhile . Il s’agit essentiellement de filter , mais devrait finir par rencontrer un élément qui ne répond pas à la condition.

Par exemple:

 val list = List(2,4,6,8,6,4,2,5,3,2) list.takeWhile(_ % 2 == 0) //result is List(2,4,6,8,6,4,2) 

Cela fonctionnera très bien pour Iterator s / Iterable s aussi. La solution que je propose pour votre “sum des nombres pairs, mais casser sur une paire” est la suivante:

 list.iterator.takeWhile(_ % 2 == 0).foldLeft(...) 

Et juste pour prouver que cela ne perd pas votre temps une fois qu’il atteint un nombre impair …

 scala> val list = List(2,4,5,6,8) list: List[Int] = List(2, 4, 5, 6, 8) scala> def condition(i: Int) = { | println("processing " + i) | i % 2 == 0 | } condition: (i: Int)Boolean scala> list.iterator.takeWhile(condition _).sum processing 2 processing 4 processing 5 res4: Int = 6 

Vous pouvez faire ce que vous voulez dans un style fonctionnel en utilisant la version paresseuse de foldRight dans scalaz. Pour une explication plus détaillée, voir cet article de blog . Bien que cette solution utilise un Stream , vous pouvez convertir une Iterable en un Stream efficacement avec iterable.toStream .

 import scalaz._ import Scalaz._ val str = Stream(2,1,2,2,2,2,2,2,2) var i = 0 //only here for testing val r = str.foldr(Some(0):Option[Int])((n,s) => { println(i) i+=1 if (n % 2 == 0) s.map(n+) else None }) 

Cela imprime seulement

 0 1 

ce qui montre clairement que la fonction anonyme n’est appelée que deux fois (c’est-à-dire jusqu’à ce qu’elle rencontre le nombre impair). Cela est dû à la définition de foldr, dont la signature (dans le cas de Stream ) est def foldr[B](b: B)(f: (Int, => B) => B)(implicit r: scalaz.Foldable[Stream]): B Notez que la fonction anonyme prend un paramètre par nom comme deuxième argument, il ne doit donc pas être évalué.

Btw, vous pouvez toujours écrire ceci avec la solution de correspondance de modèle de l’OP, mais je trouve if / else et map plus élégant.

Eh bien, Scala autorise les retours non locaux. Les avis divergent quant à savoir si c’est un bon style ou non.

 scala> def sumEvenNumbers(nums: Iterable[Int]): Option[Int] = { | nums.foldLeft (Some(0): Option[Int]) { | case (None, _) => return None | case (Some(s), n) if n % 2 == 0 => Some(s + n) | case (Some(_), _) => None | } | } sumEvenNumbers: (nums: Iterable[Int])Option[Int] scala> sumEvenNumbers(2 to 10) res8: Option[Int] = None scala> sumEvenNumbers(2 to 10 by 2) res9: Option[Int] = Some(30) 

MODIFIER:

Dans ce cas particulier, comme @Arjan l’a suggéré, vous pouvez également faire:

 def sumEvenNumbers(nums: Iterable[Int]): Option[Int] = { nums.foldLeft (Some(0): Option[Int]) { case (Some(s), n) if n % 2 == 0 => Some(s + n) case _ => return None } } 

@Rex Kerr votre réponse m’a aidé, mais j’avais besoin de le modifier pour utiliser Soit

  
   def foldOrFail [A, B, C, D] (map: B => Soit [D, C]) (fusion: (A, C) => A) (initiale: A) (it: Iterable [B]): Soit [D, A] = {
     val ii = it.iterator
     var b = initiale
     tandis que (ii.hasnext) {
       val x = ii.suivant
       carte (x) match {
         case à gauche (erreur) => retour à gauche (erreur)
         case droite (d) => b = fusionner (b, d)
       }
     }
     Droit (b)
   }

Vous pouvez essayer d’utiliser une variable temporaire et d’utiliser takeWhile. Voici une version.

  var continue = true // sample stream of 2's and then a stream of 3's. val evenSum = (Stream.fill(10)(2) ++ Stream.fill(10)(3)).takeWhile(_ => continue) .foldLeft(Option[Int](0)){ case (result,i) if i%2 != 0 => continue = false; // return whatever is appropriate either the accumulated sum or None. result case (optionSum,i) => optionSum.map( _ + i) } 

Le evenSum devrait être Some(20) dans ce cas.

Vous pouvez lancer une exception bien choisie en rencontrant votre critère de terminaison, en le traitant dans le code d’appel.

Une solution plus intéressante consisterait à utiliser span:

 val (l, r) = numbers.span(_ % 2 == 0) if(r.isEmpty) Some(l.sum) else None 

… mais il traverse la liste deux fois si tous les nombres sont pairs

Juste pour des raisons “académiques” (:

 var headers = Source.fromFile(file).getLines().next().split(",") var closeHeaderIdx = headers.takeWhile { s => !"Close".equals(s) }.foldLeft(0)((i, S) => i+1) 

Prend deux fois alors il devrait mais c’est une belle doublure. Si “Fermer” n’est pas trouvé, il retournera

 headers.size 

Un autre (meilleur) est celui-ci:

 var headers = Source.fromFile(file).getLines().next().split(",").toList var closeHeaderIdx = headers.indexOf("Close")