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 in the same order. 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.
Suppose we have a list of integers [1, 2, 3, 4, 5]
and would like to calculate the square of each integer. To do this, we first define a function to square
a single number (shown here in Haskell):
Afterwards we may 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 .
denotes function composition in Haskell.