# The Function Monad

## A Refresher on Monads

Via the `Box` type, we originally learned what a `Monad` even is. To refresh our memory, a data type can be called a `Monad` if it can implement a law-abiding instance for the `Monad` type class. We then used the `Box` type to introduce "do notation," which desugars into nested `bind`/`>>=` calls.

We later showed that using other monadic types like `Maybe`, `Either`, and `List` led to different control flows. `Maybe` led to a nested if-then-else statement. `Either` was similar but returned something when an error occurred. `List` produced a nested `for` loop.

However, we never stopped to consider the data type, `Function`. When we re-examine the `Function` data type, we'll see that it's naturally a `Monad`.

## Reviewing `Function` as a Data Type

Putting it into syntax, `Function` is defined like this:

``````data Function a b = -- implementation

infix ? Function as ->

-- Thus, when we write this:
intToString :: Int -> String
intToString _ = "a string"

-- It desguars to this:
intToString :: Function Int String
intToString _ = "a string"
``````

## Implementing the `Monad` Type Class Hierarchy's Functions

Let's start implement instances for these type classes. For now, take my word for it that these implementations satisfy the laws of their respective type classes.

### Functor

#### Initial Problems

Let's look at `Functor`. It's type signature looks like this.

``````class Functor f where
map :: forall a b. (a -> b) -> f a -> f b
``````

This creates the first problem: `Functor` expects a higher-kinded type, `f`, that only takes one type. For example, `Box a` only takes one type. However, `Function a b` takes two types. So, how can this be resolved? We must assume that `Function a b` already has its first type. For example...

``````data Function a b = -- implementation

noTypesDefined :: forall a b. Function a   b
noTypesDefined = -- implementation

oneTypeDefined :: forall   b. Function Int b
oneTypeDefined = -- implementation

allTypesDefined ::            Function Int Int
allTypesDefined = -- implementation
``````

To make `Function` higher-kinded by only one type, and not two, we should use something like `oneTypeDefined` above:

``````class Functor (Function inputType) where
``````

#### Implementing `map`

Getting back to the problem at hand, here's the type signature for Function's `map` implementation with very helpful names:

``````class Functor (Function inputType) where
map :: forall originalOutputType newOutputType.
(originalOutputType -> newOutputType) ->
Function inputType originalOutputType -> Function inputType newOutputType
``````

It should seem pretty obvious how this gets implemented. Let's walk through this slowly.

1. `map` returns a new function whose input is `input`. So, let's use an inline function to do that:
``````class Functor (Function inputType) where
map :: forall originalOutputType newOutputType.
(originalOutputType -> newOutputType) ->
Function inputType originalOutputType -> Function inputType newOutputType
map originalToNew f = (\input -> {- remaining body of function -} )
``````
1. Since `f` is the only function that can "receive" a value of type, `input`, we have to pass that value into `f`. `f` will produce `originalOutput`, so let's store that in a let binding:
``````class Functor (Function inputType) where
map :: forall originalOutputType newOutputType.
(originalOutputType -> newOutputType) ->
Function inputType originalOutputType -> Function inputType newOutputType
map originalToNew f = (\input ->
let originalOutput = f input
in {- remaining body of function -} )
``````
1. Since `originalToNew` is the only function that can "receive" a value of type, `originalOutput`, we have to pass the value outputted by `f` into that function. `originalToNew` produces a value of the type, `newOutput`, which gives us the return value of our created function:
``````class Functor (Function inputType) where
map :: forall originalOutputType newOutputType.
(originalOutputType -> newOutputType) ->
Function inputType originalOutputType -> Function inputType newOutputType
map originalToNew f = (\input ->
let originalOutput = f input
in originalToNew originalOutput)
``````

As we can see, the types guided us on how to implement this function. If we look at this closer, we can see that it's just function composition.

``````class Functor (Function inputType) where
map :: forall originalOutputType newOutputType.
(originalOutputType -> newOutputType) ->
Function inputType originalOutputType -> Function inputType newOutput
map originalToNew f = (\input -> originalToNew \$ f input)
-- or
map originalToNew f = (originalToNew <<< f)
-- or even
map = (<<<)
``````

In real code, normally we use `a`, `b` as type variable. Therefore, the above snippet will be simplfied to

``````class Functor (Function i) where
map :: forall a b. (a -> b) -> Function i a -> Function i b
map = (<<<)
``````

#### Takeaways

Our first example taught us two things:

• we have to make `Function` higher-kinded by one less type by specifying its first type (the input) and let the `a` and `b` arguments refer to its second type (the output).
• to implmement the instance, we have to create a new function by using lambda syntax: `\argument -> body`

### Apply

#### Initial Problems

Let's now look at `Apply`'s `apply` function. It's type signature looks like this.

``````class (Functor f) <= Apply f where
apply :: forall a b. f (a -> b) -> f a -> f b
``````

Again, let's take this slowly. Notice first the first argument, what should the full type signature of `f (a -> b)` be if `f` is `Function`? Since the `f` has to be the same for both situations, then `f` has to be `Function input`. In other words, the first argument is a function that returns another function:

``````class (Functor (Function inputType)) <= Apply (Function inputType) where
apply :: forall originalOutputType newOutputType.
Function inputType (originalOutputType -> newOutputType) ->
Function inputType  originalOutputType ->
Function inputType  newOutputType
``````

#### Implementing `apply`

Let's see how to implement this function.

1. Since `apply` returns a new function, let's start creating one using lambda syntax:
``````class (Functor (Function inputType)) <= Apply (Function inputType) where
apply :: forall originalOutputType newOutputType.
Function inputType (originalOutputType -> newOutputType) ->
Function inputType  originalOutputType ->
Function inputType  newOutputType
apply functionInFunction f = (\input -> {- body of function -})
``````
1. At this point, both `f` and `functionInFunction` can receive an value of type, `input`. For right now, let's do what we did last time and only pass it into `f`. We'll store the output in a let binding:
``````class (Functor (Function inputType)) <= Apply (Function inputType) where
apply :: forall originalOutputType newOutputType.
Function inputType (originalOutputType -> newOutputType) ->
Function inputType  originalOutputType ->
Function inputType  newOutputType
apply functionInFunction f = (\input ->
let originalOutput = f input
in {- body of function -})
``````
1. At this point, the only way to get map `originalOutput` into `newOutput` is to pass it into the function that's hidden in `functionInFunction`. How do we get that out? We can pass `input` into that function. Again, we'll store that output in a let binding:
``````class (Functor (Function inputType)) <= Apply (Function inputType) where
apply :: forall originalOutputType newOutputType.
Function inputType (originalOutputType -> newOutputType) ->
Function inputType  originalOutputType ->
Function inputType  newOutputType
apply functionInFunction f = (\input ->
let
originalOutput = f input
originalToNew = functionInFunction input
in {- body of function -})
``````
1. We now have all the pieces we need to return `newOutput`. Let's pass `originalOutput` into `originalTonew`:
``````class (Functor (Function inputType)) <= Apply (Function inputType) where
apply :: forall originalOutputType newOutputType.
Function inputType (originalOutputType -> newOutputType) ->
Function inputType  originalOutputType ->
Function inputType  newOutputType
apply functionInFunction f = (\input ->
let
originalOutput = f input
originalToNew = functionInFunction input
in originalToNew originalOutput)
``````

Great! Can we clean it up now?

``````class (Functor (Function inputType)) <= Apply (Function inputType) where
apply :: forall originalOutputType newOutputType.
Function inputType (originalOutputType -> newOutputType) ->
Function inputType  originalOutputType ->
Function inputType  newOutputType
apply functionInFunction f = (\input -> (functionInFunction input) (f input))
``````

#### Takeaways

Our second example taught us the following:

• to get all the pieces necessary to implement a type class' function, we sometimes need to pass the input value into multiple functions.

### Applicative

Let's now look at `Applicative`'s `pure` function. It's type signature looks like this.

``````class (Apply f) <= Applicative f where
pure :: forall a. a -> f a
``````

Converting `f` into `Function input`, we get this type signature:

``````class (Apply (Function inputType)) <= Applicative (Function inputType) where
pure :: forall outputType. outputType -> Function inputType outputType
``````

Let's see how to implement it.

1. Since `pure` returns a new function, let's start creating one using lambda syntax:
``````class (Apply (Function inputType)) <= Applicative (Function inputType) where
pure :: forall outputType. outputType -> Function inputType outputType
pure value = (\input -> {- body of function -})
``````
1. Since the function must return `value` as its output, let's ignore the argument and just return that value.
``````class (Apply (Function inputType)) <= Applicative (Function inputType) where
pure :: forall outputType. outputType -> outputType
pure value = (\input -> value)
``````

Let's clean this one up:

``````class (Apply (Function inputType)) <= Applicative (Function inputType) where
pure :: forall outputType. outputType -> Function inputType outputType
pure value = (\_ -> value)
``````

### Bind

#### Implementing `bind`

Let's now look at `Bind`'s `bind` function. It's type signature looks like this.

``````class (Functor m) <= Bind m where
bind :: forall a b. (a -> m b) -> m a -> m b
``````

Converting `m` into `Function input`, we get this type signature:

``````class (Apply (Function inputType)) <= Bind (Function inputType) where
bind :: forall originalOutputType newOutputType.
(originalOutputType -> Function inputType newOutputType) ->
Function inputType originalOutputType ->
Function inputType newOutputType
``````

Let's see how to implement it.

1. Since `bind` returns a new function, let's start creating one using lambda syntax:
``````class (Apply (Function inputType)) <= Bind (Function inputType) where
bind :: forall originalOutputType newOutputType.
(originalOutput -> Function inputType newOutputType) ->
Function inputType originalOutputType ->
Function inputType newOutputType
bind originalToFunction f = (\input -> {- body of function -})
``````
1. Since `f` is the only function that can "receive" the `input` value, let's pass it into `f` and store the output:
``````class (Apply (Function inputType)) <= Bind (Function inputType) where
bind :: forall originalOutputType newOutputType.
(originalOutputType -> Function inputType newOutputType) ->
Function inputType originalOutputType ->
Function inputType newOutputType
bind originalToFunction f = (\input ->
let originalOutput = f input
in {- body of function -})
``````
1. Since `originalToFunction` can "receive" the `originalOutput` value, let's pass that into `originalToFunction` and store its result in a let binding:
``````class (Apply (Function inputType)) <= Bind (Function inputType) where
bind :: forall originalOutputType newOutputType.
(originalOutputType -> Function inputType newOutputType) ->
Function inputType originalOutputType ->
Function inputType newOutputType
bind originalToFunction f = (\input ->
let
originalOutput = f input
inputToNewOutput = originalToFunction originalOutput
in {- body of function -})
``````
1. Since `inputToNewOutput` is the only function that can produce the `newOutput` value, let's pass `input` into it to get that value:
``````class (Apply (Function inputType)) <= Bind (Function inputType) where
bind :: forall originalOutputType newOutputType.
(originalOutputType -> Function inputType newOutputType) ->
Function inputType originalOutputType ->
Function inputType newOutputType
bind originalToFunction f = (\input ->
let
originalOutput = f input
inputToNewOutput = originalToFunction originalOutput
in inputToNewOutput input)
``````

Let's now clean it up. First we'll get rid of that `inputToNewOutput` binding:

``````class (Apply (Function inputType)) <= Bind (Function inputType) where
bind :: forall originalOutputType newOutputType.
(originalOutputType -> Function inputType newOutputType) ->
Function inputType originalOutputType ->
Function inputType newOutputType
bind originalToFunction f = (\input ->
let
originalOutput = f input
in (originalToFunction originalOutput) input)
``````

Second, we'll get rid of that `originalOutput` binding:

``````class (Apply (Function inputType)) <= Bind (Function inputType) where
bind :: forall originalOutputType newOutputType.
(originalOutputType -> Function inputType newOutputType) ->
Function inputType originalOutputType ->
Function inputType newOutputType
bind originalToFunction f = (\input -> (originalToFunction (f input)) input)
``````

As can be seen, this example was a slightly more complicated version of `apply` in that we needed to pass `input` to multiple functions.

## Summary of Our Takeaways

• `map` example:
• we have to make `Function` higher-kinded by one less type by specifying its first type (the input) and let the `a` and `b` arguments refer to its second type (the output).
• to implmement the instance, we have to create a new function by using lambda syntax: `\argument -> body`
• `apply`/`bind` example:
• to get all the pieces necessary to return the `b`/`newOutput` value, we sometimes need to pass the `input` value into multiple functions.

## Resugaring `Function`

In our code above, we desugared `(a -> b)` into `Function a b`. What would happen if we resugared our type class instances above back into `->`? How would we write it then?

``````class Functor ((->) inputType) where
map :: forall originalOutputType newOutputType.
(originalOutputType -> newOutputType) ->
(inputType -> originalOutputType) -> (inputType -> newOutputType)
map originalToNew f = (\input ->
let originalOutput = f argument
in originalToNew originalOutput)

class (Functor ((->) inputType)) <= Apply ((->) inputType) where
apply :: forall originalOutputType newOutputType.
(inputType -> (originalOutputType -> newOutputType)) ->
(inputType -> originalOutputType) ->
(inputType -> newOutputType)
apply functionInFunction f = (\input ->
let
originalOutput = f input
originalToNew = functionInFunction input
in originalToNew originalOutput)

class (Apply ((->) inputType)) <= Applicative ((->) inputType) where
pure :: forall outputType. outputType -> (inputType -> outputType)
pure value = (\_ -> value)

class (Apply ((->) inputType)) <= Bind ((->) inputType) where
bind :: forall originalOutputType newOutputType.
(originalOutputType -> (inputType -> newOutputType)) ->
(inputType -> originalOutputType) ->
(inputType -> newOutputType)
bind originalToFunction f = (\input ->
let
originalOutput = f input
inputToNewOutput = originalToFunction originalOutput
in inputToNewOutput input)
``````