diferencia entre foldLeft y reduceLeft en Scala

196

He aprendido la diferencia básica entre foldLeftyreduceLeft

foldLeft:

  • se debe pasar el valor inicial

reducir Izquierda:

  • toma el primer elemento de la colección como valor inicial
  • lanza una excepción si la colección está vacía

¿Hay alguna otra diferencia?

¿Alguna razón específica para tener dos métodos con una funcionalidad similar?

Rajesh Pitty
fuente
Te recomiendo que veas stackoverflow.com/questions/25158780/…
samthebest
Sería genial si editaras la pregunta como "diferencia entre doblar y reducir en Scala".
pedram bashiri

Respuestas:

302

Pocas cosas para mencionar aquí, antes de dar la respuesta real:

  • Su pregunta no tiene nada que ver left, se trata más bien de la diferencia entre reducir y plegar
  • La diferencia no es la implementación en absoluto, solo mira las firmas.
  • La pregunta no tiene nada que ver con Scala en particular, sino con los dos conceptos de programación funcional.

De vuelta a su pregunta:

Aquí está la firma de foldLeft(también podría haber sido foldRightpara el punto que voy a hacer):

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

Y aquí está la firma de reduceLeft(de nuevo, la dirección no importa aquí)

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

Estos dos se ven muy similares y por lo tanto causaron la confusión. reduceLeftes un caso especial de foldLeft(que por cierto significa que a veces puedes expresar lo mismo usando cualquiera de ellos).

Cuando llame a reduceLeftsay en un List[Int], literalmente reducirá toda la lista de enteros en un solo valor, que será de tipo Int(o un supertipo de Int, por lo tanto [B >: A]).

Cuando llame a foldLeftsay en un List[Int], plegará toda la lista (imagine rodar un trozo de papel) en un solo valor, pero este valor no tiene que estar relacionado Int(por lo tanto [B]).

Aquí hay un ejemplo:

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

Este método toma un List[Int]y devuelve un Tuple2[List[Int], Int]o (List[Int], Int). Calcula la suma y devuelve una tupla con una lista de enteros y es la suma. Por cierto, la lista se devuelve hacia atrás, porque usamos en foldLeftlugar de foldRight.

Mira One Fold para gobernarlos a todos y obtener una explicación más detallada.

agilesteel
fuente
¿Puedes explicar por qué Bes un supertipo de A? Parece Bque en realidad debería ser un subtipo de A, no un supertipo. Por ejemplo, suponiendo que Banana <: Fruit <: Foodsi tuviéramos una lista de Fruits, parece que puede contener algunos Bananas, pero si contuviera alguno Food, el tipo sería Food, ¿correcto? Así pues, en este caso, si Bes un subtipo de él Ay hay una lista que contiene ambos Bs y As, la lista debe ser de tipo B, no A. ¿Puedes explicar esta discrepancia?
socom1880
No estoy seguro si entiendo tu pregunta correctamente. Lo que dice mi respuesta de 5 años sobre la función reducir es que a List[Banana]puede reducirse a un solo Bananao un solo Fruito un solo Food. Porque Fruit :> Bananay 'Comida:> Plátano'.
agilesteel
Sí ... eso realmente tiene sentido, gracias. Originalmente lo estaba interpretando como "una lista de tipos Bananapuede contener un Fruit", lo que no tiene sentido. Su explicación tiene sentido: la ffunción que se pasa reduce()puede dar como resultado a Fruito a Food, lo que significa que Bla firma debe ser una superclase, no una subclase.
socom1880
193

reduceLeftEs solo un método de conveniencia. Es equivalente a

list.tail.foldLeft(list.head)(_)
Kim Stebel
fuente
11
Buena respuesta concisa :) Sin reducelftembargo
posible que
10
Buena respuesta. Esto también destaca por qué foldfunciona en una lista vacía, mientras reduceque no.
Mansoor Siddiqui
44

foldLeftes más genérico, puede usarlo para producir algo completamente diferente de lo que introdujo originalmente. Mientras reduceLeftque solo puede producir un resultado final del mismo tipo o supertipo del tipo de colección. Por ejemplo:

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

El foldLeftva a aplicar el cierre con el último resultado plegada (por primera vez usando el valor inicial) y el siguiente valor.

reduceLeftpor otro lado, primero combinará dos valores de la lista y los aplicará al cierre. A continuación, combinará el resto de los valores con el resultado acumulativo. Ver:

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

Si la lista está vacía, foldLeftpuede presentar el valor inicial como un resultado legal. reduceLeftpor otro lado, no tiene un valor legal si no puede encontrar al menos un valor en la lista.

Thoredge
fuente
5

La razón básica por la que ambos están en la biblioteca estándar de Scala es probablemente porque ambos están en la biblioteca estándar de Haskell (llamada foldly foldl1). Si reduceLeftno fuera así, a menudo se definiría como un método de conveniencia en diferentes proyectos.

Alexey Romanov
fuente
5

Como referencia, se reduceLeftproducirá un error si se aplica a un contenedor vacío con el siguiente error.

java.lang.UnsupportedOperationException: empty.reduceLeft

Reelaborando el código para usar

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

Es una opción potencial. Otra es usar la reduceLeftOptionvariante que devuelve un resultado envuelto en Opción.

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

De los principios de programación funcional en Scala (Martin Odersky):

La función reduceLeftse define en términos de una función más general, foldLeft.

foldLeftes como, reduceLeftpero toma un acumulador z , como parámetro adicional, que se devuelve cuando foldLeftse llama en una lista vacía:

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

[a diferencia de reduceLeft, lo que arroja una excepción cuando se invoca en una lista vacía.]

El curso (ver lección 5.5) proporciona definiciones abstractas de estas funciones, que ilustran sus diferencias, aunque son muy similares en su uso de la coincidencia de patrones y la recursividad.

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

Tenga en cuenta que foldLeftdevuelve un valor de tipo U, que no es necesariamente el mismo tipo que List[T], pero reduceLeft devuelve un valor del mismo tipo que la lista).

C8H10N4O2
fuente
0

Para comprender realmente lo que está haciendo con fold / reduce, consulte esto: http://wiki.tcl.tk/17983 muy buena explicación. una vez que obtenga el concepto de doblar, reducir aparecerá junto con la respuesta anterior: list.tail.foldLeft (list.head) (_)

Henry H.
fuente