Map (программирование)

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

Например, если определить функцию square следующим образом:

square x = x * x

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

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

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

Иногда встречается обобщённая версия map, принимающая функцию двух аргументов, 2 списка и применяющая её к соответствующим элементам списков. В некоторых языках для них заданы специальные имена вроде map2 или zipWith. Функция map с двумя или более списками порождает проблему работы со списками различной длины. Различные языки ведут себя по-разному: некоторые выбрасывают исключение, другие останавливаются по достижению конца короткого списка и игнорируют остальные элементы более длинных списков, третьи идут до самого длинного, возвращая некоторое специальное значение для списков, чьи значения уже закончились.

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

map в различных языках

Map в различных языках

Язык	Map	Map 2 списков	Map n списков	Примечания	Поведение при списках различной длины
Haskell	map func list	zipWith func list1 list2	zipWithn func list1 list2 …	n соответствует числу списков; определено вплоть до zipWith7	останавливается после конца самого короткого списка
Haxe	Lambda.map(iterable, func)
J	func list	list func list	func/ list1 , list2 , list3 ,: list4	Возможности обработки массивов в языке позволяют неявно вызывать такие функции, как map	Списки должны быть одинаковой длины (length error if lists not equal)
OCaml	List.map func list Array.map func array	List.map2 func list1 list2			выбрасывает исключение Invalid_argument
Standard ML	map func list	ListPair.map func (list1, list2) ListPair.mapEq func (list1, list2)		Для map двух списков, func получает элементы в виде кортежа.	ListPair.map останавливается по достижению конца самого короткого списка, ListPair.mapEq выбрасывает исключение UnequalLengths
Python	map(func, list)	map(func, list1, list2)	map(func, list1, list2, …)		zip() and map() (версии 3.x) останавливаются по достижению конца самого короткого списка, map() (2.x) и itertools.zip_longest() (3.x) расширяют короткие списки значениями None
Ruby	enum.collect {block} enum.map {block}	enum1.zip(enum2).map {block}	enum1.zip(enum2, …).map {block} [enum1, enum2, …].transpose.map {block}	enum — это перечисление	останавливается по достижению конца списка, на котором функция вызвана (первый список); если какой-либо другой список короче, он расширяется значениями nil
C++	std::transform(begin, end, result, func)	std::transform(begin1, end1, begin2, result, func)		в заголовке <algorithm> begin, end, & result итераторы результат будет записан в начало result
Perl	map block list map expr, list			В block или expr специальное значение $_ содержит каждое значение из списка.	N/A
C# 3.0	ienum.Select(func)
C# 4.0	ienum.Select(func)	ienum1.Zip(ienum2, func)			останавливается по достижению конца самого короткого списка
JavaScript 1.6	array.map(func)	-	-	map представлен только как метод массива, поэтому возможно применение только к одному списку (массиву)
Common Lisp	(mapcar func list)	(mapcar func list1 list2)	(mapcar func list1 list2 …)		Останавливается по достижению конца самого короткого списка
Scheme, Clojure	(map func list)	(map func list1 list2)	(map func list1 list2 …)		Останавливается по достижению конца самого короткого списка
Smalltalk	aCollection collect: aBlock	aCollection1 with: aCollection2 collect: aBlock			Падает
Erlang	lists: map(Fun, List)	lists: zipwith(Fun, List1, List2)		также доступен zipwith3	Списки должны быть одинаковой длины
PHP	array_map(callback, array)	array_map(callback, array1,array2)	array_map(callback, array1,array2, …)	Число аргументов callback обязано совпадать с числом массивов.	расширят короткие списки значениями NULL
Mathematica	func /@ list Map[func, list]	MapThread[func, {list1, list2}]	MapThread[func, {list1, list2, …}]		Списки должны быть одинаковой длины
MATLAB	arrayfun(func, list)	arrayfun(func, list1, list2)	arrayfun(func, list1, …, listn)	cellfun для cell-списков
Maxima	map(f, expr1, …, exprn) maplist(f, expr1, …, exprn)
S/R	lapply(list,func)	mapply(func,list1,list2)	mapply(func,list1,list2,…)		Короткие списки циклически повторяются
Scala	list.map(func)	(list1, list2).zipped.map(func)	(list1, list2,"list3").zipped.map(func)	не более 3 списков.	останавливается по достижению конца самого короткого
Java 8	list.stream().map(func)			нет функций первого класса; используется интерфейс java.lang.Function<T, R>

Оптимизации

Математическая основа операции map позволяет проводить множество оптимизаций. (map f . map g) xs (где «.» — оператор композиции функций) эквивалентно map (f . g) xs ; то есть: $\left({\text{map}}\,f\right)\circ \left({\text{map}}\,g\right)={\text{map}}\,\left(f\circ g\right)$. Эта оптимизация избавляет от необходимости в двукратном вызове map за счёт совмещения применения функций f и g.

Функцию map можно определить, используя свёртку списка. В частности, id xs = map id xs = foldr (:) [] xs = xs. Сочетание же fold и map можно оптимизировать: foldr f z . map g эквивалентно foldr (f . g) z, таким образом map g xs = (id . map g) xs = foldr ((:) . g) [] xs. Такая реализация map при использовании с односвязными списками в не-ленивых языках не поддаётся оптимизации хвостовой рекурсии напрямую (хотя подлежит оптимизации «по модулю cons»), поэтому она может привести к переполнению стека в случае применения к большим спискам. Во многих языках существует альтернативная «инвертированная функция map», эквивалентная функции map в случае инвертированного списка, но зато с возможностью оптимизации хвостовой рекурсии. Реализация, использующая левую свёртку:

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

См. также

• Свёртка списка