Карта (функция высшего порядка)

Информацию об абстрактном типе данных с тем же именем см. в разделе Карта (структура данных) .

Во многих языках программирования карта — это функция высшего порядка , которая применяет заданную функцию к каждому элементу коллекции , например списку или множеству , возвращая результаты в коллекцию того же типа. Его часто называют «применить ко всем», если рассматривать его в функциональной форме .

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

Примеры: сопоставление списка

Предположим, у нас есть список целых чисел [1, 2, 3, 4, 5] и хотел бы вычислить квадрат каждого целого числа. Для этого сначала определим функцию square одно число (показанное здесь в Haskell ):

square x = x * x

После этого мы можем позвонить

>>> map square [1, 2, 3, 4, 5]

что дает [1, 4, 9, 16, 25], демонстрируя, что map просмотрел весь список и применил функцию square каждому элементу.

Визуальный пример

Ниже вы можете увидеть каждый шаг процесса сопоставления списка целых чисел. X = [0, 5, 8, 3, 2, 1] что мы хотим сопоставить с новым списком X' согласно функции $f(x)=x+1$ :

Просмотр этапов обработки при применении функции карты в списке

The map предоставляется как часть базовой прелюдии Haskell (т.е. «стандартной библиотеки») и реализуется как:

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

Обобщение

См. Также: Теория функторов и категорий.

В Haskell полиморфная функция map :: (a -> b) -> [a] -> [b] обобщается до политипической функции fmap :: Functor f => (a -> b) -> f a -> f b, который применяется к любому типу, принадлежащему Functor тип класс .

Конструктор типов списков [] может быть определен как экземпляр Functor введите класс, используя map функция из предыдущего примера:

instance Functor [] where
  fmap = map

Другие примеры Functor экземпляры включают деревья:

-- a simple binary tree
data Tree a = Leaf a | Fork (Tree a) (Tree a)

instance Functor Tree where  
  fmap f (Leaf x) = Leaf (f x)
  fmap f (Fork l r) = Fork (fmap f l) (fmap f r)

Отображение дерева дает:

>>> fmap square (Fork (Fork (Leaf 1) (Leaf 2)) (Fork (Leaf 3) (Leaf 4)))
Fork (Fork (Leaf 1) (Leaf 4)) (Fork (Leaf 9) (Leaf 16))

Для каждого экземпляра Functor тип класса, fmap подчиняться по контракту обязан законам функтора:

fmap id      ≡ id              -- identity law
fmap (f . g) ≡ fmap f . fmap g -- composition law

где . обозначает композицию функций в Haskell.

Помимо прочего, это позволяет определять поэлементные операции для различных типов коллекций .

Теоретико-категорный фундамент

В теории функтор категорий $F:C\rightarrow D$ состоит из двух карт: одна, которая отправляет каждый объект $A$ категории на другой объект $FA$и тот, который отправляет каждый морфизм $f:A\rightarrow B$ к другому морфизму $Ff:FA\rightarrow FB$, который действует как гомоморфизм категорий (т.е. соблюдает аксиомы категорий). Интерпретация вселенной типов данных как категории $Type$, где морфизмы являются функциями, то конструктор типа F это член Functor класс типа является объектной частью такого функтора, и fmap :: (a -> b) -> F a -> F b является частью морфизма. Описанные выше законы функтора являются в точности теоретико-категорными аксиомами функтора для этого функтора.

Функторы также могут быть объектами категорий с «морфизмами», называемыми естественными преобразованиями . Учитывая два функтора $F,G:C\rightarrow D$, естественная трансформация $\eta :F\rightarrow G$ состоит из набора морфизмов $\eta _{A}:FA\rightarrow GA$, по одному на каждый объект $A$ категории $D$, которые являются «естественными» в том смысле, что они действуют как «преобразование» между двумя функторами, не принимая во внимание объекты, к которым эти функторы применяются. Естественным преобразованиям соответствуют функции вида eta :: F a -> G a, где a — это переменная универсального кванторного типа — eta ничего не знает о типе, который обитает a. Аксиома естественности таких функций автоматически выполняется, поскольку это так называемая свободная теорема, зависящая от того, что она параметрически полиморфна . Например, reverse :: List a -> List a, который переворачивает список, является естественным преобразованием, как и flattenInorder :: Tree a -> List a, который выравнивает дерево слева направо и даже sortBy :: (a -> a -> Bool) -> List a -> List a, который сортирует список на основе предоставленной функции сравнения.

Оптимизации

Математическая основа карт допускает ряд оптимизаций . Закон композиции гарантирует, что оба

• (map f . map g) list и
• map (f . g) list

привести к тому же результату; то есть, $\operatorname {map} (f)\circ \operatorname {map} (g)=\operatorname {map} (f\circ g)$. Однако вторая форма более эффективна для вычисления, чем первая, поскольку каждая map требует восстановления всего списка с нуля. Поэтому компиляторы попытаются преобразовать первую форму во вторую; этот тип оптимизации известен как объединение карт и является функциональным аналогом объединения циклов .

Функции отображения могут быть и часто определяются в терминах складки , например foldr, что означает, что можно выполнить слияние карт : foldr f z . map g эквивалентно foldr (f . g) z.

Реализация приведенной выше карты для односвязных списков не является хвостовой рекурсивной , поэтому при вызове с большим списком она может накапливать много кадров в стеке. Многие языки поочередно предоставляют функцию «обратного отображения», которая эквивалентна обращению сопоставленного списка, но является хвостовой рекурсией. Вот реализация, которая использует функциюfold -left.

reverseMap f = foldl (\ys x -> f x : ys) []

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

Сравнение языков

Функция карты возникла в функциональных языках программирования.

В языке Lisp появилась функция отображения, называемая maplist в 1959 году, а несколько иные версии появились уже в 1958 году. Это оригинальное определение понятия maplist, отображая функцию на последовательные списки отдыха:

maplist[x;f] = [null[x] -> NIL;T -> cons[f[x];maplist[cdr[x];f]]]

Функция maplist по-прежнему доступен в более новых Lisp, таких как Common Lisp , хотя функции вроде mapcar или более общий map было бы предпочтительнее.

Возведение элементов списка в квадрат с помощью maplist будет записано в нотации S-выражения следующим образом:

(maplist (lambda (l) (sqr (car l))) '(1 2 3 4 5))

Использование функции mapcar, приведенный выше пример будет записан так:

(mapcar (function sqr) '(1 2 3 4 5))

Сегодня функции отображения поддерживаются (или могут быть определены) во многих процедурных , объектно-ориентированных и мультипарадигмальных языках: в C++ они стандартной библиотеке называются std::transform, в C# (3.0) он предоставляется как метод расширения, называемый библиотеке LINQ Select. Map также часто используемая операция в языках высокого уровня, таких как язык разметки ColdFusion (CFML), Perl , Python и Ruby ; операция называется map на всех четырех этих языках. А collect псевдоним для map также предоставляется в Ruby (из Smalltalk ). Common Lisp предоставляет семейство картоподобных функций; тот, который соответствует описанному здесь поведению, называется mapcar ( -car указание доступа с помощью операции CAR ). Существуют также языки с синтаксическими конструкциями, обеспечивающими ту же функциональность, что и функция карты.

Map иногда обобщается, чтобы принимать двоичные функции (с двумя аргументами), которые могут применять предоставленную пользователем функцию к соответствующим элементам из двух списков. В некоторых языках для этого используются специальные имена, например , map2 или zipWith . Языки, использующие явные функции с переменным числом аргументов, могут иметь версии карты с переменной арностью для поддержки функций с переменной арностью . Карта с двумя или более списками сталкивается с проблемой обработки, когда списки имеют разную длину. Различные языки различаются по этому поводу. Некоторые вызывают исключение. Некоторые останавливаются после достижения длины самого короткого списка и игнорируют дополнительные элементы в других списках. Некоторые продолжают до длины самого длинного списка, а для списков, которые уже закончились, передают в функцию некоторое значение-заполнитель, указывающее отсутствие значения.

В языках, которые поддерживают первоклассные функции и каррирование , map может частично применяться для преобразования функции, которая работает только с одним значением, в поэлементный эквивалент, который работает со всем контейнером; например, map square — это функция Haskell, которая возводит в квадрат каждый элемент списка.

Карта на разных языках

Язык	Карта	Список карт 2	Карта n списков	Примечания	Обработка списков разной длины
АПЛ	func list	list1 func list2	func/ list1 list2 list3 list4	Возможности обработки массивов APL делают такие операции, как отображение, неявными.	ошибка длины, если длина списка не равна или равна 1
Общий Лисп	(mapcar func list)	(mapcar func list1 list2)	(mapcar func list1 list2 ...)		останавливается после длины кратчайшего списка
С++	std::transform(begin, end, result, func)	std::transform(begin1, end1, begin2, result, func)		в заголовке <алгоритм> начало , конец и результат являются итераторами результат записывается начиная с результата
С#	ienum.Select(func) или The select пункт	ienum1.Zip(ienum2, func)		Select это метод расширения ienum — это IEnumerable Zip представлен в .NET 4.0 Аналогично во всех языках .NET.	останавливается после того, как заканчивается кратчайший список
CFML	obj.map(func)			Где obj представляет собой массив или структуру. func получает в качестве аргументов значение каждого элемента, его индекс или ключ и ссылку на исходный объект.
Кложур	(map func list)	(map func list1 list2)	(map func list1 list2 ...)		останавливается после того, как заканчивается кратчайший список
Д	list.map!func	zip(list1, list2).map!func	zip(list1, list2, ...).map!func		Указано для сжатия с помощью StoppingPolicy: самое короткое, самое длинное или requireSameLength.
Эрланг	lists:map(Fun, List)	lists:zipwith(Fun, List1, List2)	zipwith3 также доступен		Списки должны быть одинаковой длины
Эликсир	Enum.map(list, fun)	Enum.zip(list1, list2) |> Enum.map(fun)	List.zip([list1, list2, ...]) |> Enum.map(fun)		останавливается после того, как заканчивается кратчайший список
Ф#	List.map func list	List.map2 func list1 list2		Существуют функции для других типов ( Seq и Array ).	Выдает исключение
классный	list.collect(func)	[list1 list2].transpose().collect(func)	[list1 list2 ...].transpose().collect(func)
Хаскелл	map func list	zipWith func list1 list2	zipWithn func list1 list2 ...	n соответствует количеству списков; предопределено до zipWith7	останавливается после того, как заканчивается кратчайший список
Смешанный	array.map(func) list.map(func) Lambda.map(iterable, func)
Дж	func list	list1 func list2	func/ list1, list2, list3 ,: list4	Возможности J по обработке массивов делают такие операции, как отображение, неявными.	ошибка длины, если длины списка не равны
Ява 8+	stream.map(func)
JavaScript 1.6 ECMAScript 5	array#map(func)	List1.map(function (elem1, i) { return func(elem1, List2[i]); })	List1.map(function (elem1, i) { return func(elem1, List2[i], List3[i], ...); })	Array#map передает в функцию func 3 аргумента : элемент, индекс элемента и массив. Неиспользуемые аргументы могут быть опущены.	Останавливается в конце List1 , при необходимости расширяя более короткие массивы неопределенными элементами.
Юлия	map(func, list)	map(func, list1, list2)	map(func, list1, list2, ..., listN)		ОШИБКА: Несоответствие размеров
Логток	map(Closure, List)	map(Closure, List1, List2)	map(Closure, List1, List2, List3, ...) (up to seven lists)	только аргумента Closure Необходимо создать экземпляр .	Отказ
Математика	func /@ list Map[func, list]	MapThread[func, {list1, list2}]	MapThread[func, {list1, list2, ...}]		Списки должны быть одинаковой длины
Максима	map(f, expr1, ..., exprn) maplist(f, expr1, ..., exprn)			карта возвращает выражение, ведущий оператор которого тот же, что и в выражениях; Maplist возвращает список
OCaml	List.map func list Array.map func array	List.map2 func list1 list2			вызывает исключение Invalid_argument
СТАВКА/ГП	apply(func, list)				—
Перл	map block list map expr, list			В блоке или выражении специальная переменная $_ по очереди хранит каждое значение из списка.	Помощник List::MoreUtils::each_array объединяет более одного списка, пока не будет исчерпан самый длинный, заполняя остальные undef.
PHP	array_map(callable, array)	array_map(callable, array1,array2)	array_map(callable, array1,array2, ...)	Количество параметров для вызываемых должно соответствовать количеству массивов.	расширяет более короткие списки NULL элементами
Пролог	maplist(Cont, List1, List2).	maplist(Cont, List1, List2, List3).	maplist(Cont, List1, ...).	Аргументы списка являются входными, выходными или и тем, и другим. Включает также zipWith, unzip, all	Тихий сбой (не ошибка)
Питон	map(func, list)	map(func, list1, list2)	map(func, list1, list2, ...)	Возвращает список в Python 2 и итератор в Python 3.	zip() и map() (3.x) останавливается после окончания кратчайшего списка, тогда как map() (2.х) и itertools.zip_longest() (3.x) расширяет более короткие списки с помощью None предметы
Руби	enum.collect {block} enum.map {block}	enum1.zip(enum2).map {block}	enum1.zip(enum2, ...).map {block} [enum1, enum2, ...].transpose.map {block}	enum is an Enumeration	останавливается в конце вызываемого объекта (первый список); если какой-либо другой список короче, он дополняется нулевыми элементами
Ржавчина	list1.into_iter().map(func)	list1.into_iter().zip(list2).map(func)		тот Iterator::map и Iterator::zip методы одновременно берут на себя ответственность за исходный итератор и возвращают новый; тот Iterator::zip метод внутренне вызывает IntoIterator::into_iter метод на list2	останавливается после окончания более короткого списка
С - Р	lapply(list, func)	mapply(func, list1, list2)	mapply(func, list1, list2, ...)		Более короткие списки цикличны
Скала	list.map(func)	(list1, list2).zipped.map(func)	(list1, list2, list3).zipped.map(func)	примечание: более 3 невозможно.	останавливается после окончания более короткого списка
Схема (включая хитрость и рэкет )	(map func list)	(map func list1 list2)	(map func list1 list2 ...)		все списки должны иметь одинаковую длину (SRFI-1 расширяется, чтобы принимать списки разной длины)
Смолток	aCollection collect: aBlock	aCollection1 with: aCollection2 collect: aBlock			Не удалось
Стандартный ML	map func list	ListPair.map func (list1, list2) ListPair.mapEq func (list1, list2)		Для карты с двумя аргументами func принимает аргументы в кортеже.	ListPair.map останавливается после окончания кратчайшего списка, тогда как ListPair.mapEq поднимает UnequalLengths исключение
Быстрый	sequence.map(func)	zip(sequence1, sequence2).map(func)			останавливается после того, как заканчивается кратчайший список
XPath 3 XQuery 3	list ! block for-each(list, func)	for-each-pair(list1, list2, func)		В block элемент контекста . сохраняет текущее значение	останавливается после того, как заканчивается кратчайший список

См. также

• Функтор (функциональное программирование)
• Архивирование (информатика) или zip, сопоставление «списка» с несколькими списками.
• Фильтр (функция высшего порядка)
• Сгиб (функция высшего порядка)
• цикл foreach
• Бесплатный моноид
• Функциональное программирование
• Функция высшего порядка
• Понимание списка
• Карта (параллельный шаблон)