In many programming languages, map is a higher-order function that applies a given function to each element of a collection, e.g. a list or set, returning the results in a collection of the same type. It is often called apply-to-all when considered in functional form. The concept of a map is not limited to lists: it works for sequential containers, tree-like containers, or even abstract containers such as futures and promises.
Examples: mapping a list Suppose there is a list of integers [1, 2, 3, 4, 5] . To calculate the square of each integer, one would first define a function to square a single number (shown here in Haskell):
Afterwards, call:
which yields [1, 4, 9, 16, 25], demonstrating that map has gone through the entire list and applied the function square to each element.
Visual example Below, is a view of each step of the mapping process for a list of integers X = [0, 5, 8, 3, 2, 1] mapping into a new list X' according to the function f ( x ) = x + 1 {\displaystyle f(x)=x+1} :
The map is provided as part of the Haskell's base prelude (i.e. "standard library") and is implemented as:
Generalization
In Haskell, the polymorphic function map :: (a -> b) -> [a] -> [b] is generalized to a polytypic function fmap :: Functor f => (a -> b) -> f a -> f b, which applies to any type belonging the Functor type class. The type constructor of lists [] can be defined as an instance of the Functor type class using the map function from the previous example:
Other examples of Functor instances include trees:
Mapping over a tree yields:
For every instance of the Functor type class, fmap is contractually obliged to obey the functor laws:
where . denotes function composition in Haskell. Among other uses, this allows defining element-wise operations for various kinds of collections.
Category-theoretic background In category theory, a functor F : C → D {\displaystyle F:C\rightarrow D} consists of two maps: one that sends each object A of the category to another object F A, and one that sends each morphism f : A → B {\displaystyle f:A\rightarrow B} to another morphism F f : F A → F B {\displaystyle Ff:FA\rightarrow FB} , which acts as a homomorphism on categories (i.e. it respects the category axioms). Interpreting the universe of data types as a category Type, with morphisms being functions, then a type constructor F that is a member of the Functor type class is the object part of such a functor, and fmap :: (a -> b) -> F a -> F b 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" called natural transformations. Given two functors F , G : C → D {\displaystyle F,G:C\rightarrow D} , a natural transformation η : F → G {\displaystyle \eta :F\rightarrow G} consists of a collection of morphisms η A : F A → G A {\displaystyle \eta _{A}:FA\rightarrow GA} , one for each object A of the category D, 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 form eta :: F a -> G a, where a is a universally quantified type variable – eta knows nothing about the type which inhabits a. The naturality axiom of such functions is automatically satisfied because it is a so-called free theorem, depending on the fact that it is parametrically polymorphic. For example, reverse :: List a -> List a, which reverses a list, is a natural transformation, as is flattenInorder :: Tree a -> List a, which flattens a tree from left to right, and even sortBy :: (a -> a -> Bool) -> List a -> List a, which sorts a list based on a provided comparison function.
Optimizations The mathematical basis of maps allow for a number of optimizations. The composition law ensures that both
(map f . map g) list and map (f . g) list lead to the same result; that is, map ( f ) ∘ map ( g ) = map ( f ∘ g ) {\displaystyle \operatorname {map} (f)\circ \operatorname {map} (g)=\operatorname {map} (f\circ g)} . However, the second form is more efficient to compute than the first form, because each map 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 as map fusion and is the functional analog of loop 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.
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.
Language comparison The map function originated in functional programming languages. The language Lisp introduced a map function called maplist in 1959, with slightly different versions already appearing in 1958. This is the original definition for maplist, mapping a function over successive rest lists:
maplist[x;f] = [null[x] -> NIL;T -> cons[f[x];maplist[cdr[x];f]]]
… excerpt ends here. Continue reading the full article.
