разница между foldLeft и reduLeft в Scala - PullRequest
Новая
       73

разница между foldLeft и reduLeft в Scala

183 голосов
/ 14 октября 2011

Я узнал основную разницу между foldLeft и reduceLeft

foldLeft:

  • необходимо передать начальное значение

reduceLeft:

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

Есть ли другая разница?

Есть какая-то конкретная причина иметь два метода с похожей функциональностью?

Ответы [ 7 ]

284 голосов
/ 14 октября 2011

Несколько вещей, о которых стоит упомянуть здесь, прежде чем дать фактический ответ:

  • Ваш вопрос не имеет ничего общего с left, скорее речь идет о разнице между уменьшением и складыванием
  • Разница вовсе не в реализации, просто посмотрите на сигнатуры.
  • Вопрос не имеет никакого отношения, в частности, к Scala, а скорее к двум концепциям функционального программирования.

Возвращаясь к вашему вопросу:

Вот подпись foldLeft (также могла бы быть foldRight для пункта, который я собираюсь сделать): 

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

А вот подпись reduceLeft (опять-таки здесь направление не имеет значения) 

def reduceLeft [B >: A] (f: (B, A) => B): B

Эти два выглядят очень похожими и, таким образом, вызвали путаницу.reduceLeft - это особый случай foldLeft (что, кстати, означает, что вы иногда можете выразить то же самое, используя любой из них).

Когда вы звоните reduceLeftскажем, на List[Int] он буквально сократит весь список целых чисел до одного значения, которое будет иметь тип Int (или супертип Int, следовательно, [B >: A]).

Когда вы вызываете foldLeft скажем, на List[Int] он свернет весь список (представьте, что вы катите лист бумаги) в одно значение, но это значение не обязательно должно быть даже связано с Int (следовательно, [B]).

Вот пример: 

def listWithSum(numbers: List[Int]) = numbers.foldLeft((List[Int](), 0)) {
   (resultingTuple, currentInteger) =>
      (currentInteger :: resultingTuple._1, currentInteger + resultingTuple._2)
}

Этот метод принимает List[Int] и возвращает Tuple2[List[Int], Int] или (List[Int] -> Int).Он вычисляет сумму и возвращает кортеж со списком целых чисел и его суммой.Кстати, список возвращается в обратном порядке, потому что мы использовали foldLeft вместо foldRight.

Watch One Fold, чтобы править ими всеми для более подробного объяснения.

184 голосов
/ 14 октября 2011

reduceLeft - это просто удобный метод. Это эквивалентно 

list.tail.foldLeft(list.head)(_)
43 голосов
/ 14 октября 2011

foldLeft является более общим, вы можете использовать его для создания чего-то совершенно отличного от того, что вы изначально вставили. Принимая во внимание, что reduceLeft может производить только конечный результат того же типа или супертипа типа коллекции.Например: 

List(1,3,5).foldLeft(0) { _ + _ }
List(1,3,5).foldLeft(List[String]()) { (a, b) => b.toString :: a }

foldLeft будет применять замыкание с последним согнутым результатом (первый раз с использованием начального значения) и следующим значением.

reduceLeft, с другой стороны, сначала объединит два значения из списка и применит их к закрытию.Затем он объединит остальные значения с совокупным результатом.См .: 

List(1,3,5).reduceLeft { (a, b) => println("a " + a + ", b " + b); a + b }

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

5 голосов
/ 26 июня 2013

Для справки, reduceLeft выдаст ошибку, если применить к пустому контейнеру со следующей ошибкой. 

java.lang.UnsupportedOperationException: empty.reduceLeft

Переработка кода для использования 

myList foldLeft(List[String]()) {(a,b) => a+b}

является одним из возможных вариантов. Другой вариант заключается в использовании варианта reduceLeftOption, который возвращает результат в параметре. 

myList reduceLeftOption {(a,b) => a+b} match {
  case None    => // handle no result as necessary
  case Some(v) => println(v)
}
5 голосов
/ 14 октября 2011

Основная причина, по которой они оба находятся в стандартной библиотеке Scala, вероятно, заключается в том, что они оба находятся в стандартной библиотеке Haskell (называемой foldl и foldl1).Если бы reduceLeft не было, его часто определяли как удобный метод в разных проектах.

2 голосов
/ 02 февраля 2017

С Принципы функционального программирования в Scala (Мартин Одерский):

Функция reduceLeft определяется в терминах более общей функции, foldLeft.

foldLeft похож на reduceLeft, но принимает в качестве дополнительного параметра аккумулятор z, который возвращается, когда foldLeft вызывается в пустом списке:

(List (x1, ..., xn) foldLeft z)(op) = (...(z op x1) op ...) op x

[в отличие от reduceLeft, который вызывает исключение при вызове в пустом списке.]

Курс (см. Лекцию 5.5) предоставляет абстрактные определенияэти функции, которые иллюстрируют их различия, хотя они очень похожи в использовании сопоставления с образцом и рекурсии. 

abstract class List[T] { ...
  def reduceLeft(op: (T,T)=>T) : T = this match{
    case Nil     => throw new Error("Nil.reduceLeft")
    case x :: xs => (xs foldLeft x)(op)
  }
  def foldLeft[U](z: U)(op: (U,T)=>U): U = this match{
    case Nil     => z
    case x :: xs => (xs foldLeft op(z, x))(op)
  }
}

Обратите внимание, что foldLeft возвращает значение типа U, которое не обязательнотот же тип, что и List[T], но reduLeft возвращает значение того же типа, что и список).

0 голосов
/ 06 июля 2015

Чтобы по-настоящему понять, что вы делаете со сложением / уменьшением, отметьте это: http://wiki.tcl.tk/17983 очень хорошее объяснение.как только вы поймете концепцию сгиба, сокращение придет вместе с ответом выше: list.tail.foldLeft (list.head) (_)

...