Map (higher-order function)

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.

Example: mapping a list

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

square x = x * x

Afterwards we may call

>>> map square [1, 2, 3, 4, 5]

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:

map :: (a -> b) -> [a] -> [b]
map _ []       = []
map f (x : xs) = f x : map f xs

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:

instance Functor [] where
  fmap = map

Other examples of Functor instances include trees:

-- a simple binary tree
data Tree a = Leaf a | Fork (Tree a) (Tree a)

instance Functor Tree where  
  fmap f (Leaf x) = Leaf (f x)
  fmap f (Fork l r) = Fork (fmap f l) (fmap f r)

Mapping over a tree yields:

>>> fmap square (Fork (Fork (Leaf 1) (Leaf 2)) (Fork (Leaf 3) (Leaf 4)))
Fork (Fork (Leaf 1) (Leaf 4)) (Fork (Leaf 9) (Leaf 16))

For every instance of the Functor type class, fmap is contractually obliged to obey the functor laws:

fmap id      ≡ id              -- identity law
fmap (f . g) ≡ fmap f . fmap g -- composition law

where . denotes function composition in Haskell.

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

Moreover, if $F$ and $G$ are two functors, a natural transformation is a function of polymorphic type $h:\forall T.F(T)\to G(T)$ which respects $fmap$ :

h_{Y}\circ \operatorname {fmap} (f)=\operatorname {fmap} (f)\circ h_{X}

for any function

f:X\to Y

.

If the $h$ function is defined by parametric polymorphism as in the type definition above, this specification is always satisfied.

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, $\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.^[1]

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.

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

Language comparison

References

^ "Map fusion: Making Haskell 225% faster"

[1] "Map fusion: Making Haskell 225% faster"

[1]