Abortar temprano en un pliegue

¿Cuál es la mejor manera de terminar un pliegue antes de tiempo? Como ejemplo simplificado, imagine que quiero resumir los números en un Iterable, pero si encuentro algo que no estoy esperando (digamos un número impar), es posible que desee terminar. Esta es una primera aproximación

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

Sin embargo, esta solución es bastante fea (como en, si hiciera un .foreach y un retorno, sería mucho más limpio y claro) y lo peor de todo es que atraviesa todo el iterable incluso si encuentra un número no par .

Entonces, ¿cuál sería la mejor manera de escribir un pliegue como este, que termina antes? ¿Debería escribir esto de forma recursiva o hay una forma más aceptada?

Mi primera opción suele ser utilizar la recursividad. Es solo moderadamente menos compacto, es potencialmente más rápido (ciertamente no más lento) y en una terminación anticipada puede hacer que la lógica sea más clara. En este caso, necesita defs anidadas, lo cual es un poco incómodo:

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

Mi segunda opción sería usar return, ya que mantiene todo lo demás intacto y solo necesita envolver el pliegue en un defpara tener algo de lo que regresar; en este caso, ya tiene un método, así que:

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

que en este caso particular es mucho más compacto que la recursividad (aunque tuvimos especialmente mala suerte con la recursividad ya que tuvimos que hacer una transformación iterable / iterador). El flujo de control saltado es algo que se debe evitar cuando todo lo demás es igual, pero aquí no lo es. No está de más usarlo en los casos en que sea valioso.

Si estuviera haciendo esto a menudo y lo quisiera en medio de un método en algún lugar (por lo que no podría simplemente usar return), probablemente usaría el manejo de excepciones para generar un flujo de control no local. Después de todo, eso es en lo que es bueno, y el manejo de errores no es el único momento en que es útil. El único truco es evitar generar un seguimiento de pila (que es realmente lento), y eso es fácil porque el rasgo NoStackTracey su rasgo secundario ControlThrowableya lo hacen por usted. Scala ya usa esto internamente (de hecho, ¡así es como implementa el retorno desde dentro del pliegue!). Hagamos el nuestro (no se puede anidar, aunque se podría arreglar eso):

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

Aquí, por supuesto, usar returnes mejor, pero tenga en cuenta que puede poner en shortcutcualquier lugar, no solo envolver un método completo.

El siguiente en la fila para mí sería volver a implementar el pliegue (ya sea yo mismo o encontrar una biblioteca que lo haga) para que pueda indicar la terminación anticipada. Las dos formas naturales de hacer esto son no propagar el valor sino Optioncontener el valor, donde Nonesignifica terminación; o para utilizar una función de segundo indicador que señala la finalización. El pliegue perezoso de Scalaz mostrado por Kim Stebel ya cubre el primer caso, así que mostraré el segundo (con una implementación 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 implementa la terminación por recursividad, retorno, pereza, etc., depende de usted).

Creo que cubre las principales variantes razonables; También hay algunas otras opciones, pero no estoy seguro de por qué se usarían en este caso. (en Iteratorsí mismo funcionaría bien si tuviera un findOrPrevious, pero no lo tiene, y el trabajo adicional que se necesita para hacerlo a mano lo convierte en una opción tonta para usar aquí).

El escenario que describe (salir por alguna condición no deseada) parece un buen caso de uso para el takeWhilemétodo. Esencialmente filter, pero debería terminar al encontrar un elemento que no cumple con la condición.

Por ejemplo:

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)

Esto también funcionará bien para Iterators / Iterables. La solución que sugiero para su "suma de números pares, pero romper en impares" es:

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

Y solo para demostrar que no está perdiendo el tiempo una vez que llega a un número impar ...

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

Puede hacer lo que quiera con un estilo funcional utilizando la versión perezosa de foldRight en scalaz. Para obtener una explicación más detallada, consulte esta publicación de blog . Si bien esta solución usa un Stream, puede convertir un Iterableen un de manera Streameficiente con 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
})

Esto solo imprime

0
1

lo que muestra claramente que la función anónima solo se llama dos veces (es decir, hasta que encuentra el número impar). Eso se debe a la definición de foldr, cuya firma (en el caso de Stream) es def foldr[B](b: B)(f: (Int, => B) => B)(implicit r: scalaz.Foldable[Stream]): B. Tenga en cuenta que la función anónima toma un parámetro por nombre como segundo argumento, por lo que no es necesario evaluarlo.

Por cierto, todavía puede escribir esto con la solución de coincidencia de patrones del OP, pero encuentro que if / else y el mapa son más elegantes.

Bueno, Scala permite devoluciones no locales. Hay diferentes opiniones sobre si este es un buen estilo o no.

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)

EDITAR:

En este caso particular, como sugirió @Arjan, también puede hacer:

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

Los gatos tienen un método llamado foldM que no cortocircuito (para Vector, List, Stream, ...).

Funciona de la siguiente manera:

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

Tan pronto como uno de los elementos de la colección no esté parejo, regresa.

Puede usar foldMdesde cats lib (como lo sugiere @Didac) pero sugiero usar en Eitherlugar de Optionsi desea obtener la suma real.

bifoldMapse utiliza para extraer el resultado 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)
      }
    }
  }

ejemplos:

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, tu respuesta me ayudó, pero necesitaba modificarla para usar Either

  
  def foldOrFail [A, B, C, D] (map: B => O [D, C]) (fusionar: (A, C) => A) (inicial: A) (it: Iterable [B]): O [D, A] = {
    val ii = it.iterator
    var b = inicial
    while (ii.hasNext) {
      val x = ii. siguiente
      mapa (x) coincide {
        case Left (error) => return Left (error)
        caso Derecha (d) => b = fusionar (b, d)
      }
    }
    Derecha (b)
  }

Podría intentar usar una var temporal y usar takeWhile. Aquí hay una versión.

  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)

  }

El evenSumdebe ser Some(20)en este caso.

Puede lanzar una excepción bien elegida al encontrar su criterio de terminación, manejándolo en el código de llamada.

Una solución más hermosa sería usar span:

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

... pero atraviesa la lista dos veces si todos los números son pares

Solo por razones "académicas" (:

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

Toma dos veces, entonces debería, pero es una buena línea. Si no se encuentra "Cerrar", volverá

headers.size

Otro (mejor) es este:

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