Haskell functions as functors, applicatives and monads

Function as an instance of Functor

class Functor f where
  fmap :: (a -> b) -> f a -> f b

Types parameterized by a single type can be instances of Functor if they implement fmap in a way that follows the functor laws. The simplest example is Maybe; Maybe is a type parameterized by a single type (also known as type constructor):

data Maybe a = Nothing | Just a

Maybe is a Functor:

instance Functor Maybe where
  -- fmap :: (a -> b) -> Maybe a -> Maybe b
  fmap _ Nothing = Nothing
  fmap g (Just x) = Just (g x)

So what about functions? In general, a function (->) is parameterized by two types: a -> b or alternatively (->) a b - both a (the function argument) and b (the function return value) can have arbitrary types for an arbitrary function. So functions aren't a good fit for Functor, unless we tweak something.

The tweak is to fix the argument type, leaving only the return type arbitrary. This is written as (->) a, a type parameterized by a single type - the return value (the argument type is fixed at a). Haskell type constructors can be partially applied, same as functions. As an example, consider Either, which is a type constructor parameterized by two types [1]:

> :kind Either
Either :: * -> * -> *

If we partially apply the Either type constructor we get another type constructor, this time with a single type parameter:

> :kind Either Int
Either Int :: * -> *

Similarly, we can check the kind of functions:

> :kind (->)
(->) :: * -> * -> *

And of partially-applied functions:

> :kind ((->) Int)
((->) Int) :: * -> *

Before showing how (->) a is an instance of Functor, let's reformulate it in a slightly more explicit way. Let's use FuncWithArgA to name the concept of "a function with argument of type a". This type is parameterized by a single type: b, the return value type.

So if we had to make FuncWithArgA an instance of Functor, the type of fmap would be:

fmap :: (b -> c) -> FuncWithArgA b -> FuncWithArgA c

That is, we map a function b -> c onto FuncWithArgA b to produce FuncWithArgA c. Now if we go back to the actual type of functions parameterized by the return type, we get:

fmap :: (b -> c) -> ((->) a) b -> ((->) a) c

... or

fmap :: (b -> c) -> (a -> b) -> (a -> c)

So this should be the type of fmap for functions. One way to make this work would be [2]:

instance Functor ((->) a) where
  fmap g ff = \x -> g (ff x)

Let's follow the types: ff is our functor - it's a function a -> b. The mapped function g is b -> c. Hence, the result of fmap is a function taking a and returning c, or a -> c, so this matches the expected type.

Note that \x -> g (ff x) is precisely the composition of g onto ff, or g . ff in Haskell notation. So being extra clever, we can use point-free notation to rewrite our Functor instance as:

instance Functor ((->) a) where
  fmap = (.)

Now it's time for an example. Let's take the function replicate:

replicate :: Int -> a -> [a]

By itself, replicate has two arguments, so it's not a good match for our Functor. But if we partially apply it, it will be. Say replicate 4. Its type is:

> :t replicate 4
replicate 4 :: b -> [b]

replicate 4 is a function a single parameter - a perfect fit for Functor. So we can use fmap on it! Let's fmap the function show on it. show takes any "showable" type and produces String. Therefore:

> :t fmap show (replicate 4)
fmap show (replicate 4) :: Show a => a -> String

Let's check the type of fmap:

• replicate 4 is b -> [b]
• show is Show a => a -> String; in this case [b] -> String
• So fmap show (replicate 4) is b -> String, via function composition

We can try it on different types:

> fmap show (replicate 4) 5
"[5,5,5,5]"
> fmap show (replicate 4) (Just 6)
"[Just 6,Just 6,Just 6,Just 6]"

Functor laws for functions

To be a proper Functor in Haskell, it isn't sufficient to define a Functor instance that type-checks. In addition, the definition has to satisfy the functor laws:

fmap id = id
fmap (g . h) = fmap g . fmap h

Explaining how the Functor instance for functions shown above satisfies these laws is a great exercise in mind-bending Haskell notation, and really stresses our grasp of types and type constructors. Let's get to it.

Two factors that make such derivations difficult to follow for beginners in Haskell are point-free style and currying. As an example, what does fmap id mean [3]?

We know that fmap takes two arguments: a mapped function and the functor. fmap id is partially applied, or curried - it's another function that already accounts for the mapped function so it only takes a single argument - the functor. All Haskell functions are curried by default, so any multi-argument function can be expressed as a single-argument function returning a function. In the case of fmap:

fmap g ff = \x -> g (ff x)

... can be written as

fmap g = \ff -> \x -> g (ff x)

This helps, because now we can write down what fmap id is:

fmap id = \ff -> \x -> id (ff x)

... or

fmap id = \ff -> \x -> ff x

And this is exactly id, because it takes ff and returns a function that takes an argument and applies ff to it - which is just ff itself. So the first functor law holds. Let's take a look at the second one:

fmap (g . h) = fmap g . fmap h

As before, fmap (g . h) can be written more explicitly as:

fmap (g . h) ff = \x -> (g . h) (ff x)
                = \x -> g (h (ff x))

On the other hand:

(fmap g . fmap h) ff
  = fmap g (fmap h ff)

  ... by definition of "fmap h ff"

  = fmap g (\x -> h (ff x))

  ... by definition of "fmap g ff" for ff now being (fmap h ff)

  = \y -> g ((\x -> h (ff x)) y)
  = \y -> g (h (ff y))

So the second law holds as well, meaning that our Functor instance for functions is legitimate.

Function as an instance of Applicative

Let's now move on to how functions are defined to be instances of Applicative. A reminder:

class Functor f => Applicative f where
  pure :: a -> f a
  (<*>) :: f (a -> b) -> f a -> f b

Let's start by figuring out the types of these methods in a function instance, using the helper FuncWithArgA substitute.

pure :: b -> FuncWithArgA b

Replacing FuncWithArgA by (->) a, we get:

pure :: b -> (a -> b)

A function that satisfies this type is:

pure = \x -> (\y -> x)

This is a very peculiar function, you'll notice. It takes two arguments and returns the first, completely ignoring the second. Haskell already has such a function in the standard library, it's called const:

> :t const
const :: a -> b -> a
> :t const 10
const 10 :: Num a => b -> a
> (const 10) "foo"
10
> (const 10) (Just 20)
10

Using point-free style, pure is defined as:

pure = const

Now let's turn our attention to the <*> operator. Once again, we'll be using FuncWithArgA; to make it more readable I'll rename the types in the declaration of <*>, since a is already implied in FuncWithArgA:

(<*>) :: FuncWithArgA (b -> c) -> FuncWithArgA b -> FuncWithArgA c

.. replacing FuncWithArgA by ((->) a)

(<*>) :: (a -> (b -> c)) -> (a -> b) -> (a -> c)

A definition that satisfies this type is:

g <*> h = \x -> g x (h x)

The type of g is a -> b -> c and the type of h is a -> b; hence, for a parameter of type a, the type of the expression is indeed a -> c.

To conclude, the Applicative instance for functions looks like this:

instance Applicative ((->) a) where
  pure = const
  g <*> h = \x -> g x (h x)

Applicative laws for functions

Let's see how the instance defined satisfies the applicative laws:

pure id <*> x = x
pure (g x) = pure g <*> pure x
x <*> pure y = pure (\g -> g y) <*> x
x <*> (y <*> z) = (pure (.) <*> x <*> y) <*> z

Starting with the first law [4]:

pure id <*> x

.. by definition of pure

(\x -> (\y -> x)) id <*> x
(\y -> id) <*> x

.. by definition of <*>, with (\y -> id) for g and x for h

\z -> (\y -> id) z (x z)

.. using partial function application

\z -> id (x z)
\z -> x z

Which is just another way of saying x - a function taking a single parameter and applying x to it. The first law holds! For the second law:

pure (g x)

.. by definition of pure

\y -> g x

Right-hand side:

pure g <*> pure x

.. by definition of pure

\y -> g <*> \z -> x

.. by definition of <*>

\t -> (\y -> g) t ((\z -> x) t)
\t -> (\y -> g) t x
\t -> g x

The third law, left-hand side:

x <*> pure y
x <*> \z -> y

.. by definition of <*>

\t -> x t ((\z -> y) t)
\t -> x t y

Right-hand side:

pure (\g -> g y) <*> x
\z -> (\g -> g y) <*> x

.. by definition of <*>

\t -> (\z -> (\g -> g y)) t (x t)
\t -> (\g -> g y) (x t)
\t -> x t y

The fourth law, left-hand side:

x <*> (y <*> z)
x <*> (\t -> y t (z t))
\g -> x g ((\t-> y t (z t)) g)
\g -> x g (y g (z g))

Right-hand side:

(pure (.) <*> x <*> y) <*> z
((\t -> (.) (x t)) <*> y) <*> z
(\g -> ((.) (x g)) (y g)) <*> z
\v -> x v ((y v) (z v))

Function as an instance of Monad

Finally, let's see how functions are instances of Monad, which is defined as:

class Applicative m => Monad m where
  return :: a -> m a
  (>>=) :: m a -> (a -> m b) -> m b

For functions, starting with the FuncWithArgA helper:

return :: b -> FuncWithArgA b

Which, as for Applicative has the type:

b -> a -> b

Which is satisfied by the same function, const:

return = const

Now, on to >>=:

>>= :: FuncWithArgA b -> (b -> FuncWithArgA c) -> FuncWithArgA c

.. Unpacking the ``FuncWithArgA`` helper:

>>= :: (a -> b) -> (b -> (a -> c)) -> (a -> c)
>>= :: (a -> b) -> (b -> a -> c) -> (a -> c)

A definition that satisfies this type is:

g >>= h = \x -> h (g x) x

Monad laws for functions

The monad laws are:

return x >>= f = f x
mx >>= return = mx
(mx >>= f) >>= g = mx >>= (\x -> (f x >>= g))

Let's start with the first law. Left-hand side:

return x = \y -> x
return x >>= f = \t -> f ((\y -> x) t) t
               = \t -> f x t

This is equivalent to f x, which is in point-free style. The left-hand side for the second law:

mx >>= return = \t -> return (mx t) t

              .. by definition of return, returns the first argument whenever
                 applied.

              = \t -> mx t

This can be written as just mx in point-free style. Finally, the third law. Left-hand side:

(mx >> f) >>= g = (\x -> f (mx x) x) >>= g
                = \t -> g ((\x -> f (mx x) x) t) t
                = \t -> g (f (mx t) t) t

Right-hand side:

mx >>= (\x -> (f x >>= g)) = mx >>= (\x -> (\t -> g (f x t) t))
                           = \z -> (\x -> (\t -> g (f x t) t)) (mx z) z
                           = \z -> (\t -> g (f (mx z) t) t) z
                           = \z -> g (f (mx z) z) z

Which is equivalent, modulo the renamed bound variable.

Real-life applicability

Now that we've persevered through the derivations, what practical uses does this technique have? I was wondering the same, so I created a Stack Overflow question that got a couple of answers. The main idea is that it lets us compose functions more succinctly, using more Haskell-y point-free style instead of explicitly creating functions with named parameters.

Consider the following example, taken from the top answer in the linked question. Here's a way to find whether a sequence is ascending:

> and $ (\x -> (zipWith (<=) x (drop 1 x))) [1,2,6,4]
False
> and $ (\x -> (zipWith (<=) x (drop 1 x))) [1,2,6,9]
True

Note that we create an explicit lambda for combining zipWith with its parameters in the right way. Using applicative style, we don't need it and can write the code more succinctly [5]:

> and $ (zipWith (<=) <*> drop 1) [1,2,6,4]
False
> and $ (zipWith (<=) <*> drop 1) [1,2,6,9]
True

Note how this achieves the same, but without the explicit lambda. <*> does the functional composition for us. As an exercise, follow the types of the sub-expressions in the <*> to see how this works.

Is this something you'd use in real programs? Maybe, maybe not. I think it depends on personal and project style. The first (non-applicative) option certainly looks more readable to me, but that's because I'm far from being a Haskell pro. Seasoned Haskellers may find the latter more stylistically appealing because it's more point-free, without naming parameters explicitly.