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. Map также часто используется в высокоуровневых языках, таких как Perl, Python и Ruby; во всех трех языках функция называется map. В Ruby для map также существует псевдоним collect. В Common Lisp существует целое семейство функций, подобных map; mapcar, соответствующее описанному здесь поведению (суффикс car означает доступ с помощью операции CAR). Также существуют языки с синтаксическими конструкциями, предоставляющими функциональность, аналогичную функции map.

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

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

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	J’s array processing capabilities make operations like map implicit	Списки должны быть одинаковой длины (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 списков.	останавливается по достижению конца самого короткого

Оптимизации

Математическая основа операции 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.^[1]

Функцию 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

Ссылки

1. ↑ «Map fusion: Making Haskell 225 % faster»

См. также

• Свёртка списка
• foreach
• Генераторы списков
• Свободный моноид
• MapReduce