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 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. 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. Below, you can see a view of each step of the mapping process for a list of integers X = [0, 5, 8, 3, 2, 1] that we want to map into a new list X' according to the function : 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 Functor and Category theory 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 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 .