Part 1 - Exploring the Haskell Functor
Dec 3, 2020 · 6 minute readCategory: programming
Tags: haskell
Words: 1398
Part 1 of a series exploring Functors, Applicatives and Monads
The is part of a 3 part series of Functors, Applicatives and Monads in Haskell:
- This Part - Exploring the Haskell Functor
- Part 2 - Exploring the Haskell Applicative Functor
- Part 3 - (Finally) exploring the Haskell Monad
So this article is a workthrough of what a Functor is, as I try to develop an intuition for what they are. The Wikipedia definition is a little opaque, unless you have a really good grasp of mathematics, and in particular, Category Theory:
In mathematics, specifically category theory, a functor is a map between categories.
But what does this actually mean?
In order to approach this, we'll explore it from a couple of angles, but the simplest to start with is Haskell.
Haskell Functor
Definition
So in Haskell, a Functor is a type that (minimally) has an fmap
instance. To be a proper functor it also needs to obey some laws. And that's basically it. So at it's simplest:
class Functor f where
fmap :: (a -> b) -> f a -> f b
(<$) :: a -> f b -> f a
Recall that a functor is "a map between categories", and note the fmap
type definition above. In words, fmap
takes a (function that takes a value of type a
and returns a value of type b
) and a thing f a
, and returns an f b
thing. The f
is the type that has the functor instance. Before exploring that, let's look at the laws that the Haskell Functor instance should have:
Laws
The laws are really important. They define how fmap
functions must behave in order to be composable. And in Haskell, composition is a defining aspect of producing programs.
Functors must preserve identity morphisms
fmap id == id
Or, to put it another way, id
is the identity function, and whatever you pass to it, you get back. Thus, the above says that the function fmap id
must do the same thing has just applying id
.
If it looks a bit odd, remember that in Haskell, all functions take one parameter and return a parameter. The ->
is the function, or morphism. Thus, take a look at the type signature of fmap
again:
fmap :: (a -> b) -> f a -> f b
It looks like fmap takes two parameters, but the hint is in the ->
(morphism) or function sigil. fmap
is actually a function that takes a function ((a -> b)
) and returns a function that takes an f a
and returns an f b
(or as a haskell function: f a -> f b
). Or to put it another way:
fmap :: (a -> b) -> (f a -> f b)
So the first law really says that fmap id
must be identical to id
i.e.
fmap id :: f a -> f a -- but with the proviso that they are the SAME a
-- (value)
Functors preserve composition of morphisms
fmap (h . g) == fmap h . fmap g
Normally, this would be written as fmap (f . g) ...
, but that would be confusing with the f
meaning functor above, so we'll use h
instead in this description.
Recall that (.)
is the composition function, and h . g
reads as h after g or h (g a)
. i.e. h
is applied to the return value of g
applied to a
.
. g -- the composition of h and g which becomes:
h -> c) . (a -> b) -- and simplifies to this:
(b -> c) (a
Or h . g
is the function a -> c
or what the composed "h after g" function does
i.e. h
is the function (b -> c)
, g
is the function (a -> b)
and the return value is a function (a -> c)
. Note that the last function doesn't have braces, which is just a convention. It could be written like:
. g === (b -> c) -> (a -> b) -> (a -> c) h
So we have, in terms of function type declarations, where a
, b
and c
are polymorphic types, g
and h
are functions of one parameter, and f
is a type that is an instance of the type class Functor:
h :: b -> c
g :: a -> b
. g === (b -> c) . (a -> b) === (a -> c)
h . g :: a -> c
h fmap h :: Functor f => f b -> f c
fmap g :: Functor f => f a -> f b
-- and thus, by substition
fmap (h . g) === f a -> f c
-- and with a bit of working:
fmap h) . (fmap g) === f a -> f c
(-- i.e. substituting (fmap h) and (fmap g) we get the identity:
-> f c) . (f a -> f b) === f a -> f c (f b
(Note that the ===
isn't valid Haskell; it's just me writing that they are the same thing.)
So that's the laws. Still wondering what a functor is?
Developing the intuition
So by now you may be thinking that the fmap
function is the functor? Let's see if that fits. A functor is a map between categories, so in theory a functor (i.e. the function) should take a category as a parameter and return a category.
In Haskell, the Functor type class constrains it to be the same category. In this case, category is actually the type that has an instance in the Functor type class. So in fmap
:
fmap :: Functor f => (a -> b) -> f a -> f b
And therefore, if you squit hard enough, the category is f
. So (for the Haskell implementation) what is the functor? It's fmap fn
where fn
is that function:
fn :: (a -> b)
-- and
fmap fn :: Functor => f a -> f b
And this fmap fn
obeys the laws that we discussed above. So what are fmap
and fn
? Well, fn
is whatever mapping that you want the particular functor to do. It operates on the thing (conceptually) inside the category. i.e. the objects that inhabit the category. Or more concretely, in Haskell, the values inside the type that has a Functor instance. And the fmap
is the implementation function that 'knows' how to get at the values inside the type; so fmap
is a different, concrete, function for each Functor instance. Which is why we have to define an fmap
for each type!
Some examples
These are the really easy, and frequently quoted, examples, but they should serve to embed the concept; the Maybe
and []
(list) types. First the Maybe
type:
Recall that:
data Maybe a = Just a | Nothing
i.e. the Maybe
type is either a Just <something>
or a Nothing
.
instance Functor Maybe where
fmap fn (Just x) = Just (fn x)
fmap _ Nothing = Nothing
Thus, above fn
is the mapping function, so basically this is saying fmap
applies fn
to the x
inside the Maybe
if it is a Just x
, or preserves the Nothing
if the Maybe
is a Nothing. Let's apply doubling to a Maybe
value:
*2) :: Num a => a -> a
(fmap (*2) :: Functor f => f a -> f a
-- therefore
fmap (*2) (Just 1)
=> Just 2
What about lists?
instance Functor [] where
fmap _ [] = []
fmap fn (x:xs) = fn x : fmap fn xs
Basically, the same pattern exists, the fn
function is applied to the things inside the structure. And this is a pattern that repeats, across all the of the types that are instances of the Functor type class. Crucially, an important fact arises:
The structure of the type remains unchanged; the morphisms only occur to the objects inside the structure.
And this is an important aspect of the Functor and fmap
the morphism (change) is applied to the 'contents'.
Comments are disabled for this page.