Przerwij wcześnie

Jaki jest najlepszy sposób na wcześniejsze zakończenie spasowania? Jako uproszczony przykład wyobraź sobie, że chcę zsumować liczby w an Iterable, ale jeśli napotkam coś, czego się nie spodziewam (powiedzmy nieparzystą liczbę), mogę chcieć zakończyć. To jest pierwsze przybliżenie

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

Jednak to rozwiązanie jest dość brzydkie (jak w przypadku, gdybym zrobił .foreach i return - byłoby znacznie czystsze i wyraźniejsze), a co najgorsze, przechodzi przez całą iterowalną liczbę, nawet jeśli napotka nieparzystą liczbę .

Jaki byłby więc najlepszy sposób na napisanie takiego fałdu, które kończy się wcześniej? Powinienem po prostu iść i pisać to rekurencyjnie, czy jest bardziej akceptowany sposób?

Moim pierwszym wyborem byłoby zwykle użycie rekurencji. Jest tylko umiarkowanie mniej zwarty, jest potencjalnie szybszy (z pewnością nie wolniejszy), a we wczesnym zakończeniu może uczynić logikę bardziej przejrzystą. W tym przypadku potrzebujesz zagnieżdżonych definicji, co jest trochę niezręczne:

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

Moim drugim wyborem byłoby użycie return, ponieważ zachowuje wszystko inne nienaruszone i wystarczy zawinąć fałdę, defaby mieć z czego wrócić - w tym przypadku masz już metodę, więc:

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

który w tym konkretnym przypadku jest dużo bardziej zwarty niż rekurencja (chociaż mieliśmy szczególnego pecha z rekurencją, ponieważ musieliśmy wykonać iterowalną transformację iteracyjną). Skokowy przepływ sterowania jest czymś, czego należy unikać, gdy wszystko inne jest równe, ale tutaj tak nie jest. Nie szkodzi używaniu go w przypadkach, gdy jest cenny.

Gdybym robił to często i chciałbym, żeby było to gdzieś w środku metody (więc nie mogłem po prostu użyć powrotu), prawdopodobnie użyłbym obsługi wyjątków do wygenerowania nielokalnego przepływu sterowania. To w końcu jest dobry, a obsługa błędów nie jest jedynym, kiedy jest przydatna. Jedyną sztuczką jest unikanie generowania śladu stosu (który jest naprawdę powolny), a jest to łatwe, ponieważ cecha NoStackTracei jej cecha potomna ControlThrowablejuż to robią. Scala już używa tego wewnętrznie (w rzeczywistości tak implementuje powrót z wnętrza zagięcia!). Zróbmy własne (nie można zagnieżdżać, chociaż można to naprawić):

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

Tutaj oczywiście użycie returnjest lepsze, ale pamiętaj, że możesz umieścić w shortcutdowolnym miejscu, a nie tylko opakować całą metodę.

Następnym krokiem byłoby ponowne zaimplementowanie spasowania (samodzielnie lub znalezienie biblioteki, która to robi), aby mogło sygnalizować wczesne zakończenie. Dwa naturalne sposoby na zrobienie tego to nie propagowanie wartości, ale Optionzawarcie wartości, gdzie Noneoznacza zakończenie; lub użyć drugiej funkcji wskaźnika, która sygnalizuje zakończenie. Leniwe zwinięcie Scalaz pokazane przez Kim Stebel obejmuje już pierwszy przypadek, więc pokażę drugi (ze zmienną implementacją):

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

(To, czy zaimplementujesz zakończenie przez rekursję, powrót, lenistwo itp., Zależy od Ciebie).

Myślę, że obejmuje to główne rozsądne warianty; jest też kilka innych opcji, ale nie jestem pewien, po co ich używać w tym przypadku. ( IteratorSamo działałoby dobrze, gdyby miało findOrPrevious, ale tak nie jest, a dodatkowa praca, jaką trzeba wykonać ręcznie, sprawia, że ​​jest to głupia opcja w tym miejscu).

Scenariusz, który opisujesz (wyjście po jakimś niepożądanym stanie) wydaje się być dobrym przykładem użycia tej takeWhilemetody. Zasadniczo jest filter, ale powinno zakończyć się napotkaniem elementu, który nie spełnia warunku.

Na przykład:

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)

To zadziała również dobrze dla Iterators / Iterables. Rozwiązanie, które proponuję dla twojej „sumy liczb parzystych, ale przerwa na nieparzyste” to:

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

I tylko po to, aby udowodnić, że nie marnujesz czasu, gdy trafi na nieparzystą liczbę ...

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

Możesz robić co chcesz w funkcjonalnym stylu używając leniwej wersji foldRight w scalaz. Aby uzyskać bardziej szczegółowe wyjaśnienia, zobacz ten wpis na blogu . Chociaż to rozwiązanie wykorzystuje Streamrozszerzenie, możesz skutecznie przekształcić go Iterablew plik .Streamiterable.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
})

To tylko drukuje

0
1

co wyraźnie pokazuje, że funkcja anonimowa jest wywoływana tylko dwukrotnie (tj. do momentu, gdy napotka liczbę nieparzystą). Wynika to z definicji foldr, którego podpis (w przypadku Stream) to def foldr[B](b: B)(f: (Int, => B) => B)(implicit r: scalaz.Foldable[Stream]): B. Zwróć uwagę, że funkcja anonimowa przyjmuje parametr by name jako drugi argument, więc nie trzeba go oceniać.

Przy okazji, nadal możesz to napisać za pomocą rozwiązania do dopasowywania wzorców OP, ale uważam, że jeśli / else i mapa jest bardziej elegancka.

Cóż, Scala zezwala na nielokalne zwroty. Istnieją różne opinie na temat tego, czy jest to dobry styl.

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)

EDYTOWAĆ:

W tym konkretnym przypadku, jak zasugerował @Arjan, możesz również:

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

Koty mają metodę zwaną foldM który ma zwarcie (na Vector, List, Stream, ...).

Działa w następujący sposób:

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

Gdy jeden z elementów kolekcji nie jest parzysty, zwraca.

Możesz użyć foldMz cats lib (zgodnie z sugestią @Didac), ale sugeruję użycie EitherzamiastOption jeśli chcesz uzyskać rzeczywistą sumę.

bifoldMapsłuży do wyodrębnienia wyniku z 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)
      }
    }
  }

przykłady:

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 Twoja odpowiedź pomogła mi, ale musiałem ją dostosować, aby używać jednego z nich

  
  def foldOrFail [A, B, C, D] (map: B => Either [D, C]) (merge: (A, C) => A) (początkowe: A) (it: Iterable [B]): Albo [D, A] = {
    val ii = it.iterator
    var b = początkowy
    while (ii.hasNext) {
      val x = ii.next
      map (x) match {
        case Left (błąd) => return Left (błąd)
        case Right (d) => b = merge (b, d)
      }
    }
    Prawo (b)
  }

Możesz spróbować użyć tymczasowej zmiennej i takeWhile. Oto wersja.

  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)

  }

W tym przypadku evenSumpowinno być Some(20).

Możesz zgłosić dobrze wybrany wyjątek po napotkaniu kryterium zakończenia, obsługując go w kodzie wywołującym.

Piękniejszym rozwiązaniem byłoby użycie span:

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

... ale przechodzi przez listę dwa razy, jeśli wszystkie liczby są parzyste

Tylko z powodów „akademickich” (:

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

Zajmuje dwa razy tyle, ile powinno, ale jest to ładna jedna wkładka. Jeśli „Zamknij” nie zostanie znalezione, nastąpi powrót

headers.size

Innym (lepszym) jest ten:

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