Свертка списка

В программировании свёртка (англ. folding, также известна как reduce и accumulate) — функция высшего порядка, которая производит преобразование структуры данных к единственному атомарному значению при помощи заданной функции. Операция свёртки часто используется в функциональном программировании при обработке списков.

Свёртка может быть обобщена на произвольный алгебраический тип данных при помощи понятия «катаморфизм» из теории категорий.

Описание

Функция свёртки обычно принимает три аргумента: комбинирующую функцию f, начальное значение start и структуру данных seq (далее будет рассматриваться только свёртка списков). Иногда функция свёртки не принимает начальное значение, но требует непустого списка. Рассмотрим этот, немного упрощённый вариант.

Пусть требуется найти сумму чисел списка (1 2 3 4 5). Для этого нужно вычислить значение выражения $1 + 2 + 3 + 4 + 5$ . Так как сложение является ассоциативным, порядок вычисления данного выражения не влияет на результат. Однако для произвольной бинарной комбинирующей функции порядок вычисления может иметь значение. Таким образом, для однозначного вычисления выражения требуется задать порядок вычислений. Можно применять комбинирующую функцию к первому элементу списка и результату рекурсивной обработки хвоста списка. В нашем примере получим: $1 + (2 + (3 + (4 + 5)))$ . В данном случае первое применение комбинирующей функции выполняется на двух последних элементах списка и двигается справа налево, поэтому такую свёртку называют правоассоциативной.

Можно применять комбинирующую функцию к результату рекурсивной обработки начала списка (весь список без последнего элемента) и последнему элементу. Тогда будем вычислять $(((1 + 2) + 3) + 4) + 5$ . Такую свёртку называют левоассоциативной.

На практике часто бывает нужным задать так называемое начальное значение, которое будет использовано при первом применении комбинирующей функции. В нашем примере можно выбрать 0 в качестве начального значения. Тогда получим $1 + (2 + (3 + (4 + (5 + 0))))$ при правоассоциативной свёртки и $((((0 + 1) + 2) + 3) + 4) + 5$ при левоассоциативной свёртке.

Пусть список seq является следующим: (elem_1 elem_2 ... elem_n). Функция левоассоциативной свёртки вычислит значение выражения:

(f ... (f (f start elem_1) elem_2) ... elem_n)

а правоассоциативная:

(f (f ... (f start elem_n) ... elem_2) elem_1)

Реализация

foldl, а правоассоциативная — foldr. Но их можно определить и следующим образом:

foldl :: (b -> a -> b) -> b -> [a] -> b
foldl _ v [] = v
foldl f v (x:xs) = foldl f (f v x) xs

Lisp и

(define (foldl f start seq)
  (if (null? seq)
      start
      (foldl f (f start (car seq)) (cdr seq))))

# Функция для расчета факториала числа с помощью свертки списка
def fact(num)
  (2 .. num.to_i).inject( 1 ) { |res, val| res * val}
end

# Поиск минимального элемента в списке с помощью свертки списка
use List::Util qw(reduce);
my $elems_sum = reduce { $a < $b ? $a : $b } (1..100);

Примеры

Факториал n можно представить как свертку списка, состоящего из чисел от 2 до n при помощи операции умножения:

fac n = foldl (*) 1 [2..n]

Здесь:
fac — объявление функции факториала
n — входной параметр
после знака = (равно) идёт определение функции.
foldl — функция свёртки
1 — начальное значение для свёртки
[2..n] — задаётся список по которому следует делать свёртку — массив элементов от 2х до n

Пример программы на языке

object Main {
  def main(args: Array[String]) {
    try {
      val elems = args map Integer.parseInt
      println("Сумма аргументов: " + elems.foldRight(0) (_ + _))
    } catch {
      case e: NumberFormatException => 
        println("Ошибка в аргументах. Использовать следует так: scala Main <число1> <число2> ... ")
    }
  }
}

С помощью метода map перебираются все аргументы. Все они преобразовываются в целое число методом Integer.parseInt и добавляются в список (массив) elems. Затем с помощью метода свёртки списка foldRight вычисляется сумма элементов.

Ссылки

Wikimedia Foundation. 2010.

Словари и энциклопедии на Академике

Свертка списка

Содержание

Описание

Реализация

Lisp и
(define (foldl f start seq) (if (null? seq) start (foldl f (f start (car seq)) (cdr seq))))

# Функция для расчета факториала числа с помощью свертки списка def fact(num) (2 .. num.to_i).inject( 1 ) { |res, val| res * val} end

# Поиск минимального элемента в списке с помощью свертки списка use List::Util qw(reduce); my $elems_sum = reduce { $a < $b ? $a : $b } (1..100);

Примеры

Ссылки

Полезное

Смотреть что такое "Свертка списка" в других словарях:

Поделиться ссылкой на выделенное

Словари и энциклопедии на Академике

Википедия

Свертка списка

Содержание

Описание

Реализация

Lisp и (define (foldl f start seq) (if (null? seq) start (foldl f (f start (car seq)) (cdr seq))))

# Функция для расчета факториала числа с помощью свертки списка def fact(num) (2 .. num.to_i).inject( 1 ) { |res, val| res * val} end

# Поиск минимального элемента в списке с помощью свертки списка use List::Util qw(reduce); my $elems_sum = reduce { $a < $b ? $a : $b } (1..100);

Примеры

Ссылки

Полезное

Смотреть что такое "Свертка списка" в других словарях:

Поделиться ссылкой на выделенное

Прямая ссылка:

Lisp и
(define (foldl f start seq) (if (null? seq) start (foldl f (f start (car seq)) (cdr seq))))