Quando devo usar reduceLeft, reduceRight, foldLeft, foldRight, scanLeftou scanRight?

Quero uma intuição / visão geral de suas diferenças - possivelmente com alguns exemplos simples.

Em geral, todas as funções de 6 dobras aplicam um operador binário a cada elemento de uma coleção. O resultado de cada etapa é passado para a próxima etapa (como entrada para um dos dois argumentos do operador binário). Dessa forma, podemos acumular um resultado.

reduceLefte reduceRightacumule um único resultado.

foldLefte foldRightacumule um único resultado usando um valor inicial.

scanLefte scanRightacumule uma coleção de resultados cumulativos intermediários usando um valor inicial.

Acumular

Da esquerda para a frente ...

Com uma coleção de elementos abce um operador binário add, podemos explorar o que as diferentes funções de dobra fazem ao avançar do elemento LEFT da coleção (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

À DIREITA e para trás ...

Se começarmos com o elemento RIGHT e voltarmos (de C para A), perceberemos que agora o segundo argumento para nosso operador binário acumula o resultado (o operador é o mesmo, apenas trocamos os nomes dos argumentos para deixar suas funções claras ):

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-acumular

Da esquerda para a frente ...

Se, em vez disso, deduzirmos algum resultado por subtração a partir do elemento LEFT de uma coleção, acumularemos o resultado através do primeiro argumento resdo nosso operador binário 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)

À DIREITA e para trás ...

Mas esteja atento às variações do xRight agora! Lembre-se de que o valor (des-) acumulado nas variações xRight é passado para o segundo parâmetro resdo nosso operador binário 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) 

A última lista (-2, 3, -1, 4, 0) talvez não seja o que você esperaria intuitivamente!

Como você vê, você pode verificar o que o seu foldX está fazendo, basta executar um scanX e depurar o resultado acumulado a cada etapa.

Bottom line

• Acumule um resultado com reduceLeftou reduceRight.
• Acumule um resultado com foldLeftou foldRightse você tiver um valor inicial.

• Acumule uma coleção de resultados intermediários com scanLeftou scanRight.

• Use uma variação do xLeft se desejar avançar pela coleção.

• Use uma variação xRight se você quiser retroceder na coleção.

Normalmente, o método REDUCE, FOLD, SCAN funciona acumulando dados em ESQUERDA e continua alterando a variável RIGHT. A principal diferença entre eles é REDUCE, FOLD é: -

A dobra sempre começará com um seedvalor, ou seja, um valor inicial definido pelo usuário. Reduzir lançará uma exceção se a coleção estiver vazia, onde, como dobra, devolve o valor inicial. Sempre resultará em um único valor.

A digitalização é usada para alguma ordem de processamento de itens do lado esquerdo ou direito, para que possamos usar o resultado anterior no cálculo subsequente. Isso significa que podemos digitalizar itens. Sempre resultará em uma coleção.

• O método LEFT_REDUCE funciona de maneira semelhante ao método REDUCE.

• RIGHT_REDUCE é o oposto de reduzir à esquerda, isto é, ele acumula valores em RIGHT e continua alterando a variável esquerda.

• reduzirLeftOption e reduzirRightOption são semelhantes a left_reduce e right_reduce. A única diferença é que retornam resultados no objeto OPTION.

Uma parte da saída do código abaixo mencionado seria: -

usando scanoperação sobre uma lista de números (usando seedvalor 0)List(-2,-1,0,1,2)

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

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

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

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

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

usando reduce, foldoperações sobre uma lista de StringsList("A","B","C","D","E")

• {A, B} => AB {AB, C} => ABC {ABC, D} => ABCD {ABCD, E} => ABCDE reduz (a + b) ABCDE
• {A, B} => AB {AB, C} => ABC {ABC, D} => ABCD {ABCD, E} => ABCDE reduzaLeft (a + b) ABCDE
• {A, B} => BA {BA, C} => CBA {CBA, D} => DCBA {DCBA, E} => EDCBA reduzirLeft (b + a) EDCB
• {D, E} => DE {C, DE} => CDE {B, CDE} => BCDE {A, BCDE} => ABCDE reduzaRight (a + b) ABCDE
• {D, E} => ED {C, ED} => EDC {B, EDC} => EDCB {A, EDCB} => EDCBA reduzaRight (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}))
}

Para a coleção x com os elementos x0, x1, x2, x3 e uma função arbitrária f, você tem o seguinte:

1. x.reduceLeft    (f) is f(f(f(x0,x1),x2),x3) - notice 3 function calls
2. x.reduceRight   (f) is f(f(f(x3,x2),x1),x0) - notice 3 function calls
3. x.foldLeft (init,f) is f(f(f(f(init,x0),x1),x2),x3) - notice 4 function calls
4. x.foldRight(init,f) is f(f(f(f(init,x3),x2),x1),x0) - notice 4 function calls
5. x.scanLeft (init,f) is f(init,x0)=g0
                          f(f(init,x0),x1) = f(g0,x1) = g1
                          f(f(f(init,x0),x1),x2) = f(g1,x2) = g2
                          f(f(f(f(init,x0),x1),x2),x3) = f(g2,x3) = g3
                          - notice 4 function calls but also 4 emitted values
                          - last element is identical with foldLeft
6. x.scanRight (init,f) is f(init,x3)=h0
                          f(f(init,x3),x2) = f(h0,x2) = h1
                          f(f(f(init,x3),x2),x1) = f(h1,x1) = h2
                          f(f(f(f(init,x3),x2),x1),x0) = f(h2,x0) = h3
                          - notice 4 function calls but also 4 emitted values
                          - last element is identical with foldRight

Em conclusão

• scané como, foldmas também emite todos os valores intermediários
• reduce não precisa de um valor inicial que às vezes é um pouco mais difícil de encontrar
• fold precisa de um valor inicial um pouco mais difícil de encontrar:
  • 0 para somas
  • 1 para produtos
  • primeiro elemento para min (alguns podem sugerir Integer.MAX_VALUE)
• Não tenho 100% de certeza, mas parece que existem essas implementações equivalentes:
  • x.reduceLeft(f) === x.drop(1).foldLeft(x.head,f)
  • x.foldRight(init,f) === x.reverse.foldLeft(init,f)
  • x.foldLeft(init,f) === x.scanLeft(init,f).last