- 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 arrayList.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 итераторы
результат будет записан в начало resultPerl 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
; то есть,. Эта оптимизация избавляет нас от необходимости в двукратном вызове
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
Ссылки
См. также
- Свёртка списка
- foreach
- Генераторы списков
- Свободный моноид
- MapReduce
Категория:- Функциональное программирование
Wikimedia Foundation. 2010.