Reduzir, dobrar ou digitalizar (Esquerda / Direita)?

187

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.

Marc Grue
fonte
Recomendo que você veja stackoverflow.com/questions/25158780/…
samthebest
1
Obrigado pelo ponteiro. Está um pouco acima do meu conhecimento técnico :) Existe algo na minha resposta que você acha que deveria ser esclarecido / alterado?
Marc Grue
Não, apenas apontando um pouco da história e a relevância para o MPP.
samthebest
Bem, estritamente falando, a distinção entre reducee foldNÃO é a existência de um valor inicial - é uma consequência de uma razão matemática subjacente mais profunda.
precisa

Respostas:

370

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.
Marc Grue
fonte
14
Se não me engano, a versão esquerda pode usar a otimização de chamada de cauda, ​​o que significa que é muito mais eficiente.
precisa saber é o seguinte
3
@ Marc, eu gosto dos exemplos com letras, isso tornou as coisas muito claras
Muhammad Farag
@Trylks foldRight também pode ser implementado com tailrec
Timothy Kim
@ TimothyKim, com implementações não diretas e otimizadas para isso. Por exemplo, no caso particular das listas Scala , essa maneira consiste em reverter a Listaplicação então foldLeft. Outras coleções podem implementar estratégias diferentes. Em geral, se foldLefte foldRightpode ser usado de forma intercambiável (propriedade associativa do operador aplicado), então foldLefté mais eficiente e preferível.
Trylks
9

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}))
}
Puneeth Reddy V
fonte
9
Este post é quase ilegível. Reduza sentenças, use palavras-chave reais (por exemplo, reduzaLeft em vez de LEFT_REDUCE). Use setas matemáticas reais, tags de código quando estiver lidando com o código. Prefira exemplos de entrada / saída em vez de explicar tudo. Cálculos intermediários dificultam a leitura.
Mikaël Mayer
4

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
raisercostin
fonte