Abandonner tôt dans un pli

Quelle est la meilleure façon de terminer un pli tôt? À titre d'exemple simplifié, imaginez que je veuille résumer les nombres dans un Iterable, mais si je rencontre quelque chose que je ne m'attends pas (disons un nombre impair), je pourrais vouloir 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 dans, si je faisais un .foreach et un retour - ce serait beaucoup plus propre et plus clair) et le pire de tout, elle traverse tout l'itérable même s'il rencontre un nombre non pair .

Alors, quelle serait la meilleure façon d'écrire un pli comme celui-ci, qui se termine tôt? Dois-je simplement aller écrire ceci récursivement, ou y a-t-il une manière plus acceptée?

Mon premier choix serait généralement d'utiliser la récursivité. Il n'est que modérément moins compact, est potentiellement plus rapide (certainement pas plus lent) et, en cas de résiliation anticipée, peut rendre la logique plus claire. Dans ce cas, vous avez besoin de defs imbriquées, 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 deuxième choix serait d'utiliser return, car cela garde tout le reste intact et vous n'avez qu'à envelopper le pli dans un defpour avoir quelque chose à retourner - dans ce cas, vous avez déjà une méthode, donc:

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écursion car nous devions faire une transformation itérable / itérateur). Le flux de contrôle instable est quelque chose à éviter quand tout le reste est égal, mais ici ce n'est pas le cas. Aucun mal à l'utiliser dans les cas où il est précieux.

Si je faisais cela 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 flux de contrôle non local. C'est, après tout, ce pour quoi il est bon, et la gestion des erreurs n'est pas la seule fois où c'est utile. La seule astuce est d'éviter de générer une trace de pile (qui est vraiment lente), et c'est facile car le trait NoStackTraceet son trait enfant le ControlThrowablefont déjà pour vous. Scala l'utilise déjà en interne (en fait, c'est ainsi qu'il implémente le retour depuis l'intérieur du pli!). Faisons le nôtre (ne peut pas être imbriqué, bien que l'on puisse résoudre 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, l'utilisation returnest meilleure, mais notez que vous pouvez mettre shortcutn'importe où, pas seulement envelopper une méthode entière.

La prochaine étape pour moi serait de réimplémenter le repli (soit moi-même, soit de trouver une bibliothèque qui le fasse) afin qu'il puisse signaler une résiliation anticipée. Les deux manières naturelles de le faire sont de ne pas propager la valeur mais de Optioncontenir la valeur, où Nonesignifie la terminaison; ou pour utiliser une deuxième fonction d'indicateur qui signale la fin. Le pli paresseux Scalaz montré par Kim Stebel couvre déjà le premier cas, je vais donc 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)(_ + _)

(Que vous implémentiez la résiliation par récursivité, retour, paresse, etc. dépend de vous.)

Je pense que cela couvre les principales variantes raisonnables; il existe également d'autres options, mais je ne sais pas pourquoi on les utiliserait dans ce cas. ( Iteratorlui-même fonctionnerait bien s'il avait un findOrPrevious, mais ce n'est pas le cas, et le travail supplémentaire qu'il faut pour le faire à la main en fait une option ridicule à utiliser ici.)

Le scénario que vous décrivez (quitter en cas de condition indésirable) semble être un bon cas d'utilisation de la takeWhileméthode. C'est essentiellement filter, mais devrait se terminer lors de la rencontre d'un élément qui ne remplit 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 Iterators / Iterables aussi. La solution que je suggère pour votre "somme de nombres pairs, mais coupure sur impaire" est:

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

Et juste pour prouver que cela ne vous fait pas perdre 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, consultez cet article de blog . Bien que cette solution utilise a Stream, vous pouvez convertir un Iterableen un Streamefficacement 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 (en 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 n'est donc pas nécessaire de l'évaluer.

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 opinions 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)

ÉDITER:

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
  }
}

Les chats a une méthode appelée foldM qui ne court-circuit (pour Vector, List,Stream , ...).

Cela fonctionne comme suit:

def sumEvenNumbers(nums: Stream[Int]): Option[Long] = {
  import cats.implicits._
  nums.foldM(0L) {
    case (acc, c) if c % 2 == 0 => Some(acc + c)
    case _ => None
  }
}

Dès que l'un des éléments de la collection n'est pas pair, il revient.

Vous pouvez utiliser foldMfrom cats lib (comme suggéré par @Didac) mais je suggère d'utiliser à la Eitherplace de Optionsi vous voulez obtenir la somme réelle.

bifoldMapest utilisé pour extraire le résultat de Either.

import cats.implicits._

def sumEven(nums: Stream[Int]): Either[Int, Int] = {
    nums.foldM(0) {
      case (acc, n) if n % 2 == 0 => Either.right(acc + n)
      case (acc, n) => {
        println(s"Stopping on number: $n")
        Either.left(acc)
      }
    }
  }

exemples:

println("Result: " + sumEven(Stream(2, 2, 3, 11)).bifoldMap(identity, identity))
> Stopping on number: 3
> Result: 4

println("Result: " + sumEven(Stream(2, 7, 2, 3)).bifoldMap(identity, identity))
> Stopping on number: 7
> Result: 2

@Rex Kerr votre réponse m'a aidé, mais j'avais besoin de la peaufiner pour utiliser l'un ou l'autre

  
  def foldOrFail [A, B, C, D] (map: B => Soit [D, C]) (merge: (A, C) => A) (initial: A) (it: Iterable [B]): Soit [D, A] = {
    val ii = it.iterator
    var b = initiale
    while (ii.hasNext) {
      val x = ii.next
      map (x) match {
        case Left (erreur) => retour Left (erreur)
        case Right (d) => b = merge (b, d)
      }
    }
    Droite (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 evenSumdevrait être Some(20)dans ce cas.

Vous pouvez lever une exception bien choisie lorsque vous rencontrez votre critère de terminaison, en le traitant dans le code d'appel.

Une solution plus belle consisterait à utiliser span:

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

... mais il parcourt 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 reviendra

headers.size

Un autre (meilleur) est celui-ci:

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