Scan

Иногда возникает необходимость не просто, например, посчитать сумму всех элементов, а накопить еще при этом все промежуточные результаты. Например, посчитать последовательность Фибоначчи (1, 1, 2, 4, 7, 11...). Теоретически, это можно сделать с помощью foldLeft:

(0 until 6).foldLeft(List(1)){ (l,i) => (l.head + i) :: l }.reverse

Но есть более “прямой” путь - scan.

Немного теории. Возьмем, например, последовательность треугольных чисел (-е треугольное число — это сумма первых натуральных чисел):

входной список 1 2 3 4 5 6 ...
промежуточные суммы 1 3 6 10 15 21 ...


Префиксной суммой (prefix sum) последовательности чисел называется другая последовательность чисел , состоящая из промежуточных сумм чисел входной последовательности:

$$ y_0 = x_0 $$ $$ y_1 = x_0 + x_1 $$ $$ y_2 = x_0 + x_1+ x_2 $$

Частным случаем префиксных сумм натуральных чисел являются вышеприведенные треугольные числа.

В функциональном программировании, префиксная сумма может быть обобщена для любого оператора - не только сложения; результирующая функция высшего порядка называется scan, и она тесно связана со сверткой. И scan, и fold применяют некоторую бинарную операцию к последовательности значений, но scan возвращает последовательность результатов каждой операции, в то время как fold возвращает только конечный результат. Например, последовательность факториалов натуральных чисел

входной список 1 2 3 4 5 6 ...
промежуточные произведения 1 2 6 24 120 720 ...

может быть получена с помощью операции scan и функции, умножающей два числа:

scala> List(1,2,3,4,5,6).scanLeft(1)(_ * _)
res0: List[Int] = List(1, 1, 2, 6, 24, 120, 720)

В Scala, как и в случае с fold, есть 3 версии scan: scanLeft, scanRight и scan. В принципе, scanLeft можно записать через foldLeft - со списком в качестве аккумулятора и вызовом reverse в конце:

def scanLeft[a,b](xs:Iterable[a])(s:b)(f : (b,a) => b) =
  xs.foldLeft(List(s))( (acc,x) => f(acc(0), x) :: acc).reverse

Ну и, конечно, можно отвлечься от сверток, и достичь того же самого эффекта, если использовать map с введением переменной gras:

scala> List(1,2,3,4,5,6).map{var p = 1; x => {p *= x; p}}
res1: List[Int] = List(1, 2, 6, 24, 120, 720)

Композиция трансформаций - конвейер

Конвейер в терминологии UNIX — некоторое множество процессов, для которых выполнено следующее перенаправление ввода-вывода: то, что выводит на поток стандартного вывода предыдущий процесс, попадает в поток стандартного ввода следующего процесса. Т.е. фактически это набор трансформаций над потоком данных. Эту модель, разумеется, можно использовать для разных видов данных, необязательно только для ввода-вывода и только в контексте процессов. Для простоты представим, что мы работаем со строками. Трансформация - это функция, трансформирующая некий String в другой String, т.е. String => String. И мы хотим последовательно применить некторый динамический набор трансформаций в определенном порядке, т.е. нечто вроде:

def applyTransformations(initial: String, transformations: Seq[String => String])

И приведем примеры таких трансформаций:

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

Т.е. в финале набор трансформаций должен превратиться в что-то вроде (appendBar(toUpper(reverse("foo")))), что очень напоминает уже приведенный псевдокод свертки из предыдущей части - f(f(f(f(z, a), b), c), d). И действительно, записать это с помощью foldLeft совсем несложно:

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