Map (higher-order function)

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.

To do this, 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.

: The map is provided as part of the Haskell's base prelude (i.e. "standard library") and is implemented as: 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 .

, 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.

Functors can also be objects in categories, with "morphisms" called natural transformations.

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.

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.

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 language Lisp introduced a map function called maplist[3] in 1959, with slightly different versions already appearing in 1958.

[4] This is the original definition for maplist, mapping a function over successive rest lists: The function maplist is still available in newer Lisps like Common Lisp,[5] though functions like mapcar or the more generic map would be preferred.

Squaring the elements of a list using maplist would be written in S-expression notation like this: Using the function mapcar, above example would be written like this: Today mapping functions are supported (or may be defined) in many procedural, object-oriented, and multi-paradigm languages as well: In C++'s Standard Library, it is called std::transform, in C# (3.0)'s LINQ library, it is provided as an extension method called Select.

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).

In languages which support first-class functions and currying, map may be partially applied to lift 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.