[scala] 축소, 접기 또는 스캔 (왼쪽 / 오른쪽)?

Program / 글쓴이

언제 사용해야한다 reduceLeft, reduceRight, foldLeft, foldRight, scanLeft또는 scanRight?

차이점에 대한 직관 / 개요를 원합니다-간단한 예가 있습니다.

답변

일반적으로 6 개의 모든 접기 기능은 이진 연산자를 컬렉션의 각 요소에 적용합니다. 각 단계의 결과는 다음 단계로 전달됩니다 (이진 연산자의 두 인수 중 하나에 대한 입력으로). 이런 식 으로 결과를 누적 할 수 있습니다.

reduceLeft그리고 reduceRight하나의 결과를 쌓아.

foldLeft및 foldRight시작 값을 사용하는 하나의 결과를 쌓아.

scanLeft및 scanRight시작 값을 사용하여 중간 누적 결과 집합을 쌓아.

축적하다

왼쪽부터 앞으로 …

요소 컬렉션 abc과 이진 연산자를 사용하면 컬렉션의 addLEFT 요소 (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

오른쪽에서 뒤로 …

RIGHT 요소로 시작하고 뒤로 (C에서 A로) 되돌아 가면 이제 이항 연산자에 대한 두 번째 인수가 결과를 누적 함을 알 수 있습니다 (연산자가 동일 함) 인수 이름을 전환하여 역할을 명확하게합니다. ) :

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)

.

누적 해제

왼쪽부터 앞으로 …

대신 경우 우리는했다 드 쌓아 , 우리는 첫 번째 인수를 통해 결과를 쌓아 올린 것 모음의 왼쪽 요소부터 감산에 의해 어떤 결과를 res우리의 이항 연산자의 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)

오른쪽에서 뒤로 …

그러나 지금 xRight 변형을 찾으십시오! xRight 변형의 (계산되지 않은) 값은 이항 연산자 의 두 번째 매개 변수 res로 전달됩니다 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)

마지막 목록 (-2, 3, -1, 4, 0)은 아마도 직관적으로 기대하지 않을 수도 있습니다!

보시다시피, 단순히 scanX를 실행하고 각 단계에서 누적 된 결과를 디버깅하여 foldX가 수행하는 작업을 확인할 수 있습니다.

결론

  • reduceLeft또는 로 결과를 누적합니다 reduceRight.
  • 시작 값이 foldLeft있거나 foldRight시작 값이있는 경우 결과를 누적 합니다.

  • scanLeft또는 로 중간 결과 모음을 누적합니다 scanRight.

  • 당신이 가고 싶은 경우 xLeft 변화를 사용하여 전달 컬렉션을.

  • 컬렉션을 거꾸로 돌아가려면 xRight 변형을 사용하십시오 .

답변

일반적으로 REDUCE, FOLD, SCAN 방법은 LEFT에 데이터를 누적하고 RIGHT 변수를 계속 변경하여 작동합니다. 그들 사이의 주요 차이점은 REDUCE입니다.

접기는 항상 seed사용자 정의 시작 값 과 같은 값으로 시작합니다. 접기가 시드 값을 반환하는 컬렉션이 비어 있으면 Reduce에서 예외가 발생합니다. 항상 단일 값이됩니다.

스캔은 왼쪽 또는 오른쪽 항목의 일부 처리 순서에 사용되며 이후 계산에서 이전 결과를 사용할 수 있습니다. 즉, 항목을 스캔 할 수 있습니다. 항상 컬렉션을 만듭니다.

  • LEFT_REDUCE 메소드는 REDUCE 메소드와 유사하게 작동합니다.

  • RIGHT_REDUCE는 reduceLeft와 반대입니다. 즉, RIGHT에 값을 누적하고 왼쪽 변수를 계속 변경합니다.

  • reduceLeftOption 및 reduceRightOption은 left_reduce와 비슷하며 right_reduce는 OPTION 객체에서 결과를 반환한다는 점만 다릅니다.

아래에 언급 된 코드의 출력 부분은 다음과 같습니다.

사용 scan번호 목록에서 동작을 (사용 seed가격 0)List(-2,-1,0,1,2)

  • {0, -2} =>-2 {-2, -1} =>-3 {-3,0} =>-3 {-3,1} =>-2 {-2,2} => 0 스캔리스트 (0, -2, -3, -3, -2, 0)

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

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

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

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

사용하여 reduce, fold문자열의 목록을 통해 작업을List("A","B","C","D","E")

  • {A, B} => AB {AB, C} => ABC {ABC, D} => ABCD {ABCD, E} => ABCDE 축소 (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

코드 :

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

답변

요소 x0, x1, x2, x3 및 임의의 함수 f가있는 컬렉션 x의 경우 다음이 있습니다.

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

결론적으로

  • scan 처럼 fold 뿐만 아니라 모든 중간 값을 출사
  • reduce 때로는 찾기가 조금 어려운 초기 값이 필요하지 않습니다.
  • fold 찾기가 조금 더 어려운 초기 값이 필요합니다.
    • 합계 0
    • 제품의 경우 1
    • min의 첫 번째 요소 (일부는 Integer.MAX_VALUE를 제안 할 수 있음)
  • 100 % 확실하지는 않지만 다음과 같은 동등한 구현이있는 것처럼 보입니다.
    • 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

답변