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 означает доступ к первому элементу списка). Также существуют языки с синтаксическими конструкциями, предоставляющими функциональность, аналогичную функции map.
Иногда встречается обобщённая версия map, принимающая функцию двух аргументов, 2 списка и применяющая её к соответствующим элементам списков. В некоторых языках для них заданы специальные имена вроде map2 или zipWith. Функция map с двумя или более списками порождает проблему работы со списками различной длины. Различные языки ведут себя по-разному: некоторые выбрасывают исключение, другие останавливаются по достижению конца короткого списка и игнорируют остальные элементы более длинных списков, третьи идут до самого длинного, возвращая некоторое специальное значение для списков, чьи значения уже закончились.
В языках, поддерживающих функции первого класса, 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 | Возможности обработки массивов в языке позволяют неявно вызывать такие функции, как 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 ; то есть: . Эта оптимизация избавляет от необходимости в двукратном вызове 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
Примечания
- ↑ «Map fusion: Making Haskell 225 % faster». Дата обращения: 17 июля 2011. Архивировано 6 августа 2013 года.
