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 f . map g) xs (где « . » — оператор композиции функций ) эквивалентно map (f . g) xs ; то есть: ${\displaystyle \left({\text{map}}\,f\right)\circ \left({\text{map}}\,g\right)={\text{map}}\,\left(f\circ g\right)}$ . Эта оптимизация избавляет от необходимости в двукратном вызове map за счёт совмещения применения функций f и g .

Функцию 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 при использовании с односвязными списками в не- ленивых языках не поддаётся оптимизации хвостовой рекурсии напрямую (хотя подлежит оптимизации ), поэтому она может привести к переполнению стека в случае применения к большим спискам. Во многих языках существует альтернативная «инвертированная функция map», эквивалентная функции map в случае инвертированного списка, но зато с возможностью оптимизации хвостовой рекурсии. Реализация, использующая левую свёртку:

 revMap f xs = foldl (\ys x -> f x : ys) [] xs

Примечания

См. также

• Свёртка списка