Unterschied zwischen FoldLeft und ReduceLeft in Scala

196

Ich habe den grundlegenden Unterschied zwischen foldLeftund gelerntreduceLeft

foldLeft:

  • Anfangswert muss übergeben werden

reduziere:

  • Nimmt das erste Element der Sammlung als Anfangswert
  • löst eine Ausnahme aus, wenn die Sammlung leer ist

Gibt es noch einen anderen Unterschied?

Gibt es einen bestimmten Grund für zwei Methoden mit ähnlicher Funktionalität?

Rajesh Pitty
quelle
Empfehlen Sie, dass Sie stackoverflow.com/questions/25158780/…
samthebest
Wäre toll, wenn Sie die Frage so bearbeiten würden, dass sie "Unterschied zwischen Falten und Reduzieren in Scala" ist.
Pedram Bashiri

Antworten:

302

Einige Dinge, die hier zu erwähnen sind, bevor die eigentliche Antwort gegeben wird:

  • Ihre Frage hat nichts damit zu tun left, es geht vielmehr um den Unterschied zwischen Reduzieren und Falten
  • Der Unterschied ist überhaupt nicht die Implementierung, schauen Sie sich nur die Signaturen an.
  • Die Frage hat insbesondere nichts mit Scala zu tun, sondern handelt von den beiden Konzepten der funktionalen Programmierung.

Zurück zu Ihrer Frage:

Hier ist die Unterschrift von foldLeft(könnte auch foldRightfür den Punkt gewesen sein, den ich machen werde):

def foldLeft [B] (z: B)(f: (B, A) => B): B

Und hier ist die Unterschrift von reduceLeft(auch hier spielt die Richtung keine Rolle)

def reduceLeft [B >: A] (f: (B, A) => B): B

Diese beiden sehen sich sehr ähnlich und haben somit die Verwirrung verursacht. reduceLeftist ein Sonderfall von foldLeft(was übrigens bedeutet, dass Sie manchmal dasselbe ausdrücken können, indem Sie einen von beiden verwenden).

Wenn Sie reduceLeftsay on a aufrufen , List[Int]wird die gesamte Liste der Ganzzahlen buchstäblich auf einen einzigen Wert reduziert, der vom Typ Int(oder Intdaher vom Supertyp von [B >: A]) sein wird.

Wenn Sie foldLeftsay on a aufrufen , List[Int]wird die gesamte Liste (stellen Sie sich vor, Sie rollen ein Stück Papier) zu einem einzigen Wert zusammengefasst, aber dieser Wert muss nicht einmal mit Int(daher [B]) verknüpft sein .

Hier ist ein Beispiel:

def listWithSum(numbers: List[Int]) = numbers.foldLeft((List.empty[Int], 0)) {
   (resultingTuple, currentInteger) =>
      (currentInteger :: resultingTuple._1, currentInteger + resultingTuple._2)
}

Diese Methode nimmt ein List[Int]und gibt ein Tuple2[List[Int], Int]oder zurück (List[Int], Int). Es berechnet die Summe und gibt ein Tupel mit einer Liste von ganzen Zahlen und seiner Summe zurück. Übrigens wird die Liste rückwärts zurückgegeben, weil wir foldLeftstatt verwendet haben foldRight.

Beobachten Sie One Fold, um sie alle zu regieren und eine ausführlichere Erklärung zu erhalten.

agilesteel
quelle
Können Sie erklären, warum Bein Supertyp von ist A? Es scheint, als Bsollte es sich tatsächlich um einen Subtyp handeln A, nicht um einen Supertyp. Angenommen Banana <: Fruit <: Food, wenn wir eine Liste von Fruits hätten, könnte diese einige Bananas enthalten , aber wenn sie Foods enthalten würde Food, wäre der Typ richtig? In diesem Fall sollte die Liste vom Typ sein , wenn Bes sich um einen Supertyp von handelt Aund es eine Liste gibt, die sowohl Bs als auch As enthält . Können Sie diese Diskrepanz erklären? BA
socom1880
Ich bin mir nicht sicher, ob ich Ihre Frage richtig verstehe. Was meine 5-jährige Antwort über die Reduktionsfunktion sagt, ist, dass a List[Banana]auf eine einzelne Bananaoder eine einzelne Fruitoder eine einzelne reduziert werden kann Food. Weil Fruit :> Bananaund `Essen:> Banane '.
Agilesteel
Ja ... das macht tatsächlich Sinn, danke. Ich habe es ursprünglich als "eine Liste von Typen Bananakann ein enthalten Fruit" interpretiert , was keinen Sinn ergibt. Ihre Erklärung ist sinnvoll - die fFunktion, an die übergeben wird, reduce()kann zu a Fruitoder a führen Food, was bedeutet, dass Bdie Signatur eine Oberklasse und keine Unterklasse sein sollte.
socom1880
193

reduceLeftist nur eine bequeme Methode. Es ist äquivalent zu

list.tail.foldLeft(list.head)(_)
Kim Stebel
quelle
11
Gut, prägnante Antwort :) Könnte die Rechtschreibung korrigieren wollen , reducelftobwohl
Hanxue
10
Gute Antwort. Dies zeigt auch, warum foldeine leere Liste reducenicht funktioniert.
Mansoor Siddiqui
44

foldLeftist allgemeiner, Sie können es verwenden, um etwas völlig anderes als das zu produzieren, was Sie ursprünglich eingegeben haben. Während reduceLeftnur ein Endergebnis des gleichen Typs oder Supertyps des Sammlungstyps erzeugt werden kann. Beispielsweise:

List(1,3,5).foldLeft(0) { _ + _ }
List(1,3,5).foldLeft(List[String]()) { (a, b) => b.toString :: a }

Das foldLeftwird den Verschluss mit dem zuletzt gefalteten Ergebnis (zum ersten Mal unter Verwendung des Anfangswertes) und dem nächsten Wert anwenden.

reduceLeftAuf der anderen Seite werden zuerst zwei Werte aus der Liste kombiniert und diese auf den Abschluss angewendet. Als nächstes werden die restlichen Werte mit dem kumulativen Ergebnis kombiniert. Sehen:

List(1,3,5).reduceLeft { (a, b) => println("a " + a + ", b " + b); a + b }

Wenn die Liste leer ist, foldLeftkann der Anfangswert als rechtliches Ergebnis angezeigt werden. reduceLeftAuf der anderen Seite hat es keinen legalen Wert, wenn es nicht mindestens einen Wert in der Liste finden kann.

thoredge
quelle
5

Der Hauptgrund, warum sie sich beide in der Scala-Standardbibliothek befinden, ist wahrscheinlich, dass sie sich beide in der Haskell-Standardbibliothek befinden (aufgerufen foldlund foldl1). Wenn dies reduceLeftnicht der Fall wäre, würde es in verschiedenen Projekten häufig als praktische Methode definiert.

Alexey Romanov
quelle
5

Als Referenz reduceLeftwird ein Fehler auftreten, wenn er auf einen leeren Container mit dem folgenden Fehler angewendet wird.

java.lang.UnsupportedOperationException: empty.reduceLeft

Überarbeitung des zu verwendenden Codes

myList foldLeft(List[String]()) {(a,b) => a+b}

ist eine mögliche Option. Eine andere Möglichkeit besteht darin, die reduceLeftOptionVariante zu verwenden, die ein mit Option umschlossenes Ergebnis zurückgibt.

myList reduceLeftOption {(a,b) => a+b} match {
  case None    => // handle no result as necessary
  case Some(v) => println(v)
}
Martin Smith
quelle
2

Aus funktionalen Programmierprinzipien in Scala (Martin Odersky):

Die Funktion reduceLeftwird als allgemeinere Funktion definiert foldLeft.

foldLeftist wie reduceLeft, nimmt aber einen Akkumulator z als zusätzlichen Parameter, der zurückgegeben wird, wenn foldLefter in einer leeren Liste aufgerufen wird:

(List (x1, ..., xn) foldLeft z)(op) = (...(z op x1) op ...) op x

[im Gegensatz zu reduceLeft, was eine Ausnahme auslöst, wenn es auf einer leeren Liste aufgerufen wird.]

Der Kurs (siehe Vorlesung 5.5) enthält abstrakte Definitionen dieser Funktionen, die ihre Unterschiede veranschaulichen, obwohl sie sich in der Verwendung von Mustervergleich und Rekursion sehr ähnlich sind.

abstract class List[T] { ...
  def reduceLeft(op: (T,T)=>T) : T = this match{
    case Nil     => throw new Error("Nil.reduceLeft")
    case x :: xs => (xs foldLeft x)(op)
  }
  def foldLeft[U](z: U)(op: (U,T)=>U): U = this match{
    case Nil     => z
    case x :: xs => (xs foldLeft op(z, x))(op)
  }
}

Beachten Sie, dass foldLeftein Wert vom Typ zurückgegeben wird U, der nicht unbedingt vom selben Typ ist wie List[T], aber reduLeft einen Wert vom selben Typ wie die Liste zurückgibt.

C8H10N4O2
quelle
0

Um wirklich zu verstehen, was Sie mit Fold / Reduce machen, überprüfen Sie dies: http://wiki.tcl.tk/17983 sehr gute Erklärung. Sobald Sie das Konzept der Falte erhalten haben, wird Reduzieren zusammen mit der obigen Antwort angezeigt: list.tail.foldLeft (list.head) (_)

Henry H.
quelle