différence entre foldLeft et ReduceLeft dans Scala

196

J'ai appris la différence fondamentale entre foldLeftetreduceLeft

foldLeft:

  • la valeur initiale doit être transmise

réduireGauche:

  • prend le premier élément de la collection comme valeur initiale
  • lève une exception si la collection est vide

Y a-t-il une autre différence?

Une raison spécifique pour avoir deux méthodes avec des fonctionnalités similaires?

Rajesh Pitty
la source
Je vous recommande de voir stackoverflow.com/questions/25158780/…
samthebest
Ce serait génial si vous éditiez la question comme "différence entre plier et réduire dans Scala".
pedram bashiri

Réponses:

302

Peu de choses à mentionner ici, avant de donner la vraie réponse:

  • Votre question n'a rien à voir left, elle concerne plutôt la différence entre la réduction et le pliage
  • La différence n'est pas du tout l'implémentation, il suffit de regarder les signatures.
  • La question n'a rien à voir avec Scala en particulier, elle concerne plutôt les deux concepts de programmation fonctionnelle.

Retour à votre question:

Voici la signature de foldLeft(aurait également pu être foldRightpour le point que je vais faire):

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

Et voici la signature de reduceLeft(encore une fois, la direction n'a pas d'importance ici)

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

Ces deux aspects sont très similaires et ont donc causé la confusion. reduceLeftest un cas particulier de foldLeft(ce qui signifie d'ailleurs que vous pouvez parfois exprimer la même chose en utilisant l'un ou l'autre).

Lorsque vous appelez reduceLeftsay on, List[Int]cela réduira littéralement toute la liste des entiers en une seule valeur, qui sera de type Int(ou un super-type de Int, par conséquent [B >: A]).

Lorsque vous appelez foldLeftsay on a, List[Int]il pliera toute la liste (imaginez rouler un morceau de papier) en une seule valeur, mais cette valeur ne doit même pas être liée à Int(d'où [B]).

Voici un exemple:

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

Cette méthode prend un List[Int]et retourne un Tuple2[List[Int], Int]ou (List[Int], Int). Il calcule la somme et renvoie un tuple avec une liste d'entiers et sa somme. Soit dit en passant, la liste est renvoyée à l'envers, car nous l'avons utilisé à la foldLeftplace de foldRight.

Regardez One Fold pour les gouverner tous pour une explication plus approfondie.

agilesteel
la source
Pouvez-vous expliquer pourquoi Best un super-type de A? Il semble que ce Bdevrait être un sous-type Aet non un super-type. Par exemple, en supposant que Banana <: Fruit <: Foodsi nous avions une liste de Fruits, il semble que cela puisse contenir des Bananas, mais s'il en contenait, Foodle type serait, n'est Food-ce pas? Donc, dans ce cas, si Best un sur-type de Aet qu'il existe une liste contenant à la fois Bs et As, la liste doit être de type B, non A. Pouvez-vous expliquer cet écart?
socom1880
Je ne sais pas si j'ai bien compris votre question. Ce que ma réponse de 5 ans dit à propos de la fonction de réduction est que a List[Banana]peut être réduit à un seul Bananaou à un seul Fruitou à un seul Food. Parce que Fruit :> Bananaet «Nourriture:> Banane».
agilesteel
Oui ... cela a du sens, merci. Je l'interprétais à l'origine comme "une liste de types Bananapeut contenir un Fruit", ce qui n'a pas de sens. Votre explication a un sens - la ffonction à laquelle reduce()vous passez peut entraîner un Fruitou un Food, ce qui signifie que Bla signature doit être une superclasse, pas une sous-classe.
socom1880
193

reduceLeftest juste une méthode pratique. C'est équivalent à

list.tail.foldLeft(list.head)(_)
Kim Stebel
la source
11
Bonne réponse concise :) Je voudrais peut-être corriger l'orthographe de reducelftbien
Hanxue
10
Bonne réponse. Cela souligne également pourquoi foldfonctionne sur une liste vide alors que ce reducen'est pas le cas.
Mansoor Siddiqui
44

foldLeftest plus générique, vous pouvez l'utiliser pour produire quelque chose de complètement différent de ce que vous avez mis à l'origine. Alors que reduceLeftne peut produire qu'un résultat final du même type ou super type du type de collection. Par exemple:

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

Le foldLeftappliquera la fermeture avec le dernier résultat plié (première fois en utilisant la valeur initiale) et la valeur suivante.

reduceLeftd'autre part, combinera d'abord deux valeurs de la liste et les appliquera à la fermeture. Ensuite, il combinera le reste des valeurs avec le résultat cumulatif. Voir:

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

Si la liste est vide foldLeftpeut présenter la valeur initiale comme un résultat légal. reduceLeften revanche n'a pas de valeur légale s'il ne trouve pas au moins une valeur dans la liste.

thoredge
la source
5

La raison fondamentale pour laquelle ils sont tous les deux dans la bibliothèque standard de Scala est probablement parce qu'ils sont tous les deux dans la bibliothèque standard de Haskell (appelés foldlet foldl1). Si ce reduceLeftn'était pas le cas, elle serait très souvent définie comme une méthode pratique dans différents projets.

Alexey Romanov
la source
5

Pour référence, une reduceLefterreur s’applique à un conteneur vide avec l’erreur suivante.

java.lang.UnsupportedOperationException: empty.reduceLeft

Retravailler le code à utiliser

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

est une option potentielle. Une autre consiste à utiliser la reduceLeftOptionvariante qui renvoie un résultat encapsulé Option.

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

De Principes de programmation fonctionnels à Scala (Martin Odersky):

La fonction reduceLeftest définie en termes d'une fonction plus générale, foldLeft.

foldLeftest comme reduceLeftmais prend un accumulateur z , comme paramètre supplémentaire, qui est retourné quand foldLeftest appelé sur une liste vide:

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

[par opposition à reduceLeft, qui lève une exception lorsqu'il est appelé sur une liste vide.]

Le cours (voir la conférence 5.5) fournit des définitions abstraites de ces fonctions, qui illustrent leurs différences, bien qu'elles soient très similaires dans leur utilisation de la correspondance de motifs et de la récursivité.

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

Notez que foldLeftrenvoie une valeur de type U, qui n'est pas nécessairement le même type que List[T], mais ReduceLeft renvoie une valeur du même type que la liste).

C8H10N4O2
la source
0

Pour vraiment comprendre ce que vous faites avec le repli / réduction, vérifiez ceci: http://wiki.tcl.tk/17983 très bonne explication. une fois que vous obtenez le concept de pli, la réduction s'affichera avec la réponse ci-dessus: list.tail.foldLeft (list.head) (_)

Henry H.
la source