Abandonner tôt dans un pli

Question

Quelle est la meilleure façon de mettre fin une fois au début? Comme un exemple simplifié, imaginez que je veux additionner les nombres dans un Iterable, mais si je rencontre quelque chose que je ne suis pas attendre (à dire avec un nombre impair) que je veuille mettre fin. C'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 fait un .foreach et un retour -- ce serait beaucoup plus propre et plus clair) et le pire de tout, elle parcourt l'ensemble de l'itérable, même si elle rencontre un non-nombre pair.

Alors quelle serait la meilleure façon d'écrire un pli de ce genre, qui se termine tôt? Devrais-je aller et écrire de cette manière récursive, ou est-il accepté?

Answer 1

Mon premier choix serait, en général, l'utilisation de la récursivité. Il n'est que modérément moins compacte, est potentiellement plus rapide (certainement pas plus lent), et au début de résiliation peut rendre la logique de plus en plus clair. Dans ce cas, vous devez imbriquée defs qui est un peu maladroit:

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, comme cela tout le reste est intact et vous avez seulement besoin d'envelopper le plier dans un def si vous avez quelque chose à revenir--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
  })
}

qui, dans ce cas particulier, est beaucoup plus compact que la récursivité (bien que nous avons particulièrement malchanceux avec la récursivité, puisque nous avons dû faire un objet iterable/itérateur de transformation). Les problèmes de flux de contrôle est quelque chose à éviter quand tout le reste est égal, mais ici, il ne l'est pas. Pas de mal à l'utiliser dans les cas où il est précieux.

Si je le faisais souvent, et ce au moyen d'une méthode quelque part (donc je ne pouvais pas l'utiliser juste retour), je serais probablement utiliser de gestion des exceptions pour générer de la non-locales de contrôle de flux. C'est, après tout, ce qu'il est bon, et la gestion des erreurs n'est pas la seule fois où c'est utile. Le seul truc, c'est pour éviter de générer une trace de la pile (qui est vraiment très lent), et c'est facile parce que le trait NoStackTrace et de ses traits de caractère des enfants ControlThrowable déjà le faire pour vous. Scala utilise déjà ce à l'interne (en fait, c'est la façon dont il met en œuvre la déclaration de l'intérieur de la fois!). Nous allons faire notre propre (ne peut pas être imbriquées à l', bien qu'on pourrait le corriger):

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'aide de return c'est mieux, mais notez que vous pouvez mettre shortcut n'importe où, non seulement l'enchaînement d'un ensemble de la méthode.

Le prochain dans la ligne pour moi serait de re-mettre en œuvre des fois (moi-même ou de trouver une bibliothèque qui le fait), de sorte que cela pourrait être le signe de résiliation anticipée. Les deux façons de faire cela est de ne pas propager la valeur, mais un Option contenant de la valeur, où l' None signifie la résiliation; ou l'utilisation d'un deuxième indicateur de la fonction de signaux d'achèvement. Le Scalaz paresseux fois illustré par Kim Stebel couvre déjà le premier cas, donc je vais vous montrer le deuxième (avec une mutable mise en œuvre):

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 en œuvre de la résiliation par récurrence, en retour, la paresse, etc. c'est à vous.)

Je pense que le principal raisonnable variantes; il y a quelques autres options aussi, mais je ne sais pas pourquoi on pourrait les utiliser dans ce cas. (Iterator lui-même serait bien travailler, si elle avait un findOrPrevious, mais il ne le fait pas, et le travail supplémentaire qu'il faut pour le faire à la main en fait un bête option pour utiliser ici.)

Answer 2

Le scénario que vous décrivez (sortie de certains indésirables condition) semble être un bon cas d'utilisation de l' takeWhile méthode. Il s'agit essentiellement d' filter, mais devrait mettre fin à la suite de la rencontre avec un élément qui ne satisfait 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 fonctionne très bien pour Iterators/Iterables trop. La solution que je propose pour votre "la somme des nombres pairs, mais pas dans d'impair" est:

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

Et, juste pour prouver qu'il n'est pas de perdre votre temps une fois qu'il frappe 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

Answer 3

Vous pouvez faire ce que vous voulez dans un style fonctionnel en utilisant le paresseux version de foldRight dans scalaz. Pour une explication détaillée, voir ce billet de blog. Bien que cette solution utilise un Stream, vous pouvez convertir un Iterable en 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
})

Ce n'imprime que les

0
1

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

Btw, vous pouvez toujours écrire ce avec l'OP de filtrage de la solution, mais je trouve que si/d'autre et la carte, plus élégant.

Answer 4

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)
 

MODIFIER:

Dans ce cas particulier, comme @Arjan l'a suggéré, vous pouvez également effectuer les tâches suivantes:

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

Answer 5

Vous pouvez lever une exception bien choisie lorsque vous rencontrez votre critère de résiliation, en le gérant dans le code appelant.