Fold 및 foldLeft 메서드 차이

Fold 및 foldLeft 메서드 차이

---

나는 차이점이 무엇인지 잘 모르겠습니다 fold와 foldLeft스칼라가.

질문의 배와 foldLeft 또는 foldRight의 차이? 주문에 대한 답변이 있습니다. 이해할 만합니다. 하지만 여전히 이것이 작동하는 이유를 이해하지 못합니다 (REPL에서).

scala> Array("1","2","3").foldLeft(0)(_ + _.toInt)
res6: Int = 6

그러나 이것은 그렇지 않습니다 :

scala> Array("1","2","3").fold(0)(_ + _.toInt)
<console>:8: error: value toInt is not a member of Any
              Array("1","2","3").fold(0)(_ + _.toInt)
                                               ^

이 오류 메시지는 무엇을 의미합니까?

문서의이 줄도 나에게 혼란 스럽습니다.

z- 접기 작업을위한 중립 요소; 결과에 임의의 횟수를 추가 할 수 있으며 결과를 변경해서는 안됩니다 (예 : 목록 연결의 경우 Nil, 더하기의 경우 0, 곱의 경우 1).

임의의 횟수 로 추가 되는 이유는 무엇 입니까? 접기가 다르게 작동한다고 생각했습니다.

---

Scala에서 정의한대로 foldLeft는 선형 연산이고 fold트리 연산이 될 수 있습니다. 예를 들면 :

List(1,2,3,4,5).foldLeft(0)(_ + _)
// This is the only valid order of operations
0+1 = 1
      1+2 = 3
            3+3 = 6
                  6+4 = 10
                        10 + 5 = 15
                                 15  // done

List(1,2,3,4,5).fold(0)(_ + _)
// This is valid
0+1 = 1             0+3 = 3           0+5 = 5
      1+2 = 3             3+4 = 7           5
            3         +         7=10        5
                                  10    +   5 = 15
                                                15  // done

순차 목록의 임의의 트리 분해를 허용하려면 아무 작업도 수행하지 않는 0이 있어야하며 (따라서 트리에서 필요할 때마다 추가 할 수 있습니다) 다음과 같은 종류의 것을 만들어야합니다. 이진 인수를 사용하면 트리를 분해하는 방법에 따라 유형이 변경되지 않습니다.

(트리로 평가할 수 있다는 것은 병렬화에 좋습니다. 진행하면서 출력 시간을 변환 할 수 있으려면 조합 연산자 와 표준 시작 값 변환 시퀀스 요소를 원하는대로 변환해야합니다. -유형 함수 foldLeft는 has 와 같습니다 . Scala는 이것을 가지고 있고 그것을 호출 aggregate하지만 어떤면에서는 이것은 실제 foldLeft보다 더 비슷 fold합니다.)

---

저는 Scala에 익숙하지 않지만 Scala의 컬렉션 라이브러리는 Haskell과 비슷한 디자인을 가지고 있습니다. 이 답변은 Haskell을 기반으로하며 Scala에서도 정확할 것입니다.

foldLeft입력을 왼쪽에서 오른쪽으로 처리 하기 때문에 다른 입력 및 출력 유형을 가질 수 있습니다. 반면 fold에 다양한 순서로 입력을 처리 할 수 ​​있으므로 입력과 출력이 모두 동일한 유형을 가져야합니다. 접기 표현식을 확장하면 가장 쉽게 볼 수 있습니다. foldLeft특정 순서로 작동합니다.

Array("1","2","3").foldLeft(0)(_ + _.toInt)
= ((0 + "1".toInt) + "2".toInt) + "3".toInt

배열 요소는 결합 함수의 첫 번째 매개 변수로 사용되지 않습니다. 항상 오른쪽에 나타납니다 +.

fold특정 주문을 보장하지 않습니다. 다음과 같은 다양한 작업을 수행 할 수 있습니다.

Array("1","2","3").fold(0)(_ + _.toInt)
=  ((0 + "1".toInt) + "2".toInt) + "3".toInt
or (0 + "1".toInt) + ("2" + "3".toInt).toInt
or "1" + ("2" + ("3" + 0.toInt).toInt).toInt

배열 요소는 결합 함수의 매개 변수 중 하나에 나타날 수 있습니다. 그러나 결합 함수는 첫 번째 인수가 int가 될 것으로 예상합니다. 이 제약 조건을 준수하지 않으면 결국 문자열을 int에 추가하게됩니다! 이 오류는 유형 시스템에서 발견됩니다.

중립 요소는 일반적으로 입력을 분할하고 여러 개의 순차적 폴드를 실행하여 병렬 폴드가 구현되기 때문에 여러 번 도입 될 수 있습니다. 순차 접기는 중립 요소를 한 번 소개합니다. Array(1,2,3,4).fold(0)(_ + _)어레이가 두 개의 개별 어레이로 분할되고 두 개의 스레드에서 순차적으로 접히는 특정 실행을 상상해보십시오 . (물론 실제 fold함수는 배열을 여러 배열로 뱉어 내지 않습니다.) 하나의 스레드가을 실행 Array(1,2).fold(0)(_ + _)하고 0 + 1 + 2. 다른 스레드 Array(3,4).fold(0)(_ + _)는 컴퓨팅을 실행 0 + 3 + 4합니다. 마지막으로 두 스레드의 부분 합계가 더해집니다. 중립 요소 0는 두 번 나타납니다.

---

참고 : 여기서 완전히 틀릴 수 있습니다. 내 스칼라는 완벽하지 않습니다.

차이점은 방법의 서명에 있다고 생각합니다.

def fold[A1 >: A](z: A1)(op: (A1, A1) ⇒ A1): A1

vs

def foldLeft[B](z: B)(op: (B, T) ⇒ B): B

간단히 말해서, fold는 배열 유형의 상위 유형 인 A1 유형에서 작동하는 것으로 정의되며, 이는 문자열 배열에 대해 컴파일러가 "Any"로 정의합니다 (아마도 String 또는 정수를 저장할 수있는 유형이 필요하기 때문일 것입니다). fold Fold에 전달 된 결합기 메서드는 동일한 유형의 두 매개 변수를 사용합니까?) 그것은 또한 문서가 z에 대해 말할 때 의미하는 바입니다. 예를 들어 Fold의 구현은 입력을 병렬로 결합 할 수 있습니다.

"1" + "2" --\
             --> 3 + 3 -> 6
"3" + *z* --/

반면에 foldLeft는 B 유형 (제한되지 않음)에서 작동하며 B 유형의 매개 변수와 다른 배열 유형 (귀하의 경우 String)을 취하고 B를 생성하는 결합기 메소드 만 제공하도록 요청합니다.

---

The error. You are getting a compile-time error because the signature of fold only allows folding values of type which is the supertype of the type of the values in the collection, and the only supertype of String (your collection type) and Int (the type of your provided zero element) is Any. So, the type of the fold result is inferred to be Any - and Any does not have a method toInt.

Note that the two versions of fold have different signatures:

fold[A1 >: A](z: A1)(op: (A1, A1) => A1): A1

foldLeft[B](z: B)(f: (B, A) => B): B

Why do they have different signatures? This is because fold could be implemented in parallel, as is the case with parallel collections. When multiple processors fold over the values in the collections, each one of the processors takes a subset of elements of type A and produces the folded value of type A1, by consecutively applying op. The results produced by those processors must be combined together into a final folding value - this is done using the op function, which does exactly that.

Now, note that this cannot be done using the f in foldLeft, because each of the processors produces a folded value of type B. Several values of type B cannot be combined using f, because f only combines value B with another value of type A - there is no correspondance between types A and B.

Example. In your example, assume the 1st processor takes elements "1", "2" and the 2nd takes element "3". The first one will produce the folded value 3, and the second will produce another folded value 3. Now they have to combine their results to get the final folded value - this is impossible, because the closure _ + _.toInt only knows how to combine an Int and String, and not 2 Int values.

For situations where these types differ, use aggregate, in which you have to define how to combine two values of type B:

def aggregate[B](z: B)(seqop: (B, A) => B, combop: (B, B) => B): B

The combop above defines how to do the final step when the fold result and the elements in the collection have different types.

The neutral element. As described above, multiple processors may fold over subsets of elements in the collection. Each one of them will start its folded value by adding the neutral element.

In the following example:

List(1, 2, 3).foldLeft(4)(_ + _)

always returns 10 = 4 + 1 + 2 + 3.

However, 4 should not be used with fold, as it is not a neutral element:

List(1, 2, 3).fold(4)(_ + _)

The above may return (4 + 1 + 2) + (4 + 3) = 14 or (4 + 1) + (4 + 2) + (4 + 3) = 18. If you don't use the neutral element for the fold, the results are nondeterministic. In the same way, you can use the Nil as a neutral element, but not a non-empty list.

---

As another answer points out, the fold method is primarily there to support a parallel fold. You can see this as follows. First we can define a kind of wrapper for integers that allows us to keep track of the operations that have been performed on its instances.

case class TrackInt(v: Int) {
  val log = collection.mutable.Buffer.empty[Int]
  def plus(that: TrackInt) = {
    this.log += that.v
    that.log += this.v
    new TrackInt(this.v + that.v)
  }
}

Next we can create a parallel collection of these things and an identity element:

val xs = (1 to 10).map(TrackInt(_)).par
val zero = TrackInt(0)

First we'll try foldLeft:

scala> xs.foldLeft(zero)(_ plus _)
res0: TrackInt = TrackInt(55)

scala> zero.log
res1: scala.collection.mutable.Buffer[Int] = ArrayBuffer(1)

So our zero value is only used once, as we'd expect, since foldLeft performs a sequential fold. Next we can clear the log and try fold:

scala> zero.log.clear()

scala> xs.fold(zero)(_ plus _)
res2: TrackInt = TrackInt(55)

scala> zero.log
res3: scala.collection.mutable.Buffer[Int] = ArrayBuffer(1, 6, 2, 7, 8)

So we can see that the fold has been parallelized in such a way that the zero value is used multiple times. If we ran this again we'd be likely to see different values in the log.

---

General difference

Here are the prototypes of the methods

fold[A1 >: A](z: A1)(op: (A1, A1) ⇒ A1): A1
foldLeft[B](z: B)(f: (B, A) ⇒ B): B

So, for fold the result is of type A1 >: Ainstead of any B. Moreover, as specified in the doc, for fold the order is not

About your error

When typing scala> Array("1","2","3").fold(0)(_ + _.toInt) you assume that 0, an int is a subtype of String. This is why the compiler throws an error.

About the weird z in fold

Here we have to see the implementation of fold to understand what happens. Here is what we get:

def fold[A1 >: A](z: A1)(op: (A1, A1) => A1): A1 = foldLeft(z)(op)

So basically, fold is an implementation of foldleft with a constraint on the output type. We can now see that z will in practice be used the same way as in foldleft. So we can just conclude that this comment was made because nothing assures that behavior in future implementations. We can already see it now, with parallels:

def fold[U >: T](z: U)(op: (U, U) => U): U = {
  executeAndWaitResult(new Fold(z, op, splitter))
}

---

It has been mentioned, but without example: If you want to allow parallelism with different data types for output and input, you could use aggregate:

Array("1","2","3").aggregate(0)(_ + _.toInt, _ + _)

The first function gets called first. Its results are then reduced with the second function. See Explanation of the aggregate scala function.

ReferenceURL : https://stackoverflow.com/questions/11319111/fold-and-foldleft-method-difference