One of the things that surprised me while studying Haskell is that `(->) a`

is a monad. It seems reasonable that functions form a monad, but I don’t believe I would have thought of it myself. How can this monad be used? An example, namely, `join (***)`

, was considered in a previous post. But when I think monads in Haskell I, think of `do`

notation. In this post we will define the `(->) a`

monad ourselves and explored a bit of the weirdness of its `do`

notation.

```
{-# LANGUAGE FlexibleInstances #-}
{-# LANGUAGE UndecidableInstances #-}
module Arrow where
import Prelude hiding (Functor(..), Applicative(..), Monad(..))
```

We hide `Functor`

, `Applicative`

, and `Monad`

because we will implement our own hierarchy, similar to the one before the functor-applicative-monad proposal. `FlexibleInstances`

and `UndecidableInstances`

will be necessary for later shenanigans.

First, we define `Functor`

and an instance of it for our monad. `fmap`

is just `(.)`

, pretty lame.

```
class Functor f where
fmap :: (a -> b) -> f a -> f b
instance Functor ((->) a) where
fmap = (.)
```

This can be easily excused, however. Lists are another type constructor that have this problem (`fmap`

is just `map`

, boring!), yet their monad instance simulates nondeterministic computations (awesome!).

Let’s continue with the `Applicative`

instance:

```
class Functor f => Applicative f where
pure :: a -> f a
(<*>) :: f (a -> b) -> f a -> f b
instance {-# OVERLAPPING #-} Applicative ((->) a) where
pure = const
f <*> g = \x -> f x (g x)
```

Things have certainly got a lot more interesting. `(<*>)`

and `pure`

are the S and K combinators from the SKI combinator calculus!

(The reason why the applicative instance of `(->) a`

is `OVERLAPPING`

will become clear later.)

With them, we can define the I combinator:

```
k :: a -> b -> a
k = pure
i :: a -> a
i = k <*> k
```

With applicative functors out of our way, we define a monad instance for `(->) a`

which will give us access to that sweet `do`

notation. Hopefully, things are about to get exciting.

```
class Functor m => Monad m where
return :: a -> m a
(>>=) :: m a -> (a -> m b) -> m b
instance Monad ((->) a) where
return = const
f >>= g = \x -> g (f x) x
```

Oh, no! Things have got kind of boring again! `(>>=)`

is just the S combinator with shuffled parameter order! And indeed, `(>>=)`

could have been implemented in terms of S and K:

```
instance Monad ((->) a) where
return = const
(>>=) = s (k (s (k (s (k (s s (s k))))) (s (s (k s) k)))) k
```

Yet another possible implementation (thanks to Brad Neimann):

```
instance Monad ((->) a) where
return = const
f >>= g = flip g <*> f
```

With the monad instance, we finally acquired `do`

notation, which allows us to write some weird things:

```
s :: (a -> b -> c) -> (a -> b) -> a -> c
s x y = do
x <- x
y <- y
return (x y)
```

which desugars to:

```
s :: (a -> b -> c) -> (a -> b) -> a -> c
s x y = x >>= \x -> y >>= \y -> return (x y)
```

which is just a default implementation of `(<*>)`

for any given monad:

```
instance {-# OVERLAPPABLE #-} (Functor m, Monad m) => Applicative m where
pure = return
f <*> x = f >>= \f -> x >>= \x -> return (f x)
```

This applicative instance is the reason for the extensions and the `OVERLAPPING`

in the applicative instance of `(->) a`

.

I didn’t manage to think of any useful examples of `do`

notation for the `(->) a`

monad. If you know of any, please let me know on Twitter. I would love to see more of this unexpected monad.

Special thanks to the wonderful folks at the Functional Programming Zulip.