Рекурсивным типом данных является тип данных, который может содержать значения того же самого типа. Важнейшими примерами такого типа являются такие динамические типы данных, как списки (List) и деревья (Tree). Списки в Scala фактически являются тоже рекурсивным типом данных. Упрощенно рекурсивное определение списка можно представить как:

sealed trait List[+A]
case object Nil extends List[Nothing]
case class Cons[+A](head: A, tail: List[A]) extends List[A]

где Nil - конструктор, представляющий пустой список, и Cons - конструктор, представляющий непустой список. Рекурсия здесь в том, что tail является тоже списком типа List[A], т.е. здесь может быть как Nil, так и Cons. [1] . Динамическими же они являются потому, что динамические структуры данных могут динамически менять свой размер.

Часто возникает необходимость агрегировать значения в структуре данных с помощью некоторой операции - если провести аналогию с SQL, то это операции типа SUM(), MAX(), MIN(), AVG(), и др. Разумеется, можно обойтись без специальных конструкций, и просто запрограммировать искомую операцию. Например, для нахождения суммы и произведения списка чисел получится что-то вроде:

def sum(ints: List[Int]): Int = ints match {
  case Nil => 0
  case Cons(x,xs) => x + sum(xs)
}

def product(ds: List[Double]): Double = ds match {
  case Nil => 1.0
  case Cons(x, xs) => x * product(xs)
}

К сожалению, налицо явное дублирование. Единственная разница между 2-мя функциями - это обработка ситуации с пустым списком и рекурсивный вызов операции. Явно просматривается схема, которую неплохо было бы обобщить.

Для этого существует функция (на самом деле семейство функций) fold, или “свертка”, состоящая из:

  • комбинирующей функции (функции высшего порядка, которая совершит искомую операцию - сложит два числа, найдет их среднее и т.д.),

  • ссылку на структуру данных (или ее верхний узел),

  • и возможно, некое дефолтное значение.

В процессе fold обойдет все узлы рекурсивной структуры данных, аккумулируя значения - т.е. применяя систематически переданную функцию. В случае списка узлом является значение типа Cons - хотя это уже деталь внутренней реализации. Например, для нахождения суммы списка:

val list = List("1","2","3","4")

нам нужно сделать:

list.fold("z")((b,a) => b+a)

где 0 - это дефолтное значение, а (b,a) => b+a - функция с двумя аргументами, возвращающая их сумму.

Графически fold можно представить в виде дерева. Рассмотрим свертку списка из последнего примера при помощи +. Если представить список в виде дерева, то он будет выглядеть так:

gras

Сверткой (на самом деле левой сверткой) будет f(f(f(f(z, a), b), c), d), т.е. в данном случае ((("z" + "a") + "b") + "c") + "d", которая в результате вернет zabcd и которую можно представить в виде следующего дерева:

gras

Функция fold обойдет весь список, передавая значение каждого элемента в f. Вообще, в f передается 2 параметра, и в случае левой свертки 1-й параметр - это т.н. “аккумулятор”, а второй - очередной элемент. И в случае списка fold на самом деле является foldLeft, т.е. левой сверткой. При левой свертке дерево строится снизу вверх, и последние элементы находятся в вершине. Сигнатура foldLeft выглядит следующим образом:

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

Семейство функций fold являются каррированными функциями.

Еще раз запишем fold уже явно как foldLeft:

list.foldLeft(0)((acc,elem) => acc+elem)

Здесь acc - аккумулятор, а elem - очередной элемент списка. В 1-й итерации, значение аккумулятора будет установлено в дефолтное значение. Во время 2-й, значением аккумулятора будет результат 1-го (т.е. предыдущего) вызова.

Правая свертка же будет выглядеть как f(a, f(b, f(c, f(d, z)))), т.е. в данном случае "a" + ("b" + ("c" + ("d" + "z"))) (т.е. обход, по сути, происходит с конца списка), которая в результате вернет zdcba и которую можно представить в виде:

gras

При правой свертке дерево строится сверху вниз, но вычисления производятся снизу вверх (то есть, нужно рекурсивно спуститься вниз дерева, и уже оттуда производить сложение).

Кстати, именно графическое представление правой и левой сверток подвигнуло Одерского на создание несколько другой, сокращенной формы записи левой и правой сверток - а именно - /: и :\ (см. здесь), где символы соответственно изображают деревья, наклоненные влево и вправо. Т.е., например, foldLeft можно записать как ("z" /: List("a", "b", "c", "d")) (_+_), foldRight - как (List("a", "b", "c", "d") :\ "z") (_+_).

Зачем нам нужен foldRight, например, в случае списка, не достаточно ли иметь один foldLeft? В случае оператора + и последовательности целых чисел, возможно, нет, поскольку в этом случае сложение является коммутативной операцией, но не все операции являются таковыми - например, сложение, т.е. конкатенация строк таковой не является, и порядок операндов имеет значение.

Ну и уже теперь заметно 2 вещи - и в foldLeft, и в foldRight тип результата и аккумулятора (B) может отличаться от типа элементов списка (A). И как видно, передаются они в разном порядке и в том, и другом случае.

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

def foldRight[B](z: B)(op: (A, B) => B): B

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

scala> val list = List("a", "b", "c", "d")
list: List[String] = List(a, b, c, d)
scala> list.foldLeft(List[String]())((b,a) => a :: b)
res5: List[String] = List(d, c, b, a)

Как бы мы реализовали foldRight? В принципе, напрашивается что-то вроде:

override def foldRight[A, B](z: B)(f: (A, B) => B): B = this match {
  case Nil => z
  case (x: A) :: xs => f(x, xs.foldRight(z)(f))
}

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

def foldLeft[A,B](z: B)(f: (B, A) => B): B = {
  this match {
    case Nil => z
    case (x: A) :: xs => foldLeft(f(z, x))(f)
  }
}

В чем здесь проблема? foldLeft обходит список от начала до конца и при каждой итерации сразу производит вычисление, и в конце на выходе мы имеем искомое значение. foldLeft в данном виде является, что называется, tail-recursive, т.е. реализованный с помощью концевой рекурсии. В то же время, foldRight доходит до конца списка, а затем возвращается обратно, производя вычисления. Т.е. в случае рекурсивной реализации, в случае foldRight мы должны сохранить весь стек вызовов и затем развернуть его обратно. В случае больших спиcков, естественно, это закончится StackOverflowError. Для tail-recursive вызовов этого не происходит, поскольку компилятор оптимизирует хвостовую рекурсию таким образом, что она превращается в цикл.

Как же это все реализовано в действительности для списка, во всяком случае, в версии 2.11? В трейте LinearSeqOptimized, который является базовым для Stack, Queue, Stream и List, foldLeft и foldRight определены как:

  def foldLeft[B](z: B)(f: (B, A) => B): B = {
    var acc = z
    var these = this
    while (!these.isEmpty) {
      acc = f(acc, these.head)
      these = these.tail
    }
    acc
  }

  def foldRight[B](z: B)(f: (A, B) => B): B =
    if (this.isEmpty) z
    else f(head, tail.foldRight(z)(f))

Т.е. foldLeft вообще не использует рекурсию, а использует цикл и вызовы head и tail, а foldRight использует опять-таки простую рекурсию. Но в трейте List метод foldRight переопределен как:

override def foldRight[B](z: B)(op: (A, B) => B): B =
  reverse.foldLeft(z)((right, left) => op(left, right))

Т.е., во всяком случае для списков, StackOverflowError у нас уже не будет (кстати, нечто подобное сделано и для Range). Да, у нас есть некоторый оверхед на reverse (O(2N) вместо O(N)), но зато мы можем уже спокойно использовать foldRight для больших списков.

Что касается других применений fold, то, подтверждая аналогию с агрегатными функциями в SQL, приведем аналоги для COUNT(), AVG() и UNIQUE():

def count(list: List[Any]): Int =
  list.foldLeft(0)((sum,_) => sum + 1)

def average(list: List[Double]): Double =
  list.foldLeft(0.0)(_+_) / list.foldLeft(0.0)((r,c) => r+1)

def unique[A](list: List[A]): List[A] =
  list.foldLeft(List[A]()) { (r,c) =>
    if (r.contains(c)) r else c :: r
  }.reverse

count, в принципе, довольно очевиден; average представляет собой комбинацию sum и count; в случае unique мы стартуем с пустым списком, затем аккумулируем новый список, для каждого следующего проверяя каждый следующий элемент, не находится ли он уже в аккумуляторе, и добавляя его, если нет. Затем список необходимо развернуть. Другой вариант - если переписать reverse с использованием foldLeft:

def unique[A](list: List[A]): List[A] =
  list.foldLeft(List[A]()) { (r,c) =>
    if (r.contains(c)) r else c :: r
  }.foldLeft(List[A]())((r,c) => c :: r)

Возникает вопрос, зачем вообще существует отдельный вызов fold, если он фактически идентичен foldLeft. Это, вообще говоря, верно только для List, и у этих 2-ух методов разное предназначение:

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

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

В Scaladoc написано, что в то время как foldLeft применяет бинарный оператор к начальному значению и всем элементам последовательно слева направо, и между типами B (тип начального значения и аккумулятора) и A (тип элементов коллекции) нету непосредственной связи, то случае fold порядок не регламентируется, соотвественно, мы не знаем, в каком порядке будет применен оператор op, т.е. не гарантируется, что аккумулятор будет слева, а элемент справа. Поэтому здесь несколько другие связи между типами - тип A1 оба операнда, и этот же тип имеет результат, причем A должен наследовать A1. Операнды в fold формируют моноид (Если коротко, то моноид - ассоциативная бинарная функция вместе с нейтральным элементом для этой функции. Примеры типичных моноидов - (0)(_+_) или (1)(_*_). fold добавлялся в первую очередь в расчете на параллельные коллекции, т.е. коллекции, где свертку можно делать в параллель, поскольку порядок не имеет значения.

Но если у нас ситуация, когда типы аккумулятора и элементов все же не связаны, но мы хотим использовать fold с его потенциальным параллелизмом, то для этого существует aggregate - в нем есть возможность определить, как именно скомбинировать несвязанные между собой типы A и B - а именно дополнительную операцию combop:

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

Reduce

Что же такое reduce? Сравним для примера сигнатуры foldLeft и reduceLeft:

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

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

reduceLeft является левой сверткой, только более специфичным ее случаем. Очевидно, что в случае reduceLeft коллекция будет “сведена” в одно единственное значение, и тип этого значения должен совпадать с типом элементов. Из реализации reduceLeft

def reduceLeft[B >: A](f: (B, A) => B): B =
  if (isEmpty) throw new UnsupportedOperationException("empty.reduceLeft")
  else tail.foldLeft[B](head)(f)

видно, что фактически reduceLeft есть частный случай foldLeft, но только без дефолтного значения, таким образом, в качестве дефолтного значения используется первый элемент, ну и случай пустого списка вообще запрещен, так как смысла в этом случае не имеет. Хотя для последней ситуации тоже есть лекарство - метод reduceLeftOption, который в случае пустого списка вернет None.

Аналогичным образом reduceRight и reduce тоже являются частными случаями своих fold-собратьев.