Разница в методе Fold и foldLeft

Ответ 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

Чтобы разрешить произвольные древовидные разложения в последовательном списке, у вас должен быть нуль, который ничего не делает (чтобы вы могли добавлять его везде, где вам это нужно в дереве), и вы должны создать то же самое, что вы берете в качестве двоичных аргументов, чтобы типы не изменялись на вас в зависимости от того, как вы разложите дерево.

(Возможность оценить как дерево приятно для распараллеливания. Если вы хотите, чтобы у вас было время для преобразования времени вывода, вам нужен как оператор комбинации, так и стандартный start-value-transforms-sequence-element- to-wish-type, как и у foldLeft. Scala имеет это и называет его aggregate, но в некотором роде это больше похоже на foldLeft, чем fold.)

Ответ 2

Я не знаком с Scala, но библиотека коллекции Scala имеет аналогичный дизайн для Haskell's. Этот ответ основан на 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. Если вы не уважаете это ограничение, вы в конечном итоге добавляете строки в ints! Эта ошибка попадает в систему типов.

Нейтральный элемент может вводиться несколько раз, потому что, как правило, параллельная складка реализуется путем разделения входа и выполнения нескольких последовательных сгибов. Последовательная справка вводит нейтральный элемент один раз. Представьте себе одно конкретное выполнение 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 появляется дважды.

Ответ 3

ПРИМЕЧАНИЕ. Я мог быть совершенно неправ. Мой scala менее совершенен.

Я думаю, что разница заключается в сигнатуре методов:

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

против

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

Короче говоря, fold определяется как работающий на некотором типе A1, который является супертипом типа массива, который для вашего строкового массива компилятор определяет как "Any" (вероятно, потому, что ему нужен тип, который может хранить вашу String или что метод объединителя для сброса Fold принимает два параметра одного и того же типа?) То же, что означает документация, когда речь идет о z, реализация Fold может быть такой, что она объединяет ваши входы параллельно, например:

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

С другой стороны, foldLeft работает с типом B (без ограничений) и только просит, чтобы вы предоставили метод объединения, который принимает параметр типа B и другой тип вашего массива (String в вашем случае) и производит B.

Ответ 4

Ошибка.. Вы получаете ошибку времени компиляции, потому что подпись fold позволяет только складывать значения типа, который является супертипом типа значений в коллекции, и только супертип String (ваш тип коллекции) и Int (тип вашего нулевого элемента) Any. Таким образом, тип результата сгиба определяется как Any - и Any не имеет метода toInt.

Обратите внимание, что две версии fold имеют разные подписи:

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

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

Почему у них разные подписи? Это связано с тем, что fold может быть реализовано параллельно, как в случае с параллельными коллекциями. Когда несколько процессоров сбрасывают значения в коллекциях, каждый из процессоров принимает подмножество элементов типа A и производит сложенное значение типа A1, последовательно применяя op. Результаты, полученные этими процессорами, должны быть объединены вместе в окончательное значение складывания - это делается с помощью функции op, которая делает именно это.

Теперь обратите внимание, что это невозможно сделать с помощью f в foldLeft, потому что каждый из процессоров производит сложенное значение типа B. Несколько значений типа B нельзя комбинировать с помощью f, потому что f объединяет значение B с другим значением типа A - между типами A и B не существует соответствия.

Пример. В вашем примере предположим, что 1-й процессор принимает элементы "1", "2", а второй принимает элемент "3". Первый будет производить сложенное значение 3, а второе будет производить другое сложенное значение 3. Теперь они должны объединить свои результаты, чтобы получить окончательное свернутое значение - это невозможно, потому что закрытие _ + _.toInt знает, как объединить значения Int и String, а не 2 Int.

В ситуациях, когда эти типы отличаются, используйте aggregate, в котором вы должны определить, как объединить два значения типа B:

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

combop выше определяет, как сделать последний шаг, когда результат сгиба и элементы в коллекции имеют разные типы.

Нейтральный элемент. Как описано выше, несколько процессоров могут сгибать подмножества элементов в коллекции. Каждый из них начнет сворачивать значение, добавив нейтральный элемент.

В следующем примере:

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

всегда возвращает 10 = 4 + 1 + 2 + 3.

Однако 4 не следует использовать с fold, поскольку он не является нейтральным элементом:

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

Вышеуказанное может возвращать (4 + 1 + 2) + (4 + 3) = 14 или (4 + 1) + (4 + 2) + (4 + 3) = 18. Если вы не используете нейтральный элемент для fold, результаты являются недетерминированными. Точно так же вы можете использовать Nil как нейтральный элемент, но не непустой список.

Ответ 5

Общая разность

Вот прототипы методов

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

Итак, для сложения результат имеет тип A1 >: A вместо любого B. Более того, как указано в документе, для fold порядок не

О вашей ошибке

При вводе scala> Array("1","2","3").fold(0)(_ + _.toInt) вы предполагаете, что 0, int является подтипом String. Вот почему компилятор выдает ошибку.

О странном z в складке

Здесь мы должны увидеть реализацию fold, чтобы понять, что происходит. Вот что мы получаем:

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

В принципе, fold представляет собой реализацию foldleft с ограничением на тип вывода. Теперь мы можем видеть, что z на практике будет использоваться так же, как в foldleft. Поэтому мы можем просто заключить, что этот комментарий был сделан, потому что ничто не гарантирует такого поведения в будущих реализациях. Мы уже видим это сейчас, parallels:

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

Ответ 6

Как следует из другого ответа, метод fold предназначен, прежде всего, для поддержки параллельного сгиба. Вы можете видеть это следующим образом. Сначала мы можем определить своего рода оболочку для целых чисел, которая позволяет нам отслеживать операции, которые были выполнены в его экземплярах.

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

Далее мы можем создать параллельный набор этих вещей и элемент идентификации:

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

Сначала попробуем foldLeft:

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

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

Итак, наше нулевое значение используется только один раз, как и следовало ожидать, поскольку foldLeft выполняет последовательную складку. Затем мы можем очистить журнал и попробовать 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)

Итак, мы видим, что сгиб распараллелен таким образом, что нулевое значение используется несколько раз. Если мы запустим это снова, мы, вероятно, увидим разные значения в журнале.

Ответ 7

Было упомянуто, но без примера: если вы хотите разрешить параллелизм для разных типов данных для вывода и ввода, вы можете использовать aggregate:

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

Первая функция вызывается первой. Его результаты затем уменьшаются с помощью второй функции. См. Объяснение агрегатной функции scala.