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 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^[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

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