Прервать преждевременное сгибание

Как лучше всего прервать фолд раньше срока? В качестве упрощенного примера представьте, что я хочу суммировать числа в Iterable, но если я встречу что-то, чего я не ожидаю (скажем, нечетное число), я, возможно, захочу завершить. Это первое приближение

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

Однако это решение довольно уродливое (например, если бы я сделал .foreach и return - это было бы намного чище и яснее), и, что хуже всего, оно проходит всю итерацию, даже если встречает нечетное число .

Итак, как лучше всего написать такую ​​складку, которая завершается раньше времени? Должен ли я просто пойти и написать это рекурсивно, или есть более приемлемый способ?

Мой первый выбор обычно - использовать рекурсию. Он лишь умеренно менее компактен, потенциально быстрее (конечно, не медленнее) и при раннем завершении может сделать логику более понятной. В этом случае вам нужны вложенные defs, что немного неудобно:

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

Мой второй вариант - использовать return, поскольку он сохраняет все остальное нетронутым, и вам нужно только обернуть складку, defчтобы вам было из чего вернуться - в этом случае у вас уже есть метод, поэтому:

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

который в данном конкретном случае намного компактнее, чем рекурсия (хотя нам особенно не повезло с рекурсией, так как нам пришлось выполнять преобразование итерация / итератор). При прочих равных следует избегать прерывистого потока управления, но здесь это не так. Нет вреда в использовании в тех случаях, когда это ценно.

Если бы я делал это часто и хотел, чтобы это было где-то в середине метода (чтобы я не мог просто использовать return), я бы, вероятно, использовал бы обработку исключений для генерации нелокального потока управления. В конце концов, это то, в чем он хорош, и обработка ошибок - не единственный раз, когда это полезно. Единственная уловка - избежать генерации трассировки стека (что очень медленно), и это легко, потому что трейт NoStackTraceи его дочерний трейт ControlThrowableуже делают это за вас. Scala уже использует это для внутренних целей (фактически, именно так он реализует возврат изнутри свертки!). Создадим свой (не может быть вложенным, хотя это можно исправить):

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

Здесь, конечно, returnлучше использовать, но учтите, что вы можете разместить shortcutгде угодно, а не просто обернуть весь метод.

Следующим в очереди для меня было бы повторно реализовать свертку (либо я, либо найти библиотеку, которая это делает), чтобы это могло сигнализировать о раннем завершении. Два естественных способа сделать это - не распространять значение, а Optionсодержать значение, где Noneозначает завершение; или использовать вторую функцию индикатора, сигнализирующую о завершении. Ленивая свертка Scalaz, показанная Кимом Стебелем, уже охватывает первый случай, поэтому я покажу второй (с изменяемой реализацией):

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

(Реализуете ли вы завершение рекурсией, возвратом, ленью и т. Д. - решать вам.)

Думаю, это охватывает основные разумные варианты; есть и другие варианты, но я не уверен, зачем их использовать в этом случае. ( Iteratorсам по себе работал бы хорошо, если бы у него был findOrPrevious, но его нет, и дополнительная работа, необходимая для выполнения этого вручную, делает его глупым вариантом для использования здесь.)

Сценарий, который вы описываете (выход из какого-то нежелательного состояния), кажется хорошим вариантом использования этого takeWhileметода. По сути, это так filter, но должно закончиться при обнаружении элемента, не соответствующего условию.

Например:

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)

Это будет отлично работать и для Iterators / Iterables. Решение, которое я предлагаю для вашей «суммы четных чисел, но с разбивкой на нечетные»:

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

И просто чтобы доказать, что это не зря тратит ваше время, когда выпадает нечетное число ...

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

Вы можете делать все, что хотите, в функциональном стиле, используя ленивую версию foldRight в scalaz. Для более подробного объяснения см. Это сообщение в блоге . Хотя в этом решении используется объект Stream, вы можете эффективно преобразовать Iterableего Streamс помощью 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
})

Это только печатает

0
1

что ясно показывает, что анонимная функция вызывается только дважды (то есть до тех пор, пока она не встретит нечетное число). Это связано с определением foldr, подпись которого (в случае Stream) есть def foldr[B](b: B)(f: (Int, => B) => B)(implicit r: scalaz.Foldable[Stream]): B. Обратите внимание, что анонимная функция принимает параметр по имени в качестве второго аргумента, поэтому его не нужно оценивать.

Кстати, вы все еще можете написать это с помощью решения сопоставления шаблонов OP, но я считаю, что if / else и map более элегантны.

Что ж, Scala допускает нелокальный возврат. Есть разные мнения о том, хороший это стиль или нет.

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)

РЕДАКТИРОВАТЬ:

В этом конкретном случае, как предложил @Arjan, вы также можете:

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

Кошки имеют метод , называемый foldM , который делает короткое замыкание (для Vector, List, Stream, ...).

Это работает следующим образом:

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

Как только один из элементов коллекции не четный, он возвращается.

Вы можете использовать foldMfrom cats lib (как было предложено @Didac), но я предлагаю использовать Eitherвместо этого, Optionесли вы хотите получить реальную сумму.

bifoldMapиспользуется для извлечения результата из 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)
      }
    }
  }

Примеры:

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, ваш ответ мне помог, но мне нужно было настроить его, чтобы использовать Either

  
  def foldOrFail [A, B, C, D] (map: B => Either [D, C]) (merge: (A, C) => A) (начальное: A) (it: Iterable [B]): Либо [D, A] = {
    val ii = it.iterator
    var b = начальный
    while (ii.hasNext) {
      val x = ii.next
      map (x) match {
        case Left (ошибка) => return Left (ошибка)
        case Right (d) => b = merge (b, d)
      }
    }
    Право (б)
  }

Вы можете попробовать использовать временную переменную и takeWhile. Вот такая версия.

  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)

  }

В этом случае evenSumдолжно быть Some(20).

Вы можете выбросить хорошо подобранное исключение при обнаружении вашего критерия завершения, обработав его в вызывающем коде.

Более красивым решением будет использование диапазона:

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

... но он проходит список два раза, если все числа четные

Просто по "академическим" причинам (:

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

Требуется дважды, но это хороший лайнер. Если "Закрыть" не найдено, он вернется

headers.size

Другой (лучше) вот такой:

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