In many programming languages, map is the name of a higher-order function that applies a given function to a sequence of elements (such as a list) and returns a sequence of results. They are examples of both catamorphisms and anamorphisms.
For example, if we define 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].
Map itself may be defined recursively, like this code in Haskell:
map f [] = [] map f (x:xs) = f x : map f xs
Language comparison
The map function is especially common in functional programming languages, but some high-level procedural languages support it as well, and in others it may be defined. Common Lisp provides a whole family of map-like functions. The one that corresponds to the behavior described here is called mapcar, where the -car designation indicates access using the CAR operation. In C++'s Standard Template Library, the map function is called transform. In C# (3.0), the map function is provided as an extension method called select. It is also frequently used as an array operation in scripting languages such as Perl, Python and Ruby; the operation is called map in Perl and Python and collect in Ruby.
Optimizations
The mathematical basis of maps allow for a number of optimizations. If one has map f . map g ('.' is function composition) then it is the same as the simpler map (f . g) xs; that is,
. This particular optimization eliminates an expensive second map by fusing it with the first map; thus it is a "map fusion"[1].
Map functions can and often are defined in terms of a fold such as foldr, which means one can do a "map-fold fusion": 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 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.
Haskell's Functor class
In the Haskell programming language, map is generalized to a polymorphic function called fmap using the Functor type class. For every Functor instance, fmap must be defined such that it obeys the Functor laws:
fmap id = id -- identityfmap (f . g) = fmap f . fmap g -- composition
Mapping in .NET Procedural Languages
The map function in .NET Procedural languages like C# or VB.NET (as of C# 2.0 and VB 8.0) is supported through the select extension method. Here's an example that combines the use of select() with the use of anonymous functions, support for which was added to C# in version 3.0 (November 2007).
var values = new System.Collections.Generic.List<int>() { 7, 13, 4, 9, 3 };
var foo = values.Select(d => d * d);