Abortar logo no início

Qual é a melhor maneira de encerrar um fold mais cedo? Como um exemplo simplificado, imagine que eu queira somar os números em um Iterable, mas se encontrar algo que não estou esperando (digamos um número ímpar), posso encerrar. Esta é uma primeira aproximação

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

No entanto, esta solução é muito feia (como em, se eu fizesse um .foreach e um retorno - seria muito mais limpo e claro) e o pior de tudo, ela percorre todo o iterável, mesmo se encontrar um número não par .

Então, qual seria a melhor maneira de escrever uma dobra como essa, que termina mais cedo? Devo escrever recursivamente ou há uma maneira mais aceita?

Minha primeira escolha normalmente seria usar recursão. É apenas moderadamente menos compacto, é potencialmente mais rápido (certamente não é mais lento) e, no encerramento antecipado, pode tornar a lógica mais clara. Neste caso, você precisa de defs aninhados, o que é um pouco estranho:

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

Minha segunda opção seria usar return, pois mantém todo o resto intacto e você só precisa embrulhar a dobra defpara ter algo de onde retornar - neste caso, você já tem um método, então:

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

que, neste caso específico, é muito mais compacto do que a recursão (embora tenhamos tido azar especial com a recursão, uma vez que tivemos que fazer uma transformação iterável / iterador). O fluxo de controle instável é algo a evitar quando tudo o mais é igual, mas aqui não é. Não há mal nenhum em usá-lo nos casos em que é valioso.

Se eu estivesse fazendo isso com frequência e quisesse no meio de um método em algum lugar (portanto, não poderia apenas usar return), provavelmente usaria o tratamento de exceções para gerar um fluxo de controle não local. Afinal, é nisso que ele é bom, e o tratamento de erros não é o único momento em que é útil. O único truque é evitar a geração de um rastreamento de pilha (que é muito lento), e isso é fácil porque o traço NoStackTracee o traço filho ControlThrowablejá fazem isso por você. O Scala já usa isso internamente (na verdade, é assim que ele implementa o retorno de dentro do fold!). Vamos fazer o nosso (não pode ser aninhado, embora isso possa ser corrigido):

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

Aqui, returné claro, usar é melhor, mas observe que você pode colocar em shortcutqualquer lugar, não apenas envolver um método inteiro.

O próximo passo para mim seria reimplementar o fold (eu mesmo ou para encontrar uma biblioteca que o faça) para que possa sinalizar o encerramento antecipado. As duas maneiras naturais de fazer isso são não propagar o valor, mas Optionconter o valor, onde Nonesignifica o encerramento; ou para usar uma segunda função de indicador que sinaliza a conclusão. A dobra preguiçosa do Scalaz mostrada por Kim Stebel já cobre o primeiro caso, então mostrarei o segundo (com uma implementação mutável):

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)(_ + _)

(Se você implementa a rescisão por recursão, retorno, preguiça, etc., depende de você.)

Acho que isso cobre as principais variantes razoáveis; há algumas outras opções também, mas não sei por que alguém as usaria neste caso. ( Iteratorfuncionaria bem se tivesse um findOrPrevious, mas não tem, e o trabalho extra necessário para fazer isso manualmente torna-o uma opção boba de usar aqui).

O cenário que você descreve (sair após alguma condição indesejada) parece um bom caso de uso para o takeWhilemétodo. É essencialmente filter, mas deve terminar ao encontrar um elemento que não atende à condição.

Por exemplo:

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)

Isso funcionará bem para Iterators / Iterables também. A solução que sugiro para a sua "soma dos números pares, mas quebra nos ímpares" é:

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

E só para provar que não está perdendo seu tempo quando atinge um número ímpar ...

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

Você pode fazer o que quiser em um estilo funcional usando a versão preguiçosa de foldRight em scalaz. Para obter uma explicação mais detalhada, consulte esta postagem do blog . Embora esta solução use um Stream, você pode converter um Iterableem um de forma Streameficiente com 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
})

Isso só imprime

0
1

o que mostra claramente que a função anônima é chamada apenas duas vezes (ou seja, até encontrar o número ímpar). Isso se deve à definição de foldr, cuja assinatura (no caso de Stream) é def foldr[B](b: B)(f: (Int, => B) => B)(implicit r: scalaz.Foldable[Stream]): B. Observe que a função anônima recebe um parâmetro por nome como seu segundo argumento, portanto, não precisa ser avaliada.

Btw, você ainda pode escrever isso com a solução de correspondência de padrões do OP, mas acho if / else e map mais elegante.

Bem, Scala permite devoluções não locais. Existem opiniões divergentes sobre se este é um bom estilo ou não.

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:

Neste caso específico, como @Arjan sugeriu, você também pode fazer:

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

Cats tem um método chamado foldM que não curto-circuito (para Vector, List,Stream , ...).

Funciona da seguinte maneira:

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

Se encontrar um elemento não par, ele retorna None sem calcular o resto, caso contrário, ele retorna a soma das entradas pares.

Se você quiser manter a contagem até que uma entrada par seja encontrada, você deve usar um Either[Long, Long]

Você pode usar foldMfrom cats lib (como sugerido por @Didac), mas sugiro usar em Eithervez deOption se você quiser obter uma soma real.

bifoldMapé usado para extrair o resultado 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)
      }
    }
  }

exemplos:

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 sua resposta me ajudou, mas eu precisava ajustá-la para usar qualquer um

  
  def foldOrFail [A, B, C, D] (mapa: B => Qualquer [D, C]) (mesclar: (A, C) => A) (inicial: A) (it: Iterable [B]): Qualquer um [D, A] = {
    val ii = it.iterator
    var b = inicial
    enquanto (ii.hasNext) {
      val x = ii.next
      map (x) match {
        case Left (erro) => return Left (error)
        case Right (d) => b = unir (b, d)
      }
    }
    Certo (b)
  }

Você pode tentar usar uma var temporária e usar takeWhile. Aqui está uma versão.

  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)

  }

O evenSumdeveria ser Some(20)neste caso.

Você pode lançar uma exceção bem escolhida ao encontrar seu critério de encerramento, tratando-o no código de chamada.

Uma solução mais bonita seria usar span:

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

... mas percorre a lista duas vezes se todos os números forem pares

Apenas por razões "acadêmicas" (:

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

Leva duas vezes, então deveria, mas é um bom forro. Se "Fechar" não for encontrado, ele retornará

headers.size

Outro (melhor) é este:

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