Hidden structure

The unexpected similarities between mapping over a list and function composition

Trying to understand functors, I came accross the initially strange fact that functions are functors. Which means, roughly speaking, you can "map", another function over it. So given a function

g :: r -> a

and another function

f :: a -> b

you can "map" the second function over the first to get another function, which is defined as the composition of the two.

fmap f g :: r -> b
fmap f g = f . g

Similarly, and more familiarly, you can take a list

xs :: [a]

and a function

f :: a -> b

and map the function over the list to get another list.

fmap f xs :: [b]
fmap f xs = [f x | x <- xs]

(I suspect this isn't how fmap is defined on a list in the real source, but I find list comprehensions quite easy to understand.)

The suprising thing is that you can express two seemingly very different activities, mapping a function over a list, and composing a function with another function, in Haskell using the same function: fmap. Here "the same" is defined as having the same type signature.

fmap :: Functor f => (a -> b) -> f a -> f b

Although yes, the implementation of fmap for functions and lists are indeed different.