This articlerelies largely or entirely on asingle source. Relevant discussion may be found on thetalk page. Please helpimprove this article byintroducing citations to additional sources. Find sources: "Map" higher-order function – news ·newspapers ·books ·scholar ·JSTOR(November 2012)

In manyprogramming languages,map is ahigher-order function that applies agiven function to each element of acollection, e.g. alist orset, returning the results in a collection of the same type. It is often calledapply-to-all when considered infunctional form.

The concept of a map is not limited to lists: it works for sequentialcontainers, tree-like containers, or even abstract containers such asfutures and promises.

Suppose there is a list of integers[1, 2, 3, 4, 5] . To calculate thesquare of each integer, one would first define a function tosquare a single number (shown here inHaskell):

squarex=x*x

Afterwards, call:

>>>mapsquare[1,2,3,4,5]

which yields[1, 4, 9, 16, 25], demonstrating thatmap has gone through the entire list and applied the functionsquare to each element.

Below, is a view of each step of the mapping process for a list of integersX = [0, 5, 8, 3, 2, 1] mapping into a new listX' according to the function${\displaystyle f(x)=x+1}$ :

Themap is provided as part of the Haskell's base prelude (i.e. "standard library") and is implemented as:

map::(a->b)->[a]->[b]map_[]=[]mapf(x:xs)=fx:mapfxs

In Haskell, thepolymorphic functionmap::(a->b)->[a]->[b] is generalized to apolytypic functionfmap::Functorf=>(a->b)->fa->fb, which applies to any type belonging theFunctortype class.

Thetype constructor of lists[] can be defined as an instance of theFunctor type class using themap function from the previous example:

instanceFunctor[]wherefmap=map

Other examples ofFunctor instances include trees:

-- a simple binary treedataTreea=Leafa|Fork(Treea)(Treea)instanceFunctorTreewherefmapf(Leafx)=Leaf(fx)fmapf(Forklr)=Fork(fmapfl)(fmapfr)

Mapping over a tree yields:

>>>fmapsquare(Fork(Fork(Leaf1)(Leaf2))(Fork(Leaf3)(Leaf4)))Fork(Fork(Leaf1)(Leaf4))(Fork(Leaf9)(Leaf16))

For every instance of theFunctor type class,fmap iscontractually obliged to obey the functor laws:

fmapid≡id-- identity lawfmap(f.g)≡fmapf.fmapg-- composition law

where. denotesfunction composition in Haskell.

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

Incategory theory, afunctor${\displaystyle F:C\to D}$ consists of two maps: one that sends each objectA of the category to another objectF A, and one that sends each morphism${\displaystyle f:A\to B}$ to another morphism${\displaystyle Ff:FA\to FB}$, which acts as ahomomorphism on categories (i.e. it respects the category axioms). Interpreting the universe of data types as a categoryType, with morphisms being functions, then a type constructorF that is a member of theFunctor type class is the object part of such a functor, andfmap::(a->b)->Fa->Fb is the morphism part. The functor laws described above are precisely the category-theoretic functor axioms for this functor.

Functors can also be objects in categories, with "morphisms" callednatural transformations. Given two functors${\displaystyle F,G:C\to D}$, a natural transformation${\displaystyle \eta :F\to G}$ consists of a collection of morphisms${\displaystyle {\eta }_A:FA\to GA}$, one for each objectA of the categoryD, which are 'natural' in the sense that they act as a 'conversion' between the two functors, taking no account of the objects that the functors are applied to. Natural transformations correspond to functions of the formeta::Fa->Ga, wherea is a universally quantified type variable –eta knows nothing about the type which inhabitsa. The naturality axiom of such functions is automatically satisfied because it is a so-called free theorem, depending on the fact that it isparametrically polymorphic.^[1] For example,reverse::Lista->Lista, which reverses a list, is a natural transformation, as isflattenInorder::Treea->Lista, which flattens a tree from left to right, and evensortBy::(a->a->Bool)->Lista->Lista, which sorts a list based on a provided comparison function.

The mathematical basis of maps allow for a number ofoptimizations. The composition law ensures that both

• (map f . map g) list and
• map (f . g) list

lead to the same result; that is,${\displaystyle \mathrm{map}(f)\circ \mathrm{map}(g)=\mathrm{map}(f\circ g)}$. However, the second form is more efficient to compute than the first form, because eachmap requires rebuilding an entire list from scratch. Therefore, compilers will attempt to transform the first form into the second; this type of optimization is known asmap fusion and is thefunctional analog ofloop fusion.^[2]

Map functions can be and often are defined in terms of afold such asfoldr, which means one can do amap-fold fusion:foldr f z . map g is equivalent tofoldr (f . g) z.

The implementation of map above on singly linked lists is nottail-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 thefold-left function.

reverseMapf=foldl(\ysx->fx: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, though it requires performing two passes over the list.

The map function originated infunctional programming languages.

The languageLisp introduced a map function calledmaplist^[3] in 1959, with slightly different versions already appearing in 1958.^[4] This is the original definition formaplist, mapping a function over successive rest lists:

maplist[x;f] = [null[x] -> NIL;T -> cons[f[x];maplist[cdr[x];f]]]

The functionmaplist is still available in newer Lisps likeCommon Lisp,^[5] though functions likemapcar or the more genericmap would be preferred.

Squaring the elements of a list usingmaplist would be written inS-expression notation like this:

(maplist(lambda(l)(sqr(carl)))'(12345))

Using the functionmapcar, above example would be written like this:

(mapcar(functionsqr)'(12345))

Today mapping functions are supported (or may be defined) in manyprocedural,object-oriented, andmulti-paradigm languages as well: InC++'sStandard Library, it is calledstd::transform orstd::ranges::transform, inC# (3.0)'s LINQ library, it is provided as an extension method calledSelect. Map is also a frequently used operation in high level languages such asColdFusion Markup Language (CFML),Perl,Python, andRuby; the operation is calledmap in all four of these languages. Acollect alias formap is also provided in Ruby (fromSmalltalk).Common Lisp provides a family of map-like functions; the one corresponding to the behavior described here is calledmapcar (-car indicating access using theCAR 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 asmap2 orzipWith. Languages using explicitvariadic functions may have versions of map with variablearity to supportvariable-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 supportfirst-class functions andcurrying,map may bepartially applied tolift a function that works on only one value to an element-wise equivalent that works on an entire container; for example,map square is a Haskell function which squares each element of a list.

• Functor (functional programming)
• Zipping (computer science) or zip, mapping 'list' over multiple lists
• Filter (higher-order function)
• Fold (higher-order function)
• foreach loop
• Free monoid
• Functional programming
• Higher-order function
• List comprehension
• Map (parallel pattern)

• Higher-order functions
• Programming language comparisons
• Iteration in programming

• Articles with short description
• Short description is different from Wikidata
• Articles needing additional references from November 2012
• All articles needing additional references
• Articles with example Haskell code