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 input
    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)