A Small Adventure In Functors
Published on
The function composition operator in Haskell, i.e. (.)
, is much more
complicated than at first sight, or rather, the function composition operator
plus the type system and default currying of functions. The simple case is,
well, simple, as this function that joins integers into a string demonstrates:
--concatenate a list of integers
concatIntegers :: [Integer] -> String
concatIntegers = concat . map show
Once Haskell type unification does its magic, the types of the functions and the composition operator fit like hand and glove:
map show :: Show a => [a] -> [String]
concat :: [[a]] -> [a]
(.) :: (b -> c) -> (a -> b) -> (b -> c)
a
in the type of map show
is matched to Integer
, and [String]
, which is
in fact [[Char]]
is mapped to the first argument of concat
, leading to the
final output of [Char]
. So far so simple.
Things get rather complicated when currying and more complicated types come into the picture, though. I ran into one such case recently while trying to complete the exercises of the CIS lectures. The homework for week 10 requires you to write a functor instance for the following Parser type:
newtype Parser a = Parser { runParser :: String -> Maybe (a, String) }
This is a relatively straightforward task for which my solution was also straightforward, from a Python dev’s perspective:
first :: (a -> b) -> (a,c) -> (b,c)
first f (a,c) = (f a, c)
instance Functor Parser where
fmap f parser = Parser (\string -> (first f) <$> (runParser parser string))
The first
function was given as a tip in the task. The solution was included
as a part of the homework for week 11, and it looked radically different from
mine:
first :: (a -> b) -> (a,c) -> (b,c)
first f (x,y) = (f x, y)
inParser f = Parser . f . runParser
instance Functor Parser where
fmap = inParser . fmap . fmap . first
Well, at least the implementation of first
is the same. The implementation of
fmap
for Parser
here is in the celebrated point-free
style which takes a while to
get used to, but once you understand it, makes a whole lot of sense. I had to go
through a pretty detailed step-by-step analysis of fmap
for Parser
to get
how it’s constructed, and the kind of thinking required to write such code; read
on if you’re interested.
inParser
is superficially similar to the simple composition example above, but
fmap
is a totally different game. To understand it, let’s look at each
composition separately. The first one is fmap . first
; here are the types of
the individual functions:
first :: (a -> b) -> (a, c) -> (b, c)
fmap :: Functor f => (a -> b) -> f a -> f b
How is fmap
mapped on to first
? They both receive three arguments, but
(.)
, whose type is (b -> c) -> (a -> b) -> (b -> c)
(repeating because it’s
worth memorizing), combines functions with two arguments. The secret here is in
that Haskell functions are curried by default. When they are passed two or more
arguments, it is allright to think of functions like first
and fmap
as
functions with two arguments, but in higher-order contexts like this one, you
have to keep in mind that you can think of first
as a function that receives
one argument of type (a -> b)
, returning a function of type (a, c) -> (b,
c)
. The same thing is valid for fmap
: The output of first
with only one
argument (b
in the type of (.)
) is the first argument of fmap. This is where
the type system of Haskell comes into play, unifying the types (a,c) -> (b,c)
and (a -> b)
, so that the first argument to fmap becomes (a,c) -> (b,c)
. The
type of the first composition is thus the following:
ghci> :t fmap . first
fmap . first :: Functor f => (a -> b) -> f (a, c) -> f (b, c)
There are two more compositions to go. What does the second fmap
composition
do? There are two kinds of answers to this question: What does it
programmatically do (at the level of types and transformations), and how should
we think about it to write and understand similar code (aka functional
thinking)? We can figure out the programmatic part again by treating the output
of the second component of the composition (now fmap . first
) as the first
argument to fmap, and type-matching. So now f (a, c) -> f (b, c)
has to be
mapped to (a -> b), where we end up with a
matched to f (a, c)
and b
matched to f (b, c)
. The result of this second fmap is the following (to be
referred to as S1 later):
ghci> :t fmap . fmap . first
fmap . fmap . first
:: (Functor f1, Functor f) =>
(a -> b) -> f (f1 (a, c)) -> f (f1 (b, c)) -- [S1]
The functional thinking part has to wait for the last composition, because the
types are determined right to left ((.)
is right-associative), but
functionality is built left to right, since the end result is determined by the
last application. If you look at the type of inParser
in ghci, you might get a
bit confused:
inParser
:: ((String -> Maybe (a1, String)) -> String -> Maybe (a, String))
-> Parser a1 -> Parser a
What the hell is this supposed to be? And how is it going to match the output
type of fmap . fmap . first
? Let’s start by understanding what inParser
does. It takes a pretty complicated function (the argument f
), and a parser,
and returns another parser. The complicated function f
has the following
signature:
((String -> Maybe (a1, String)) -> String -> Maybe (a, String)) -- S2
and is supposed to modify the function that the first Parser wraps. As a reminder, this wrapped function has the following signature:
runParser :: String -> Maybe (a, String)
This is also the first argument of the complicated function, which, only with
this first argument, returns another function. So we’re talking about a function
that gets a function as an argument, and returns another function with the same
signature. We can see this better if we regroup the arguments of f
:
((String -> Maybe (a1, String)) ->
(String -> Maybe (a, String)))
This signature has to match the return value of fmap . fmap . first
. As you
can remember, that was f (f1 (a, c)) -> f (f1 (b, c))
. This is not possible
without functions being functors themselves, which they in fact
are:
instance Functor ((->) r) where
fmap = (.)
And fmap is nothing other than function composition itself! Nice plot twist
there, no? We can make sure that the first fmap is getting applied to a function
instance of functor by replacing it with (.)
, and checking the type of the
resulting composition:
ghci> :t inParser . (.) . fmap . first
inParser . (.) . fmap . first :: (a1 -> a) -> Parser a1 -> Parser a
Good to know I’m not making stuff up. Keep in mind that the functor instance for
function definition is made for ((->) r)
, fixing the first argument and
polymorphic on the second (or rest, to be more precise). This means that f1
in
S1 is matched to the second argument of the individual functions in S2, namely
to Maybe (a, String)
. Maybe
is of course also a functor, which takes care of
the next functor instance in S1. We end up with the following signature instead
of S1:
((String -> Maybe (a1, String)) -> String -> Maybe (a, String))
And the following actual implementation:
(Functor f1) => (.) (maybeFmap (a, c)) -> (.) (maybeFmap (b, c))
maybeFmap
refers to the fmap of Functor instance for Maybe.
Now we can also grasp the kind of functional thinking that leads to the double
fmap
s. Texts on functors usually focus on how they are kinds of “containers”
or “context providers” where operating on the value contained within requires a
special access method that preserves the context, best examplified by Maybe a
.
If you think of the functor instance for function creation, though, it becomes
obvious that functors go beyond containers. Functors are an abstract
relationship between two types, where one is restricting how to compose on the
second. When you are trying to reach into a parametric type and act on the inner
type, and if one of the common abstract relationships such as functors is
defined, it is possible to write code that is simpler in terms of new
definitions. Instead of parsing a new function, you need only to be acquianted
with standard ways of composing. In the case of that second fmap
that turns
out to be function composition, I wrote a function that executes the function
wrapped by Parser
and wraps its result. An experienced Haskell developer, on
the other hand, sees the commonality between manipulating the result of a
function, and what is inside a Maybe
,and uses the same interface for both.
Functional programming is more than being able to pass functions as arguments; it’s about treating behavior the same way as data structures, in fact turning functions into structures that we can reason about as we do with data.