Map (higher-order function)

In many programming languages, map is the name of a higher-order function that applies a given function to each element of a list, returning a list of results. It is often called apply-to-all when considered in functional form.

Example

For example, if we define in Haskell a function square as follows:

square x = x * x

Then calling map square [1,2,3,4,5] will return [1,4,9,16,25], as map will go through the list and apply the function square to each element.

Generalization

See also: Functor and Category theory

In the Haskell programming language, the polymorphic function  map :: (a -> b) -> [a] -> [b] is generalized to a polytypic function called fmap :: Functor f => (a -> b) -> f a -> f b, which applies to any type in the Functor class.

map is used in Haskell's Prelude to define the list type constructor ([]) an instance of the Functor type class as follows

 instance Functor [] where fmap = map

But trees may belong to Functor too, for example:

 data Tree a = Leaf a | Fork (Tree a) (Tree a)
 instance Functor Tree where  
   fmap f (Leaf x) = Leaf (f x)
   fmap f (Fork l r) = Fork (fmap f l) (fmap f r)

 fmap (1+) (Fork(Fork(Leaf 0)(Leaf 1))(Fork(Leaf 2)(Leaf 3)))

evaluates to:

 Fork (Fork(Leaf 1)(Leaf 2))(Fork(Leaf 3)(Leaf 4))

For every instance of the Functor type class, fmap is expected to be defined such that it obeys the functor laws:

fmap id = id -- identity
fmap (f . g) = fmap f . fmap g -- composition

Among other uses, this allows defining element-wise operations for various kinds of collections.

Moreover, if $F$ and $G$ are two functors, a natural transformation is a function of polymorphic type $h: \, \forall T.\, F \, T \rarr G \, T$ which respects fmap:

$h_{Y} \circ (\mathrm{fmap} \, k) = (\mathrm{fmap} \, k) \circ h_{X}$ for any function $k: X \rarr Y$.

If the h function is defined by parametric polymorphism as in the type definition above, this specification is always satisfied.

Optimizations

The mathematical basis of maps allow for a number of optimizations. If one has (map f . map g) xs ('.' is function composition) then it is the same as the simpler map (f . g) xs; that is, $\left( \text{map}\,f \right) \circ \left( \text{map}\,g \right) = \text{map}\,\left( f \circ g \right)$. This particular optimization eliminates an expensive second map by fusing it with the first map; thus it is a "map fusion".

Map functions can be and often are defined in terms of a fold such as foldr, which means one can do a "map-fold fusion": foldr f z . map g is equivalent to foldr (f . g) z.

The implementation of map above on singly linked lists is not tail-recursive, so it may build up a lot of frames on the stack when called with a large list. Many languages alternately provide a "reverse map" function, which is equivalent to reversing a mapped list, but is tail-recursive. Here is an implementation which utilizes the fold-left function.

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

Since reversing a singly linked list is also tail-recursive, reverse and reverse-map can be composed to perform normal map in a tail-recursive way.

Language comparison

The map function originated in functional programming languages but is today supported (or may be defined) in many procedural, object oriented, and multi-paradigm languages as well: In C++'s Standard Template Library, it is called transform, in C# (3.0)'s LINQ library, it is provided as an extension method called Select. Map is also a frequently used operation in high level languages such as CFML, Perl, Python and Ruby; the operation is called map in all four of these languages. A collect alias for map is also provided in Ruby (from Smalltalk). Common Lisp provides a family of map-like functions; the one corresponding to the behavior described here is called mapcar (-car indicating access using the CAR operation). There are also languages with syntactic constructs providing the same functionality as the map function.

Map is sometimes generalized to accept dyadic (2-argument) functions that can apply a user-supplied function to corresponding elements from two lists; some languages use special names for this, such as map2 or zipWith. Languages using explicit variadic functions may have versions of map with variable arity to support variable-arity functions. Map with 2 or more lists encounters the issue of handling when the lists are of different lengths. Various languages differ on this; some raise an exception, some stop after the length of the shortest list and ignore extra items on the other lists; some continue on to the length of the longest list, and for the lists that have already ended, pass some placeholder value to the function indicating no value.

In languages which support first-class functions, map may be partially applied to "lift" functions to element-wise versions; for instance, (map square) is a Haskell function which squares lists element-wise.

Map in various languages

Language	Map	Map 2 lists	Map n lists	Notes	Handling lists of different lengths
Common Lisp	(mapcar func list)	(mapcar func list1 list2)	(mapcar func list1 list2 ...)		stops after the length of the shortest list
C++	std::transform(begin, end, result, func)	std::transform(begin1, end1, begin2, result, func)		in header <algorithm> begin, end, & result are iterators result is written starting at result
C# 3.0	ienum.Select(func)			Select is an extension method ienum is an IEnumerable Similarly in all .NET languages
C# 4.0	ienum.Select(func)	ienum1.Zip(ienum2, func)		Select is an extension method ienum is an IEnumerable Similarly in all .NET languages	stops after the shortest list ends
CFML	obj.map(func)			Where obj is an array or a structure. func receives as arguments each item's value, its index or key, and a reference to the original object.
Clojure	(map func list)	(map func list1 list2)	(map func list1 list2 ...)		Clojure: stops after the shortest list ends
D	list.map!func	zip(list1, list2).map!func	zip(list1, list2, ...).map!func		Specified to zip by StoppingPolicy: shortest, longest, or requireSameLength
Erlang	lists:map(Fun, List)	lists:zipwith(Fun, List1, List2)	zipwith3 also available		Lists must be equal length
F#	List.map func list	List.map2 func list1 list2		Functions exist for other types (Seq and Array)	Throws exception
Haskell	map func list	zipWith func list1 list2	zipWithn func list1 list2 ...	n corresponds to the number of lists; predefined up to zipWith7	stops after the shortest list ends
Groovy	list.collect(func)	[list1 list2].transpose().collect(func)	[list1 list2 ...].transpose().collect(func)
Haxe	array.map(func) list.map(func) Lambda.map(iterable, func)
J	func list	list1 func list2	func/ list1, list2, list3 ,: list4	J's array processing capabilities make operations like map implicit	length error if list lengths not equal
Java 8+	stream.map(func)
JavaScript 1.6 ECMAScript 5	array#map(func)	List1.map(function (elem1, i) { return func(elem1, List2[i]); })	List1.map(function (elem1, i) { return func(elem1, List2[i], List3[i], ...); })	Array#map passes 3 arguments to func: the element, the index of the element, and the array. Unused arguments can be omitted.	Stops at the end of List1, extending the shorter arrays with undefined items if needed.
Logtalk	map(Closure, List)	map(Closure, List1, List2)	map(Closure, List1, List2, List3, ...) (up to seven lists)	Only the Closure argument must be instantiated.	Failure
Mathematica	func /@ list Map[func, list]	MapThread[func, {list1, list2}]	MapThread[func, {list1, list2, ...}]		Lists must be same length
Maxima	map(f, expr1, ..., exprn) maplist(f, expr1, ..., exprn)			map returns an expression whose leading operator is the same as that of the expressions; maplist returns a list
OCaml	List.map func list Array.map func array	List.map2 func list1 list2			raises Invalid_argument exception
PARI/GP	apply(func, list)				N/A
Perl	map block list map expr, list			In block or expr special variable $_ holds each value from list in turn.	Helper List::MoreUtils::each_array combines more than one list until the longest one is exhausted, filling the others with undef.
PHP	array_map(callback, array)	array_map(callback, array1,array2)	array_map(callback, array1,array2, ...)	The number of parameters for callback should match the number of arrays.	extends the shorter lists with NULL items
Prolog	maplist(Cont, List1, List2).	maplist(Cont, List1, List2, List3).	maplist(Cont, List1, ...).	List arguments are input, output or both. Subsumes also zipWith, unzip, all	Silent failure (not an error)
Python	map(func, list)	map(func, list1, list2)	map(func, list1, list2, ...)	Returns a list in Python 2 and an iterator in Python 3.	zip() and map() (3.x) stops after the shortest list ends, whereas map() (2.x) and itertools.zip_longest() (3.x) extends the shorter lists with None items
Racket	(map func list)	(map func list1 list2)	(map func list1 list2 ...)		lists must all have the same length
Ruby	enum.collect {block} enum.map {block}	enum1.zip(enum2).map {block}	enum1.zip(enum2, ...).map {block} [enum1, enum2, ...].transpose.map {block}	enum is an Enumeration	stops at the end of the object it is called on (the first list); if any other list is shorter, it is extended with nil items
S/R	lapply(list, func)	mapply(func, list1, list2)	mapply(func, list1, list2, ...)		Shorter lists are cycled
Scala	list.map(func)	(list1, list2).zipped.map(func)	(list1, list2, list3).zipped.map(func)	note: more than 3 not possible.	stops after the shorter list ends
Scheme	(map func list)	(map func list1 list2)	(map func list1 list2 ...)		lists must all have same length
Smalltalk	aCollection collect: aBlock	aCollection1 with: aCollection2 collect: aBlock			Fails
Standard ML	map func list	ListPair.map func (list1, list2) ListPair.mapEq func (list1, list2)		For 2-argument map, func takes its arguments in a tuple	ListPair.map stops after the shortest list ends, whereas ListPair.mapEq raises UnequalLengths exception
Swift	array.map(func) map(sequence, func)	map(zip(sequence1, sequence2), func)			stops after the shortest list ends
XPath 3 XQuery 3	list ! block for-each(list, func)	for-each-pair(list1, list2, func)		In block the context item . holds the current value	stops after the shortest list ends

See also

• Convolution (computer science), (also known as conv or zip)
• Filter (higher-order function)
• Fold (higher-order function)
• foreach
• Free monoid
• Functional programming
• Higher-order function
• List comprehension
• Map (parallel pattern)