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

Ссылки[править | править исходный текст]

См. также[править | править исходный текст]