diferencia entre foldLeft y reduceLeft en Scala

functional-programming higher-order-functions

Question

Aprendí la diferencia básica entre foldLeft y reduceLeft

foldLeft:

• el valor inicial tiene que ser pasado

reduceLeft:

• toma el primer elemento de la colección como valor inicial
• arroja 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?

Answer 1

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

java.lang.UnsupportedOperationException: empty.reduceLeft

Retrabajando el código para usar

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

es una opción potencial. Otra opción es usar la variante reduceLeftOption , que reduceLeftOption un resultado envuelto por la opción.

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

Answer 2

De Principios de Programación Funcional en Scala (Martin Odersky):

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

foldLeft es como reduceLeft pero toma un acumulador z , como un parámetro adicional, que se devuelve cuando se llama a foldLeft en una lista vacía:

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

[a diferencia de reduceLeft , que lanza una excepción cuando se llama en una lista vacía.]

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

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 foldLeft devuelve un valor de tipo U , que no es necesariamente del mismo tipo que List[T] , pero reduceLeft devuelve un valor del mismo tipo que la lista).

Answer 3

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 Haskell (llamada foldl y foldl1 ). Si no fue reduceLeft , a menudo se define como un método de conveniencia en diferentes proyectos.

Answer 4

Para entender realmente qué haces con fold / reduce, mira esto: http://wiki.tcl.tk/17983 muy buena explicación. una vez que obtenga el concepto de fold, reduce se combinará con la respuesta anterior: list.tail.foldLeft (list.head) (_)

Answer 5

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

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

De vuelta a tu pregunta:

Aquí está la firma de foldLeft (también podría haber sido foldRight para 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 parecen muy similares y causaron la confusión. reduceLeft es un caso especial de foldLeft (que, por cierto, significa que a veces puedes expresar lo mismo al usar cualquiera de ellos).

Cuando llame a reduceLeft diga en una List[Int] que 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 foldLeft diga en una List[Int] que foldLeft toda la lista (imagine enrollar una hoja de papel) en un solo valor, pero este valor no tiene que estar ni siquiera relacionado con Int (de ahí [B] ).

Aquí hay un ejemplo:

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

Este método toma una 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 su suma. Por cierto, la lista se devuelve al revés, porque usamos foldLeft lugar de foldRight .

Answer 6

foldLeft es más genérico, puede usarlo para producir algo completamente diferente de lo que originalmente reduceLeft . Mientras que reduceLeft solo puede producir un resultado final del mismo tipo o súper tipo 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 foldLeft aplicará el cierre con el último resultado doblado (la primera vez que usa el valor inicial) y el siguiente valor.

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

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

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

Answer 7

reduceLeft es solo un método de conveniencia. Es equivalente a

list.tail.foldLeft(list.head)(_)