scala fold

¿Reducir, doblar o escanear(izquierda/derecha)?

Question

¿Cuándo debo usar reduceLeft , reduceRight , foldLeft , foldRight , scanLeft o scanRight ?

Quiero una intuición / visión general de sus diferencias, posiblemente con algunos ejemplos simples.

Answer 1

En general, todas las funciones de 6 veces aplican un operador binario a cada elemento de una colección. El resultado de cada paso se pasa al siguiente paso (como entrada a uno de los dos argumentos del operador binario). De esta forma podemos acumular un resultado.

reduceLeft y reduceRight un solo resultado.

foldLeft y foldRight un solo resultado utilizando un valor de inicio.

scanLeft y scanRight una colección de resultados acumulados intermedios utilizando un valor de inicio.

Acumular

Desde la IZQUIERDA y hacia adelante ...

Con una colección de elementos abc y un operador binario add , podemos explorar lo que hacen las diferentes funciones de plegado al avanzar desde el elemento IZQUIERDO de la colección (de A a C):

val abc = List("A", "B", "C")

def add(res: String, x: String) = { 
  println(s"op: $res + $x = ${res + x}")
  res + x
}

abc.reduceLeft(add)
// op: A + B = AB
// op: AB + C = ABC    // accumulates value AB in *first* operator arg `res`
// res: String = ABC

abc.foldLeft("z")(add) // with start value "z"
// op: z + A = zA      // initial extra operation
// op: zA + B = zAB
// op: zAB + C = zABC
// res: String = zABC

abc.scanLeft("z")(add)
// op: z + A = zA      // same operations as foldLeft above...
// op: zA + B = zAB
// op: zAB + C = zABC
// res: List[String] = List(z, zA, zAB, zABC) // maps intermediate results

Desde la DERECHA y hacia atrás ...

Si comenzamos con el elemento DERECHO y retrocedemos (de C a A) notaremos que ahora el segundo argumento para nuestro operador binario acumula el resultado (el operador es el mismo, simplemente cambiamos los nombres de los argumentos para dejar claros sus roles) )

def add(x: String, res: String) = {
  println(s"op: $x + $res = ${x + res}")
  x + res
}

abc.reduceRight(add)
// op: B + C = BC
// op: A + BC = ABC  // accumulates value BC in *second* operator arg `res`
// res: String = ABC

abc.foldRight("z")(add)
// op: C + z = Cz
// op: B + Cz = BCz
// op: A + BCz = ABCz
// res: String = ABCz

abc.scanRight("z")(add)
// op: C + z = Cz
// op: B + Cz = BCz
// op: A + BCz = ABCz
// res: List[String] = List(ABCz, BCz, Cz, z)

.

De-cumulate

Desde la IZQUIERDA y hacia adelante ...

Si, en cambio, debiésemos des-acumular algún resultado por resta a partir del elemento IZQUIERDO de una colección, podríamos acumular el resultado a través del primer argumento res de nuestro operador binario minus :

val xs = List(1, 2, 3, 4)

def minus(res: Int, x: Int) = {
  println(s"op: $res - $x = ${res - x}")
  res - x
}

xs.reduceLeft(minus)
// op: 1 - 2 = -1
// op: -1 - 3 = -4  // de-cumulates value -1 in *first* operator arg `res`
// op: -4 - 4 = -8
// res: Int = -8

xs.foldLeft(0)(minus)
// op: 0 - 1 = -1
// op: -1 - 2 = -3
// op: -3 - 3 = -6
// op: -6 - 4 = -10
// res: Int = -10

xs.scanLeft(0)(minus)
// op: 0 - 1 = -1
// op: -1 - 2 = -3
// op: -3 - 3 = -6
// op: -6 - 4 = -10
// res: List[Int] = List(0, -1, -3, -6, -10)

Desde la DERECHA y hacia atrás ...

¡Pero cuidado con las variaciones de xRight ahora! Recuerde que el valor (des) acumulado en las variaciones xRight se pasa al segundo parámetro res de nuestro operador binario minus :

def minus(x: Int, res: Int) = {
  println(s"op: $x - $res = ${x - res}")
  x - res
}

xs.reduceRight(minus)
// op: 3 - 4 = -1
// op: 2 - -1 = 3  // de-cumulates value -1 in *second* operator arg `res`
// op: 1 - 3 = -2
// res: Int = -2

xs.foldRight(0)(minus)
// op: 4 - 0 = 4
// op: 3 - 4 = -1
// op: 2 - -1 = 3
// op: 1 - 3 = -2
// res: Int = -2

xs.scanRight(0)(minus)
// op: 4 - 0 = 4
// op: 3 - 4 = -1
// op: 2 - -1 = 3
// op: 1 - 3 = -2
// res: List[Int] = List(-2, 3, -1, 4, 0) 

¡La última lista (-2, 3, -1, 4, 0) quizás no sea lo que intuitivamente esperarías!

Como puede ver, puede verificar qué está haciendo su foldX simplemente ejecutando un scanX en su lugar y depurando el resultado acumulado en cada paso.

Línea de fondo

• Acumule un resultado con reduceLeft o reduceRight .
• Acumule un resultado con foldLeft o foldRight si tiene un valor de inicio.

• Acumule una colección de resultados intermedios con scanLeft o scanRight .

• Use una variación xLeft si desea avanzar en la colección.

• Use una variación xRight si desea retroceder en la colección.

Answer 2

Normalmente, el método REDUCE, FOLD, SCAN funciona acumulando datos a la IZQUIERDA y sigue cambiando la variable DERECHA. La principal diferencia entre ellos es REDUCE, FOLD es: -

El plegado siempre comenzará con un valor seed , es decir, el valor de inicio definido por el usuario. Reducir lanzará una excepción si la colección está vacía, ya que al doblar devuelve el valor inicial. Siempre dará como resultado un valor único.

El escaneo se usa para algunas órdenes de procesamiento de elementos del lado izquierdo o derecho, luego podemos utilizar el resultado anterior en el cálculo posterior. Eso significa que podemos escanear elementos. Siempre resultará una colección.

• El método LEFT_REDUCE funciona de forma similar al método REDUCE.

• RIGHT_REDUCE es opuesto a reduceLeft one, es decir, acumula valores en DERECHA y sigue cambiando la variable izquierda.

• reduceLeftOption y reduceRightOption son similares a left_reduce y right_reduce solo la diferencia es que devuelven resultados en el objeto OPTION.

Una parte del resultado del código mencionado a continuación sería:

usando la operación de scan sobre una lista de números (usando seed valor seed 0 ) List(-2,-1,0,1,2)

• {0, -2} => - 2 {-2, -1} => - 3 {-3,0} => - 3 {-3,1} => - 2 {-2,2} => 0 Lista de escaneo (0, -2, -3, -3, -2, 0)

• {0, -2} => - 2 {-2, -1} => - 3 {-3,0} => - 3 {-3,1} => - 2 {-2,2} => 0 ScanLeft (a + b) List (0, -2, -3, -3, -2, 0)

• {0, -2} => - 2 {-2, -1} => - 3 {-3,0} => - 3 {-3,1} => - 2 {-2,2} => 0 Lista de ScanLeft (b + a) (0, -2, -3, -3, -2, 0)

• {2,0} => 2 {1,2} => 3 {0,3} => 3 {-1,3} => 2 {-2,2} => 0 lista de ScanRight (a + b) ( 0, 2, 3, 3, 2, 0)

• {2,0} => 2 {1,2} => 3 {0,3} => 3 {-1,3} => 2 {-2,2} => 0 lista de ScanRight (b + a) ( 0, 2, 3, 3, 2, 0)

utilizando operaciones de reduce , fold sobre una lista de lista de cadenas List("A","B","C","D","E")

• {A, B} => AB {AB, C} => ABC {ABC, D} => ABCD {ABCD, E} => ABCDE reduce (a + b) ABCDE
• {A, B} => AB {AB, C} => ABC {ABC, D} => ABCD {ABCD, E} => ABCDE reduceLeft (a + b) ABCDE
• {A, B} => BA {BA, C} => CBA {CBA, D} => DCBA {DCBA, E} => EDCBA reduceLeft (b + a) EDCB
• {D, E} => DE {C, DE} => CDE {B, CDE} => BCDE {A, BCDE} => ABCDE reduceRight (a + b) ABCDE
• {D, E} => ED {C, ED} => EDC {B, EDC} => EDCB {A, EDCB} => EDCBA reduceRight (b + a) EDCBA

Código:

object ScanFoldReduce extends App {

    val list = List("A","B","C","D","E")
            println("reduce (a+b) "+list.reduce((a,b)=>{
                print("{"+a+","+b+"}=>"+ (a+b)+"  ")
                a+b
            }))

            println("reduceLeft (a+b) "+list.reduceLeft((a,b)=>{
                print("{"+a+","+b+"}=>"+ (a+b)+"  ")
                a+b
            }))

            println("reduceLeft (b+a) "+list.reduceLeft((a,b)=>{
                print("{"+a+","+b+"}=>"+ (b+a)+"  " )
                b+a
            }))

            println("reduceRight (a+b) "+list.reduceRight((a,b)=>{
                print("{"+a+","+b+"}=>"+ (a+b)+"  " )
                a+b
            }))

            println("reduceRight (b+a) "+list.reduceRight((a,b)=>{
                print("{"+a+","+b+"}=>"+ (b+a)+"  ")
                b+a
            }))

            println("scan            "+list.scan("[")((a,b)=>{
                print("{"+a+","+b+"}=>"+ (a+b)+"  " )
                a+b
            }))
            println("scanLeft (a+b)  "+list.scanLeft("[")((a,b)=>{
                print("{"+a+","+b+"}=>"+ (a+b)+"  " )
                a+b
            }))
            println("scanLeft (b+a)  "+list.scanLeft("[")((a,b)=>{
                print("{"+a+","+b+"}=>"+ (b+a)+"  " )
                b+a
            }))
            println("scanRight (a+b) "+list.scanRight("[")((a,b)=>{
                print("{"+a+","+b+"}=>"+ (a+b)+"  " )
                a+b
            }))
            println("scanRight (b+a) "+list.scanRight("[")((a,b)=>{
                print("{"+a+","+b+"}=>"+ (b+a)+"  " )
                b+a
            }))
//Using numbers
     val list1 = List(-2,-1,0,1,2)

            println("reduce (a+b) "+list1.reduce((a,b)=>{
                print("{"+a+","+b+"}=>"+ (a+b)+"  ")
                a+b
            }))

            println("reduceLeft (a+b) "+list1.reduceLeft((a,b)=>{
                print("{"+a+","+b+"}=>"+ (a+b)+"  ")
                a+b
            }))

            println("reduceLeft (b+a) "+list1.reduceLeft((a,b)=>{
                print("{"+a+","+b+"}=>"+ (b+a)+"  " )
                b+a
            }))

            println("      reduceRight (a+b) "+list1.reduceRight((a,b)=>{
                print("{"+a+","+b+"}=>"+ (a+b)+"  " )
                a+b
            }))

            println("      reduceRight (b+a) "+list1.reduceRight((a,b)=>{
                print("{"+a+","+b+"}=>"+ (b+a)+"  ")
                b+a
            }))

            println("scan            "+list1.scan(0)((a,b)=>{
                print("{"+a+","+b+"}=>"+ (a+b)+"  " )
                a+b
            }))

            println("scanLeft (a+b)  "+list1.scanLeft(0)((a,b)=>{
                print("{"+a+","+b+"}=>"+ (a+b)+"  " )
                a+b
            }))

            println("scanLeft (b+a)  "+list1.scanLeft(0)((a,b)=>{
                print("{"+a+","+b+"}=>"+ (b+a)+"  " )
                b+a
            }))

            println("scanRight (a+b)         "+list1.scanRight(0)((a,b)=>{
                print("{"+a+","+b+"}=>"+ (a+b)+"  " )
                a+b}))

            println("scanRight (b+a)         "+list1.scanRight(0)((a,b)=>{
                print("{"+a+","+b+"}=>"+ (a+b)+"  " )
                b+a}))
}