Статьи

Секретные силы foldLeft () в Scala

Январь 4, 2019

Метод foldLeft (), доступный для всех коллекций в Scala, позволяет заданной функции с двумя аргументами работать с последовательными элементами этой коллекции, где результат этой функции передается в качестве первого аргумента в следующем вызове. Второй аргумент — это всегда текущий элемент в коллекции. Звучит не очень обнадеживающе, но, как мы скоро увидим, есть несколько вариантов использования, ожидающих своего открытия

Прежде чем мы углубимся в foldLeft, давайте взглянем на упрощенную версию foldLeft. Я всегда считал, что рабочий код стоит тысячи слов :

val input = List(3, 5, 7, 11)
input.reduce((total, cur) => total + cur)

или более читаемый:  

def op(total: Int, cur: Int) = total + cur
 
input reduce op

Результат 26 (сумма). Код более-менее читабелен: для сокращения метода мы передаем 2-аргументную функцию op (operation). Оба параметра этой функции (и ее возвращаемое значение) должны иметь тот же тип, что и коллекция. Reduce () вызовет эту операцию для двух первых элементов коллекции:  

op(3, 5)  //8

Результат (8) передается в качестве первого аргумента последующему вызову операции op, где вторым аргументом является следующий элемент коллекции:  

op(8, 7)  //15

и наконец:  

op(15, 11)  //26

С логической точки зрения была вызвана следующая составная операция:  

op(op(op(3, 5), 7), 11)

Когда мы понимаем, что op () является в основном дополнением:

(((3 + 5) + 7) + 11)

Пока все хорошо — Reduce () сводит коллекцию данного типа к одному значению того же типа. Примеры вариантов использования включают сложение чисел, объединение последовательности строк и т. Д .:  

List("Foo", "Bar", "Buzz").reduce(_ + _)

Обратите внимание на сокращенное обозначение блока кода без указания параметров: _ + _. Очевидно, мы не ограничены оператором сложения:  

def factorial(x: Int) = (2 to x).reduce(_ * _)

Стоит упомянуть два особых случая: когда в коллекции есть только один элемент, lower () возвращает именно этот элемент. Когда оно пустое, limit () выдаст исключение. Посмотрим правде в глаза, как правило, мы реализуем факториал в первый (и последний) раз где-то в начале университета и сложить числа у нас есть удобный метод:  

input.sum

Кроме того, проблема с пустыми коллекциями немного болезненна — ведь сумма пустого набора чисел интуитивно равна 0, а конкатенация пустого набора строк — это … пустая строка. Вот куда входит foldLeft () с возможностью указать начальное значение:  

input.foldLeft(0)(op)

В этом случае сначала вызывается функция op () с начальным значением 0 в качестве первого аргумента и с первым элементом коллекции:  

op(0, 3)

Последующие итерации остаются прежними. Если коллекция пуста, foldLeft () возвращает начальное значение. Грустно, сколько учебников останавливаются прямо здесь. В конце концов, мы можем просто добавить начальное значение к списку ввода и с радостью использовать redu ():  

(0 :: input).reduce(op)
(0 :: Nil).reduce(op)  //empty list is prepended by 0

Хуже того, многие предлагают «упрощенный» синтаксис foldLeft (), я сомневаюсь, что он что-то упрощает:  

(0 /: input)(op)

Это эквивалентно input.foldLeft (0) (op), но предназначено для людей, которые любят Perl. Итак, закрывая этот путь слишком длинным введением, давайте посмотрим на истинную мощь за foldLeft ().

Предположим, что у нас есть объект типа [T], для которого мы хотели бы выполнить набор преобразований. Преобразование — это не что иное, как функция, которая принимает и возвращает объект типа [T]. Мы можем вернуть тот же экземпляр (без преобразования), обернуть оригинальный объект ( шаблон Decorator ) или изменить его.

Нетрудно представить, что порядок преобразований важен. Например, давайте используем обычную строку и набор преобразований, представленных функциями String => String:  

val reverse = (s: String) => s.reverse
 
val toUpper = (s: String) => s.toUpperCase
 
val appendBar = (s: String) => s + "bar"

Вспоминая, что результат первого преобразования является аргументом второго, мы можем сказать:  

appendBar(toUpper(reverse("foo")))  //OOFbar
toUpper(reverse(appendBar("foo")))  //RABOOF

Я думаю, что это очевидно. К сожалению, нам нужен метод, принимающий произвольный (возможно пустой или динамически создаваемый) список преобразований для применения:  

def applyTransformations(initial: String, transformations: Seq[String => String]) = //???
 
applyTransformations("foo", List(reverse, toUpper, appendBar))
applyTransformations("foo", List(appendBar, reverse, toUpper))
applyTransformations("foo", List.fill(7)(appendBar))

Последняя строка выполняет преобразование appendBar 7 раз для начального значения «foo». Как реализовать метод applyTransformations? Программист с очень важным опытом, вероятно, придумал бы что-то вроде этого:  

def applyTransformations(initial: String, transformations: Seq[String => String]) = {
 var cur = initial
 for(transformation <- transformations) {
  cur = transformation(cur)
 }
 cur
}

Скучный цикл по всем преобразованиям, промежуточный результат сохраняется в переменной. Эта реализация имеет несколько недостатков. Во-первых, крайне важно (!) Scala пытается охватить парадигму функционального программирования, и этот код кажется очень низкоуровневым. Наш второй подход гораздо более идиоматичен в отношении Scala — мы используем рекурсию и сопоставление с образцом:  

@tailrec
def applyTransformations(initial: String, transformations: Seq[String => String]): String =
    transformations match {
        case head :: tail => applyTransformations(head(initial), tail)
        case Nil => initial
    }

Немного сложнее понять по сравнению с императивным решением. Если список преобразований пуст — вернуть текущее значение. Если это не так, примените первое преобразование (head (initial)) и рекурсивно назовите себя с остальными преобразованиями (tail).

Оказывается, эта проблема может быть реализована намного, намного более кратко, без явных циклов и рекурсии. Заметили ли вы, как проблема с вложенными преобразованиями (appendBar (toUpper (reverse («foo»)))) аналогична тому, как работает foldLeft () (op (op (op (3, 5), 7), 11)) ?  

def applyTransformations(initial: String, transformations: Seq[String => String]) =
    transformations.foldLeft(initial) {
        (cur, transformation) => transformation(cur)
    }

 Понимание того, как работает приведенный выше код, требует немного времени, но впоследствии это действительно полезно. Также это позволяет полностью понять всю силу foldLeft (). Прежде чем идти дальше, постарайтесь понять это самостоятельно. Несколько советов:

  • Тип результата foldLeft () [B] не обязательно должен совпадать с типом коллекции [A]. Это тип начального значения. В нашем примере входная коллекция содержит функции, но начальное значение — String.
  • Функция, переданная в качестве аргумента для foldLeft (), не должна принимать оба аргумента типа [A] и возвращать этот тип, как это было в случае с Reduce (). На самом деле подпись foldLeft () выглядит следующим образом: 
    def foldLeft[B](initial: B)(op: (B, A) => B): B
  • Значение, возвращаемое функцией op, должно быть того же типа, что и первый аргумент. Также весь вызов foldLeft () будет иметь одинаковый тип.

 Давайте подумаем об этом: тип первого аргумента op () совместим с начальным значением (initial: B), потому что на первой итерации это начальное значение, которое передается как первый аргумент op. Второй аргумент — это первый элемент входной коллекции типа [A]. Во второй итерации результат вызова op () (типа [B]) передается как первый аргумент последующего вызова op. На этот раз второй элемент входной коллекции используется в качестве второго аргумента. И это продолжается до тех пор, пока не достигнет конца коллекции.

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

List(reverse, toUpper, appendBar).foldLeft("foo") {
    (cur, transformation) => transformation(cur)
}

Последующие итерации (псевдокод):  

val initial = "foo"
val temp1 = (initial, reverse) => reverse(initial)
val temp2 = (temp1, toUpper) => toUpper(temp1)
val temp3 = (temp2, appendBar) => appendBar(temp2)

И после встраивания временных переменных: 

val initial = "foo"
appendBar(toUpper(reverse(initial)))

 

Разве это не тот результат, которого мы так долго ждали? Как выясняется, метод foldLeft () полезен не только тогда, когда нам нужно уменьшить (агрегировать) коллекцию до одного значения, например, сложить числа — на самом деле, в этом случае лучше всего использовать Redu () или Sum (). foldLeft (), кажется, отлично подходит, когда нам нужно перебрать произвольную коллекцию, но каждая итерация требует своего рода результата из предыдущей. Кстати, это причина, почему операции складывания и уменьшения не могут выполняться параллельно.

В комментариях к оригинальной статье Цезарий Бартошук предложил альтернативный способ использования foldLeft () в этой задаче:  

def composeAll[A](ts: Seq[A => A]): A => A = ts.foldLeft(identity[A] _)(_ compose _)
 
def applyTransformations(init: String, ts: Seq[String => String]): String = composeAll(ts.reverse)(init)

Если это решение вам не понятно, еще раз несколько советов. Прежде всего, идентичность [A] _ — это функция идентичности, которая всегда возвращает аргумент без изменений. Во-вторых, val компонент = appendBar compose toUpper эквивалентен:

val composed = (s: String) => appendBar(toUpper(s))

 Итак, еще один математический термин: состав функции .


Это был перевод моей статьи
«Ukryta potęga foldLeft ()», первоначально опубликованной на
scala.net.pl .

190
Share: