Map (higher-order function)

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 .