Früh abbrechen

88

Was ist der beste Weg, um eine Falte vorzeitig zu beenden? Stellen Sie sich als vereinfachtes Beispiel vor, ich möchte die Zahlen in einem zusammenfassen Iterable, aber wenn ich auf etwas stoße, das ich nicht erwarte (z. B. eine ungerade Zahl), möchte ich möglicherweise beenden. Dies ist eine erste Annäherung

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

Diese Lösung ist jedoch ziemlich hässlich (wie in, wenn ich eine .foreach und eine Rückkehr gemacht hätte - es wäre viel sauberer und klarer) und am schlimmsten ist, dass sie die gesamte Iterierbarkeit durchläuft, selbst wenn sie auf eine ungerade Zahl stößt .

Was wäre also der beste Weg, um eine solche Falte zu schreiben, die früh endet? Soll ich das einfach rekursiv schreiben oder gibt es einen akzeptierteren Weg?

Heptisch
quelle
Möchten Sie die Zwischenantwort beenden und aufzeichnen?
Brian Agnew
In diesem Fall nein. Aber in einem etwas allgemeineren Fall möchte ich vielleicht ein Entweder zurückgeben, das einen Fehler hat oder so
Heptic
Es gibt diese Frage: stackoverflow.com/questions/1595427/…
ziggystar
Diese Antwort über das Ausbrechen von Schleifen könnte auch nützlich sein: stackoverflow.com/a/2742941/1307721
ejoubaud

Antworten:

64

Meine erste Wahl wäre normalerweise die Rekursion. Es ist nur mäßig weniger kompakt, möglicherweise schneller (sicherlich nicht langsamer) und kann bei vorzeitiger Beendigung die Logik klarer machen. In diesem Fall benötigen Sie verschachtelte Defs, was etwas umständlich ist:

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

Meine zweite Wahl wäre zu verwenden return, da es alles andere intakt hält und Sie nur die Falte in eine einwickeln müssen, defdamit Sie etwas zurückgeben können - in diesem Fall haben Sie bereits eine Methode, also:

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

Dies ist in diesem speziellen Fall viel kompakter als die Rekursion (obwohl wir mit der Rekursion besonders unglücklich waren, da wir eine iterable / iterator-Transformation durchführen mussten). Der nervöse Kontrollfluss ist etwas zu vermeiden, wenn alles andere gleich ist, aber hier ist es nicht. Kein Schaden bei der Verwendung in Fällen, in denen es wertvoll ist.

Wenn ich dies oft tun würde und es irgendwo in der Mitte einer Methode haben wollte (also konnte ich nicht einfach return verwenden), würde ich wahrscheinlich die Ausnahmebehandlung verwenden, um einen nicht lokalen Kontrollfluss zu generieren. Das ist schließlich das, was es kann, und die Fehlerbehandlung ist nicht das einzige Mal, dass es nützlich ist. Der einzige Trick besteht darin, zu vermeiden, dass eine Stapelverfolgung generiert wird (was sehr langsam ist), und das ist einfach, da die Eigenschaft NoStackTraceund ihre untergeordnete Eigenschaft dies ControlThrowablebereits für Sie tun. Scala verwendet dies bereits intern (tatsächlich implementiert es so die Rückgabe aus dem Inneren der Falte!). Lassen Sie uns unsere eigenen machen (kann nicht verschachtelt werden, obwohl man das beheben könnte):

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

Hier ist natürlich die Verwendung returnbesser, aber beachten Sie, dass Sie shortcutüberall platzieren können, nicht nur eine ganze Methode einwickeln.

Als nächstes müsste ich fold erneut implementieren (entweder ich selbst oder eine Bibliothek finden, die dies tut), damit dies eine vorzeitige Beendigung signalisieren kann. Die zwei natürlichen Wege, dies zu tun, bestehen darin, den Wert nicht zu verbreiten, sondern Optionden Wert zu enthalten, wobei Nonedie Beendigung bedeutet; oder um eine zweite Anzeigefunktion zu verwenden, die den Abschluss signalisiert. Die von Kim Stebel gezeigte faule Falte von Scalaz deckt bereits den ersten Fall ab, daher zeige ich den zweiten (mit einer veränderlichen Implementierung):

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

(Ob Sie die Kündigung durch Rekursion, Rückkehr, Faulheit usw. implementieren, liegt bei Ihnen.)

Ich denke, das deckt die wichtigsten vernünftigen Varianten ab; Es gibt auch einige andere Optionen, aber ich bin mir nicht sicher, warum man sie in diesem Fall verwenden würde. ( Iteratorselbst würde gut funktionieren, wenn es eine hätte findOrPrevious, aber es funktioniert nicht, und die zusätzliche Arbeit, die erforderlich ist, um dies von Hand zu tun, macht es zu einer dummen Option, hier zu verwenden.)

Rex Kerr
quelle
Das foldOrFailist genau das, was ich hatte , kam mit , wenn es um die Frage nachzudenken. Kein Grund, in der IMO-Implementierung keinen veränderlichen Iterator und keine while-Schleife zu verwenden, wenn alles gut gekapselt ist. Die Verwendung iteratorzusammen mit der Rekursion macht keinen Sinn.
0__
@ Rex Kerr, danke für Ihre Antwort. Ich habe eine Version für meinen eigenen Gebrauch optimiert, die entweder ... verwendet (ich werde sie als Antwort veröffentlichen)
Core
Wahrscheinlich einer der Nachteile der Rückkehr -basierte Lösung, ist , dass es eine Weile zu erkennen , nimmt die es funktioniert gilt: sumEvenNumbersoder Fold istop
Ivan Balashov
1
@IvanBalashov - Nun, dauert es eine Weile , einmal zu erfahren , was Scala Regeln sind für return(dh es kehrt aus innerste expliziter Methode Sie es in finden), aber nach , dass es sollte nicht sehr lange dauern. Die Regel ist ziemlich klar und defverrät, wo sich die Einschlussmethode befindet.
Rex Kerr
Ich mag dein foldOrFail, aber persönlich hätte ich den Rückgabetyp Bnicht gemacht, Option[B]weil es sich dann wie ein Fold verhält, bei dem der Rückgabetyp dem Typ des Nullakkumulators entspricht . Ersetzen Sie einfach alle Optionsrückgaben durch b. und pas in None als Null. Immerhin wollte die Frage eine Falte, die vorzeitig enden kann, anstatt zu scheitern.
Karl
25

Das von Ihnen beschriebene Szenario (Beenden eines unerwünschten Zustands) scheint ein guter Anwendungsfall für die takeWhileMethode zu sein. Es ist im Wesentlichen filter, sollte aber mit der Begegnung mit einem Element enden, das die Bedingung nicht erfüllt.

Beispielsweise:

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)

Dies funktioniert auch für Iterators / Iterables einwandfrei. Die Lösung, die ich für Ihre "Summe aus geraden Zahlen, aber ungeraden Zahlen" vorschlage, lautet:

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

Und nur um zu beweisen, dass es nicht Ihre Zeit verschwendet, wenn es eine ungerade Zahl erreicht ...

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
Dylan
quelle
14

Mit der faulen Version von foldRight in Scalaz können Sie in einem funktionalen Stil tun, was Sie wollen. Eine ausführlichere Erklärung finden Sie in diesem Blogbeitrag . Während diese Lösung a verwendet Stream, können Sie Iterableein Streameffizient in ein mit umwandeln 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
})

Dies wird nur gedruckt

0
1

Dies zeigt deutlich, dass die anonyme Funktion nur zweimal aufgerufen wird (dh bis sie auf die ungerade Zahl trifft). Das liegt an der Definition von foldr, dessen Unterschrift (im Fall von Stream) ist def foldr[B](b: B)(f: (Int, => B) => B)(implicit r: scalaz.Foldable[Stream]): B. Beachten Sie, dass die anonyme Funktion einen by name-Parameter als zweites Argument verwendet und daher nicht ausgewertet werden muss.

Übrigens können Sie dies immer noch mit der Pattern Matching-Lösung des OP schreiben, aber ich finde if / else und map eleganter.

Kim Stebel
quelle
Was passiert, wenn Sie printlnvor if- elseAusdruck setzen?
fehlender Faktor
@missingfaktor: dann druckt es 0 und 1, aber nicht mehr
Kim Stebel
@missingfaktor: Da mein Punkt auf diese Weise einfacher zu formulieren ist, habe ich ihn in der Antwort geändert
Kim Stebel
1
Beachten Sie, dass Sie jedes Iterable mit in einen Stream verwandeln können toStream, sodass diese Antwort allgemeiner ist, als es zunächst erscheint.
Rex Kerr
2
Da Sie Scalaz verwenden, warum nicht ‛0.some‛ verwenden?
Pedrofurla
7

Nun, Scala erlaubt nicht lokale Rückgaben. Es gibt unterschiedliche Meinungen darüber, ob dies ein guter Stil ist oder nicht.

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)

BEARBEITEN:

In diesem speziellen Fall können Sie, wie von @Arjan vorgeschlagen, auch Folgendes tun:

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
  }
}
fehlender Faktor
quelle
2
stattdessen Some(0): Option[Int]kannst du einfach schreiben Option(0).
Luigi Plinge
1
@LuigiPlinge, ja. Ich habe gerade den OP-Code kopiert und nur genug Änderungen vorgenommen, um einen Punkt zu verdeutlichen.
fehlender Faktor
5

Katzen haben eine Methode namens foldM , die nicht kurzgeschlossen (für Vector, List,Stream , ...).

Es funktioniert wie folgt:

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

Sobald eines der Elemente in der Sammlung nicht gerade ist, wird es zurückgegeben.

Didac Montero
quelle
1

@ Rex Kerr Ihre Antwort hat mir geholfen, aber ich musste sie optimieren, um entweder zu verwenden

  
  def foldOrFail [A, B, C, D] (Karte: B => Entweder [D, C]) (Zusammenführen: (A, C) => A) (Initiale: A) (it: Iterable [B]): Entweder [D, A] = {
    val ii = it.iterator
    var b = initial
    while (ii.hasNext) {
      val x = ii.next
      map (x) match {
        case Left (Fehler) => return Left (Fehler)
        case Right (d) => b = merge (b, d)
      }}
    }}
    Richtig (b)
  }}
Ader
quelle
1

Sie können versuchen, eine temporäre Variable und takeWhile zu verwenden. Hier ist eine Version.

  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)

  }

Das evenSumsollte Some(20)in diesem Fall sein.

Möwe1089
quelle
1

Sie können foldMvon Katzen lib verwenden (wie von @Didac vorgeschlagen), aber ich schlage vor, zu verwenden, Eitheranstatt, Optionwenn Sie tatsächliche Summe heraus erhalten möchten.

bifoldMapwird verwendet, um das Ergebnis aus zu extrahieren 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)
      }
    }
  }

Beispiele:

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
rozky
quelle
Kam hierher, um eine ähnliche Antwort zu posten, da dies meiner Meinung nach die bequemste und dennoch FP-Methode ist. Ich war überrascht, dass niemand dafür stimmt. Also schnapp dir meine +1. (Ich bevorzuge (acc + n).asRightstatt Either.right(acc + n)aber trotzdem)
Abdolenz
0

Eine schönere Lösung wäre die Verwendung von span:

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

... aber es durchläuft die Liste zweimal, wenn alle Zahlen gerade sind

Arjan
quelle
2
Ich mag das Querdenken, das durch Ihre Lösung veranschaulicht wird, aber es löst nur das spezifische Beispiel, das in der Frage ausgewählt wurde, anstatt sich mit der allgemeinen Frage zu befassen, wie eine Falte vorzeitig beendet werden kann.
Iainmcgin
Ich wollte zeigen, wie man das Gegenteil macht, nicht eine Falte vorzeitig beenden, sondern nur (in diesem Fall Summe) über die Werte falten, die wir falten wollen
Arjan
0

Nur aus "akademischen" Gründen (:

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

Dauert zweimal als es sollte, aber es ist ein schöner Einzeiler. Wenn "Schließen" nicht gefunden wird, wird es zurückgegeben

headers.size

Ein anderer (besserer) ist dieser:

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