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 в различных языках
ЯзыкMapMap 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

Примечания

См. также

This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.