This post explores how functions in Haskell can be seen as instances of the
`Functor`, `Applicative` and `Monad` type classes, with some reflection on
the practical uses of this technique.

## 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 `b -> c`; 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.

[1] | These samples show Haskell kinds
using the :kind query in ghci. In :kind output, * denotes
concrete values (also known as nullary type contructors), * -> *
denotes a single-parameter type constructor (for example the kind of
Maybe is * -> *), and so on. |

[2] | In fact, it's not just one way to make this work; it's the only way
to make this work. Functor instances for any given type are unique
in Haskell, as long as the functor laws are satisfied. This can be proved
but is outside the scope of this article. |

[3] | Note that in the equation fmap id = id, the types of id are
different on the left and on the right. On the left, fmap id takes
a functor and returns a functor, while id takes and returns the
type parameter of the functor. In other words, for Functor a,
id on the left has type a -> a while id on the right has type
Functor a -> Functor a. |

[4] | In this derivation, and throughout the post I'm making liberal use of the
power of renaming bound variables in functions. For example I may have
a function \x -> foo x on one line, and refer to it as \y -> foo
y on another line - the two are equivalent, and this renaming helps
avoid name collisions. This is called alpha conversion in Lambda calculus. |

[5] | You'll need to import Control.Applicative to get access to the
built-in applicative instance for functions. |