Functors and other dirty words

Title: Functors and other dirty words.
Alternative title: Functors, Applicatives, and Monads, with a dash of Category Theory and a generous amount of Haskell.

Introduction

Let us consider (think of) a type. Any type that Haskell supports. Let us call this type a. This type can be any built-in Haskell type. I already said that. This type can be, for example, an Int. See what I did here? D-i-d y-o-u s-e-e w-h-a-t I d-i-d h-e-r-e? D-o I h-a-v-e t-o s-p-e-l-l i-t o-u-t f-o-r y-o-u?

OK, I’ll stop joking. But, really, did you see what I did? I wrote the type Int with a capital “i”, whereas I wrote the type a with a small letter. This is the convention. In Haskell, the capitalization (or the lack of it) of the first letter of a name, is a very important matter. In Haskell, we write specific types with their first letter capitalized. So we write Int, Float, Double, String and so on. But when it comes to denoting a generic type, we write its first letter without capitalization. So we write a, b, aType, blaBla, chicken and so on. Since the first letter is a small letter, these names denote generic types, i.e. types that can be any type. We can call these types variable types, generic types, or parametric types, in order to distinguish them from specific types.

Haskell is great because it allows us to write functions with generic types, rather than specific types. So, instead of having many versions of a function only because we want its arguments and output to be of a great variety of types, we can use generic types instead. For example, instead of having one function f1 that puts an Int into an one-element list

f1 :: Int -> [Int]
f1 x = [x]

and another function f2 that puts a String into an one-element list

f2 :: String -> [String]
f2 x = [x]

and another function f3 that puts a Double into an one-element list

f3 :: Double -> [Double]
f3 x = [x]

we can write only one function f

f :: a -> [a]
f x = [x]

that covers every case of the argument’s type and output’s type.

Although this is one of the most powerful concepts of Haskell, it is not the topic of this blog post, and I do not want to digress.

So, let us consider a type a. It can be an Int, a String, a list of Floats, whatever. And let us consider another type, b. Now, b can also be whatever type we wish. It can also be the same type as a. IT can be different than a, but it does not have to be. Equality is an option.

OK, so we have two Haskell types, a and b. Now let us consider a function a -> b. It is a function that takes an argument of type a as input and produces output of type b. Great. So we have types and we also have functions from a type to another type. We denote types by their names or generic names and we denote functions using arrows from one type to another.

Thinking in Category Theory terms, we can imagine that we have a Category whose objects are the Haskell types. Thus a is an object, a dot in this Category. b is also an object, another dot in this Category. A function a -> b is a morphism, an arrow in this Category.

So, we can think that we have a Category whose objects are the types in Haskell and whose morphisms are the functions we can create in Haskell. a and b are objects of this Category. a -> b is a morphism of this Category.

Thus a -> b is a function a Haskell, in other words, a morphism in our Category. We call a -> b a function in Haskell terms and an arrow or a morphism in Category Theory terms. But we do NOT call a -> b a mapping. a -> b is not a mapping in Category Theory terms. A mapping is something else, as we will soon see.

Type constructors

Thus far, we have a Category of types as objects, and of functions (from one type to another type) as morphisms. Now imagine that we create a type constructor in Haskell. A type constructor creates a new type and it is denoted by a name that has its first letter capitalized. So we can call our type constructor A, B, Chicken, and so on, as long as we follow the convention: the first letter of the name of the constructor must be a capital letter. OK, let us call our type constructor OurTC, for lack of a better name. This name reminds us that this type constructor is ours and, well, it is a type constructor.

Great, now we have a type constructor, named OurTC. Let us make this type constructor operate on any existing type, modifying the existing type to be something of type OurTC. We have already seen examples of type constructors in my blog post titled “Examples of Functors in Haskell”. Let us make OurTC an extremely simple one. Let us define it as:

data OurTC a = OurType a deriving (Show)

The following program proves that OurTC operates as a type constructor:


module Main where

data OurTC a = OurType a deriving (Show)

main :: IO ()
main  =
   do
      putStrLn "Program begins."

      putStrLn "Tests that prove that OurTC behaves as a type constructor."

      let thing1 = OurType 31
      print thing1
      print (OurType "This is a test string.")
      print (OurType [1,2,3])
      print (OurType ([10,20,30,40],12,13,["one","two"],"cat"))

      putStrLn "Program ends."

The output of the previous program is:


Program begins.
Tests that prove that OurTC behaves as a type constructor.
OurType 31
OurType "This is a test string."
OurType [1,2,3]
OurType ([10,20,30,40],12,13,["one","two"],"cat")
Program ends.

So OurTC can operate on any type a and transform it to OurType a, where OurType a is a type that belongs to the “realm” of OurTC.

So now we can imagine that there exists another Category, which has as objects the types that OurTC creates (the “realm” of OurTC). For every type a in the original Category, a type OurTC a equal to OurType a exists in the new Category.  If we wish, we can also think that the new Category is the same as the original one, since they both contain types as objects. But it will be more clear if we consider the new Category to be a new one, consisting only of objects of type OurTC a, in other words, of objects of type OurType a.

So, OurTC is a type constructor. It is also a mapping. Remember when I wrote that a morphism a -> b is not a mapping? Indeed, a function should be considered as a morphism and not as a mapping. But a type constructor is a mapping: a mapping of the types of one Category to another Category. OurTC maps a type a to a type OurType a. Type a belongs to the original (source) Category, type OurType a belongs to the new (destination) Category.

Thus a type constructor is a mapping of types from one Category to another. We can say that a type constructor elevates types from one Category to another. OurTC elevates a type a, which can be any built-in Haskell type, to the type OurType a. Thus a type constructor is a mapping of objects from one Category to another Category, when these Categories have types as objects.

Now, OurTC is a trivial type constructor and it does nothing more than reiterate the type given to it by rapping it inside an OurType type, which in itself has no real computational  or semantic “value”. But we have already seen other type constructors that have more functionality and usefulness. And we are going to discuss other type constructors like the Maybe type constructor, the list type constructor, tree type constructors and other type constructors that have real “value”. But let us continue our analysis with OurTC, which is a very simple type constructor, in order to introduce a few concepts and nothing more.

Let me stress again the fact that our type constructor OurTC is a mapping of types (objects) from the Category of Haskell types to the Category of OurType types (objects). Thus, a type constructor is a mapping of objects from one Category to another Category. And it does not matter if we consider the two Categories to be the same Category or to be  different Categories.

So, we have a type constructor, named OurTC, which is effectively a mapping from the source Category of Haskell types to the destination Category of OurType types. And that may be enough in and of itself. I mean, we may only want to have this mapping and nothing else. If this is the case, we remain as we are, having this mapping of types to types and everything is fine. There are certainly cases where we only want such a mapping and nothing else.

Why we need Functors, Applicatives, and Monads

But there are also cases that we want more. Look at our situation here. We have two Categories: a “source” Category with types as objects and morphisms from one type to another, and a “destination” Category with types of OurType that are created by OurTC. OurTC constitutes a mapping of objects (types) from the source Category to the destination Category. Now, someone may think: Since we have a mapping of objects from the source Category to the destination Category, why don’t we also create a mapping of morphisms (functions) from the source Category to the destination Category, as well? Such an extended mapping can only benefit us. Our types in the destination Category will only be more useful if we have morphisms in the destination Category to utilize with the types there.

Indeed, this is the concept of a Functor. A Functor is a mapping of objects from a source Category to objects of a destination Category, and also a mapping of morphisms from the source Category to morphisms of the destination Category. OurTC provides the mapping of objects from the source Category to the destination Category. We can elevate, beef up, supercharge our type constructor to a Functor by giving it the ability to map morphisms (functions) from the source Category to morphisms (functions) of the destination Category. We have seen how to do this in my blog post “Examples of Functors in Haskell” and I am going to repeat it here. Thus, OurTC can be augmented in order to provide a mapping of morphisms as well as types.

And this is the reason we need Functors and other concepts in Haskell. “What was this reason again?” might you ask. Well, the reason is that Haskell lets us create our own type constructors. And after we create our own type constructors, what are we going to do with them? We need Functors in order to be able to reuse the functions that already exist with the existing types. We need to be able to take a function that worked with the previous types and we want to be able to elevate it so that it works with our new types. And this can be done by turning our type constructor into a Functor. Because then, it not only maps types to new types, but it can also map existing functions to functions that operate on the new types.

We may also need the ability to take elevated functions and apply them to elevated types. I will explain this concept further below. And since we may need this ability, we should turn our type constructor into an Applicative, as well.

And we may also need the ability to compose functions that take existing types as input but produce elevated types as output. I will also explain this concept further below. And since we may need this ability, we should turn our type constructor into a Monad, as well.

Thus, we can understand why we need Functors, Applicatives, and Monads in Haskell. It is because Haskell allows us to create our own types and we want these types to be as useful and powerful as the built-in types. So, we begin by creating type constructors in order to produce elevated types. But then we need to advance our type constructors to Functors in order to use existing functions with our elevated types.  After that, we also need to advance our Functors to Applicatives, in order to use elevated functions with our elevated types. At last, we need to advance our Applicatives to Monads, because we also need to compose functions that take built-in types as input, but produce our elevated types as output.

OK, let us now see how this is done in practice, and also further explain the concepts of Functors, Applicatives and Monads while we are at it.

Functors

I am going to use the type constructor OurTC I created earlier as an example. Here is its definition again:

data OurTC a = OurType a deriving (Show)

Alone and by itself, OurTC is a mapping of types such as a and b to types such as OurType a and OurType b. Types such as a and b, and OurType a and OurType b, correspond to objects in Category Theory. And functions such as a -> b and OurType a -> OurType b correspond to morphisms in Category Theory. So, alone and by itself, OurTC is half of a Functor, so to speak. This is because it only performs a mapping of types (objects). To be a Functor, OurTC should also be able to perform a mapping of functions (morphisms).

It easy to turn our type constructor into a Functor. All we have to do is provide a definition for the function fmap. This is because Haskell has this code embedded in it:

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

Since Haskell has this code embedded in it, we do not need to write it ourselves. We only need to provide an instance of the class Functor for OurTC where we will define the function fmap. The function fmap will tell Haskell how to perform the mapping of a function such as a -> b to a function such as OurTC a -> OurTC b. fmap will thus elevate a function such a -> b to a function such as OurTC a -> OurTC b.

Please be careful. Here f denotes a type constructor and a Functor (OurTC). It does not denote a function. The function is denoted by the symbol ->.

So the code we need to write in order to elevate our type constructor to a Functor is the following:

instance Functor OurTC where
   fmap f (OurType x) = OurType (f x)

Please be extra careful. Here f denotes a function such as a -> b. f here does not denote a Functor. OurTC is the Functor. Although I could have used another name for the argument f to avoid confusion, it is best that you are made aware of this particular point, so that you can tell the difference between functions and Functors, even in the most ambiguous circumstances.

In my blog post titled “Examples of Functors in Haskell”, I analyzed the correspondence between the declaration class Functor f whereand our implementation instance Functor OurTC where … To recapitulate, in the declaration, f is the type constructor/Functor. In our definition, OurTC is the type contrsuctor/Functor. In the declaration, a -> b is a function and the first argument of fmap. In the definition, this function is denoted by f. In the declaration, f a is an elevated type and second argument to fmap. In our definition, this corresponds to OurType x, where x is of type a. In the declaration, f b is an elevated type and the output type of fmap. In our definition, this corresponds to OurType (f x), where f x is of type b.

So all we needed to write was a very small amount of code (instance Functor OurTC where  fmap f (OurType x) = OurType (f x)) in order to turn OurTC into a Functor. Of course we would need more complex code for a more complex type constructor.  But in every case, all we need to define is how fmap should be able to elevate a function of signature a -> b to a function of signature f a -> f b, where f here is the Functor. In other words, fmap takes two arguments, the first argument is the original function a -> b and the second argument is the elevated type of the first argument f a. fmap should be defined to return the elevated type of the original output, thus f b.

In the case of OurTC, fmap takes the original function and applies it inside the OurType specifier. And so, the fmap definition is completed!

The following program proves that OurTC has been elevated into a Functor:


module Main where

data OurTC a = OurType a deriving (Show)

instance Functor OurTC where
   fmap f (OurType x) = OurType (f x)

main :: IO ()
main  =
   do
      putStrLn "Program begins."

      putStrLn "Tests that prove that OurTC behaves as a type constructor."

      let thing1 = OurType 31
      print thing1
      print (OurType "This is a test string.")
      print (OurType [1,2,3])
      print (OurType ([10,20,30,40],12,13,["one","two"],"cat"))

      putStrLn "Tests that prove that OurTC behaves as a Functor."

      print (fmap (*3) thing1)
      print (fmap (+7) thing1)
      print (fmap (:[]) thing1)
      print (fmap (\x -> 3*x+7:[1,2,3]) thing1)
      print (fmap length (OurType "My string."))

      putStrLn "Program ends."

The output of the previous program is:


Program begins.
Tests that prove that OurTC behaves as a type constructor.
OurType 31
OurType "This is a test string."
OurType [1,2,3]
OurType ([10,20,30,40],12,13,["one","two"],"cat")
Tests that prove that OurTC behaves as a Functor.
OurType 93
OurType 38
OurType [31]
OurType [100,1,2,3]
OurType 10
Program ends.

The previous program starts by creating thing1 which is of type OurTC Int. It does so with the statement let thing1 = OurType 31. Here OurTC elevates the type Int with value 31 to the type OurType Int with value OurType 31. Without the definition of fmap, OurTC is only able to elevate types. But since we define fmap using the statement instance Functor OurTC where fmap f (OurType x) = OurType (f x), we are then able to use ordinary functions with signatures like Int -> Int or like Int – > [Int] to operate on thing1, which is of type OurTC Int. Thus, with the definiton of fmap in the statement instance Functor OurTC where fmap f (OurType x) = OurType (f x), OurTC can also elevate functions (morphisms), thus OurTC can also function as a full Functor.

Applicatives (correct name: Applicative Functors)

In the previous section, we saw that by just providing the instance Functor OurTC where … definition , we turned our type constructor into a Functor. In this section, we will see that just be providing the instance Applicative OurTC where … definition, we will turn our type constructor/Functor into an Applicative. And in the next section we will see that just be providing the instance Monad OurTC where … definition, we will turn out type constructor/Functor/Applicative into a Monad.

OK, in this section we will elevate our type contructor/Functor OurTC into an Applicative. Let me explain what an Applicative is.

The definition that Haskell has built-in for the Applicative is the following:

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

Here f denotes the type constructor/Functor/Applicative and the functions are denoted by ->. What this definition tells us is that first of all an Applicative should be a Functor and that the function pure ensures that there is a way to perform type elevation. The most important function though is the second one, <*>, which is applied infix and has a type signature of f (a -> b) -> f a -> f b. This type signature tells us that function <*> takes an elevated function and returns a function that takes the function’s elevated input and returns the function’s elevated output. In other words, <*> takes a function a -> b that has been elevated into the “realm” (i.e Category) of the type constructor and has become of type f (a-> b) where f is the type constructor. <*> also takes a second argument f a, which is the elevated type of the function’s argument. Finally, <*> returns output of type f b, which is the type of the elevated function’s output. Thus, <*> should obtain the function a -> b from f (a -> b) and apply it to f a, in order to get f b.

All we have to do to turn OurTC from a Functor to an Applicative is provide the implementation of pure and <*>, as follows:

instance Applicative OurTC where
   pure = OurType
   (OurType f) <*> (OurType x) = OurType (f x)

The previous implementation shows us that the function pure is the OurType function, since this is the function that creates OurTC types. Instead of pure = OurType we could have also written pure x = OurType x. Either statement is exactly the same thing. Now the definition of <*> also deserves some explanation. First of all, we see that the application of the function <*> is an infix operation. Also here f denotes a function and not the type constructor/Functor. <*> has as its first argument the elevated function f, thus OurType f. (We see that f is inside OurType; up till now we only saw types inside OurType, now with the use of Applicatives, we can have functions inside OurType as well). <*> has a second argument of type OurType x, where x can be of any type. The definition of <*> that we provide takes f and x out of OurType and provides f x as its output.

It is important to understand the correspondence between the declaration class (Functor f) => Applicative f where … and our definition instance Applicative OurTC where … In the declaration, we have f as the type constructor/Functor/Applicative. In our definition, this f becomes OurType. In the declaration, we have f (a -> b) as the elevated function, i.e. the function a -> b “inside” our type f. In our definition, we have OurType f as the elevated function, where OurType is the type and f is the function. In the declaration, we have the elevated type f a (which is the second argument to <*>), where f is the type/Functor and a is the input type to the function a -> b. In our definition, we have OurType x as the elevated type (which is the second argument to <*>), where OurType is the type constructor/Functor and x is the input type to function f. In the declaration, we have f b (which is the output type of <*>), where f is the type/Functor and b is the output type of the function a -> b. In our definition, we have OurType (f x) as the output of <*>, where OurType is the type constructor/Functor and f x is the output type of function f.

The following program proves that OurTC has been elevated to an Applicative:


module Main where

import Control.Applicative

data OurTC a = OurType a deriving (Show)

instance Functor OurTC where
   fmap f (OurType x) = OurType (f x)

instance Applicative OurTC where
   pure = OurType
   (OurType f) <*> (OurType x) = OurType (f x)

main :: IO ()
main  =
   do
      putStrLn "Program begins."

      putStrLn "Tests that prove that OurTC behaves as a type constructor."

      let thing1 = OurType 31
      print thing1
      print (OurType "This is a test string.")
      print (OurType [1,2,3])
      print (OurType ([10,20,30,40],12,13,["one","two"],"cat"))

      putStrLn "Tests that prove that OurTC behaves as a Functor."

      print (fmap (*3) thing1)
      print (fmap (+7) thing1)
      print (fmap (:[]) thing1)
      print (fmap (\x -> 3*x+7:[1,2,3]) thing1)
      print (fmap length (OurType "My string."))

      putStrLn "Tests that prove that OurTC behaves as an Applicative."

      print (OurType (*100) <*> thing1)
      let thing2 = (pure 50) :: OurTC Int
      print thing2
      print (OurType (*100) <*> thing2)
      print (OurType (*4) <*> pure 30)
      print (OurType (*2) <*> OurType 25)
      print (OurType length <*> OurType "This is one string.")
      print (OurType (\x -> 3*x+7) <*> OurType 100)
      print (OurType (11:) <*> OurType [12,13,14,15])
      print (OurType ([11] ++) <*> OurType [12,13,14,15])

      putStrLn "Program ends."

The output of the previous program is:


Program begins.
Tests that prove that OurTC behaves as a type constructor.
OurType 31
OurType "This is a test string."
OurType [1,2,3]
OurType ([10,20,30,40],12,13,["one","two"],"cat")
Tests that prove that OurTC behaves as a Functor.
OurType 93
OurType 38
OurType [31]
OurType [100,1,2,3]
OurType 10
Tests that prove that OurTC behaves as an Applicative.
OurType 3100
OurType 50
OurType 5000
OurType 120
OurType 50
OurType 19
OurType 307
OurType [11,12,13,14,15]
OurType [11,12,13,14,15]
Program ends.

Please note that although Haskell imports the declarations for Functor and Monad automatically, it does not do so for Applicative, thus we needed to do import Control.Applicative in the beginning of the program. Also, when we needed to test the function pure alone and out of its context, we needed to specify its type with the :: operator. This is because we needed to tell Haskell which Applicative instance this pure function corresponds to. In a program, we can have many Applicative instances, since we can have many type constructors. And although in this program we only have the OurTC instance, there are also built-in Applicatives in Haskell, thus there is always a need to specify the instance for pure, if it cannot be found from the context.

Monads

In my blog post “Monads in Haskell finally explained”, I explain the need for Monads, something that I also going to present in this blog post as well. Let me begin by giving you the built-in Haskell declaration for the Monad typeclass:

class Monad m where  
    return :: a -> m a 
    (>>=) :: m a -> (a -> m b) -> m b 
    (>>) :: m a -> m b -> m b  
    x >> y = x >>= \_ -> y 
    fail :: String -> m a  
    fail = error

The Monad typeclass has the function return which provides the elevation of types, just as the Applicative typeclass has the function pure. The important part in the declaration of Monad is the function >>= which is of infix type and also called “bind”. It is the function that, when implemented, will provide the way to compose functions of type a -> m b. Indeed, the type signature of the function >>= is m a -> (a -> m b) -> m b. What this means is that >>= shows how to take the output of a function a -> m b and pass it to  a function b -> m c in order to produce the output m c.  Thus >>= is of type m b -> ( b -> m c) -> m c, or, by renaming the types: m a -> ( a -> m b) -> m b.

The function >> is less important and a default implementation (using >>=) is provided for it in the declaration. It concerns functions such as y that ignore their argument. In other wotrds, >> is >>= for functions that ignore their argument. A default implementation is also provided for the function fail. Thus, all we have to do in order to implement a Monad instance is to define the functions return and >>=. Indeed, our implementation of the Monad instance for OurTC is as follows:

instance Monad OurTC where
    return = OurType
    OurType x >>= f = f x

Again, as we saw for pure in the Applicative case, return here is implemented as OurType. We could have written equivalently: return x = OurType x. The implementation of >>= is underneath that of return. We see that >>= is applied in a infix manner. >>= takes two arguments: The first argument is OurType x, where x is of type a and OurType x is of type OurType a. The second argument is a function f of type a -> OurType b  and produces the output f x (which is the application of function f to x) and is of type OurType b.

The correspondence between the declaration of the function >>= (>>=) :: m a -> (a -> m b) -> m b and our definition for it OurType x >>= f = f x, is as follows: The declaration has m as the type constructor/Monad. Our definition has OurTC, and specifically OurType, as the type constructor/Monad. The first argument type in the declaration is m a. The first argument in our definition is OurType x, where x is of type a. The second argument in the declaration is a function of type a -> m b. The second argument in our definition is a function f of type a -> OurType b. The declaration shows that >>= provides output of type m b. Our definition shows that >>= produces f x as output, which is of type OurType b, since f is of type a -> OurType b.

The following program proves that OurTC has been elevated to a Monad:


module Main where

import Control.Applicative

data OurTC a = OurType a deriving (Show)

instance Functor OurTC where
   fmap f (OurType x) = OurType (f x)

instance Applicative OurTC where
   pure = OurType
   (OurType f) <*> (OurType x) = OurType (f x)

instance Monad OurTC where
   return = OurType
   OurType x >>= f = f x

main :: IO ()
main  =
   do
      putStrLn "Program begins."

      putStrLn "Tests that prove that OurTC behaves as a type constructor."

      let thing1 = OurType 31
      print thing1
      print (OurType "This is a test string.")
      print (OurType [1,2,3])
      print (OurType ([10,20,30,40],12,13,["one","two"],"cat"))

      putStrLn "Tests that prove that OurTC behaves as a Functor."

      print (fmap (*3) thing1)
      print (fmap (+7) thing1)
      print (fmap (:[]) thing1)
      print (fmap (\x -> 3*x+7:[1,2,3]) thing1)
      print (fmap length (OurType "My string."))

      putStrLn "Tests that prove that OurTC behaves as an Applicative."

      print (OurType (*100) <*> thing1)
      let thing2 = (pure 50) :: OurTC Int
      print thing2
      print (OurType (*100) <*> thing2)
      print (OurType (*4) <*> pure 30)
      print (OurType (*2) <*> OurType 25)
      print (OurType length <*> OurType "This is one string.")
      print (OurType (\x -> 3*x+7) <*> OurType 100)
      print (OurType (11:) <*> OurType [12,13,14,15])
      print (OurType ([11] ++) <*> OurType [12,13,14,15])

      putStrLn "Tests that prove that OurTC behaves as a Monad."

      let thing3 = return 30 :: OurTC Int
      print thing3
      let thing4 = return "Test string." :: OurTC String
      print thing4
      print (thing1 >>= (\x -> OurType (2*x)))
      print ((OurType "This is a small sentence.") >>= (\x -> OurType x))
      print ((OurType "This is a small sentence.") >>= (\x -> OurType (length x)))
      print (thing2 >>= return)
      print ((OurType [1,2,3]) >>= (\xs -> OurType (reverse xs)))
      print ((OurType [1,2,3]) >>= (\xs -> OurType (reverse xs)) >>= (\xs -> OurType (xs ++ [7,8,9])))
      print ((OurType [1,2,3]) >>= (\xs -> OurType (sum xs)) >>= (\x -> OurType (x+10)))
      print ((OurType [1,2,3]) >>= (\xs -> OurType (sum xs)) >>= (\x -> OurType (x+10)) >>= (\x -> OurType [(x,[x])]))

      putStrLn "Program ends."

The output of the previous program is:


Program begins.
Tests that prove that OurTC behaves as a type constructor.
OurType 31
OurType "This is a test string."
OurType [1,2,3]
OurType ([10,20,30,40],12,13,["one","two"],"cat")
Tests that prove that OurTC behaves as a Functor.
OurType 93
OurType 38
OurType [31]
OurType [100,1,2,3]
OurType 10
Tests that prove that OurTC behaves as an Applicative.
OurType 3100
OurType 50
OurType 5000
OurType 120
OurType 50
OurType 19
OurType 307
OurType [11,12,13,14,15]
OurType [11,12,13,14,15]
Tests that prove that OurTC behaves as a Monad.
OurType 30
OurType "Test string."
OurType 62
OurType "This is a small sentence."
OurType 25
OurType 50
OurType [3,2,1]
OurType [3,2,1,7,8,9]
OurType 16
OurType [(16,[16])]
Program ends.

Please note that when we needed to test the function return alone and out of its context, we needed to specify its type with the :: operator. This is because we needed to tell Haskell which Monad instance this return function corresponds to. In a program, we can have many Monad instances, since we can have many type constructors. And although in this program we only have the OurTC instance, there are also built-in Monads in Haskell, thus there is always a need to specify the instance for return, if it cannot be found from the context.

Bonus section

In the previous sections, I provided a lot of tests and examples in order to prove that OurTC functions as a type constructor, Functor, Applicative, and Monad. But I would now like to present a program that provides the minimum amount of tests to prove the functionality of OurTC. Indeed, only one test is needed for each case (type constructor, Functor, Applicative, Monad). But in the case of the Applicative, I also provided a test for the function pure, since we also define it along with the function <*>. And in the case of the Monad, I also provided a test for the function return, since we also define it along with the function >>=.

So here is a program with an almost minimum amount of proof-of-concept tests:


module Main where

import Control.Applicative

data OurTC a = OurType a deriving (Show)

instance Functor OurTC where
   fmap f (OurType x) = OurType (f x)

instance Applicative OurTC where
   pure = OurType
   (OurType f) <*> (OurType x) = OurType (f x)

instance Monad OurTC where
   return = OurType
   OurType x >>= f = f x

main :: IO ()
main  =
   do
      putStrLn "Program begins."

      putStrLn "Tests that prove that OurTC behaves as a type constructor."

      print (OurType 11)

      putStrLn "Tests that prove that OurTC behaves as a Functor."

      print (fmap (*2) (OurType 21))

      putStrLn "Tests that prove that OurTC behaves as an Applicative."

      print (OurType (*3) <*> (pure 31))
      print (OurType (*4) <*> (OurType 32))

      putStrLn "Tests that prove that OurTC behaves as a Monad."

      print ((OurType 41) >>= return)
      print ((OurType 42) >>= (\x -> OurType (5*x)))

      putStrLn "Program ends."

The output of the previous program is:


Program begins.
Tests that prove that OurTC behaves as a type constructor.
OurType 11
Tests that prove that OurTC behaves as a Functor.
OurType 42
Tests that prove that OurTC behaves as an Applicative.
OurType 93
OurType 128
Tests that prove that OurTC behaves as a Monad.
OurType 41
OurType 210
Program ends.

I would also like to present a little reminder. This is the code that Haskel has already built-in, so you should not provide it. But just by looking at it, you should be able to remember what Functors, Applicatives, and Monads are.

class Functor f where
   fmap :: (a -> b) -> f a -> f b
(Here the type constructor is denoted by f)

class (Functor f) => Applicative f where  
   pure :: a -> f a  
   (<*>) :: f (a -> b) -> f a -> f b
(Here the type constructor is denoted by f)

class Monad m where  
    return :: a -> m a 
    (>>=) :: m a -> (a -> m b) -> m b 
    (>>) :: m a -> m b -> m b  
    x >> y = x >>= \_ -> y 
    fail :: String -> m a  
    fail = error
(Here the type constructor is denoted by m)

Even more succinctly, the previous reminder is:

Type Constructor T
T a
Functor T
fmap ::
(a -> b) -> T a -> T b

Applicative T
(<*>) :: T (a -> b) -> T a -> T b
Monad T
(>>=) :: T a -> (a -> T b) -> T b

The reminder for the Functor reminds us that a type constructor T can be elevated to a Functor, if we provide a function fmap that takes a function a -> b as its first argument and an elevated type T a as its second argument and produces an elevated type T b as output. In other words, a Functor maps functions of type a -> b to functions of type T a -> T b.

The reminder for the Applicative reminds us that a type constructor T, that has also been elevated into a Functor, can also be elevated to an Applicative, if we provide a function <*> that takes an elevated function T (a -> b) as its first argument and an elevated type T a as its second argument and produces an elevated type T b as output. In other words, a Applicative maps functions of type T (a -> b) to functions of type T a -> T b.

The reminder for the Monad reminds us that a type constructor T can be elevated to a Monad, if we provide a function >>= that takes an elevated type T a as its first argument and a function a -> T b as its second argument and provides an elevated type T b as output. In other words, a Monad allows us to compose functions of type a -> T b, that is, functions that have a normal type as input and an elevated type as output.

To explain this last point: Indeed, if we have a function p -> T q, a function q -> T r, and a function r -> T s, we can compose them with the help of >>= as follows:

(p -> T q) >>= (q -> T r) >>= (r -> T s)

This expression provides us with a function that takes an argument of type p as input and produces an argument of type T s as output. Indeed, bind (>>=) makes the composition of the three functions succeed. The first >>= takes the output T q of the first function and passes it to the second function q -> T r, producing T r as output. The second >>= takes the output T r of the first >>= and passes it to the function r -> T s, producing T s as output. >>= is able to achieve this because we provide its definition to the declaration T a -> (a -> T b) -> T b, enabling it to take an elevated type T a and a function of type a -> T b and produce output of type T b, where a and b can be any types.

Please note that although the previous example composed three functions together, we can use >>= repetitively to compose as many functions as we need. In the last example of the program in the section titled “Monads”, I used >>= repetitively to compose four functions.

Final notes

In Haskell, as we can see from the declaration of the Applicative (class (Functor f) => Applicative f where …), an Applicative has to be a Functor first. In other words, an Applicative is a superset of Functor. But, in Haskell, as we can see from the declaration of the Monad (class Monad m where …), a Monad does not have to be an Applicative (or a Functor) first. Most experts believe this to be an oversight and they want to fix it in future versions of the language. Thus, there is a rumor that in future versions of Haskell, a Monad will also have to be a Functor and an Applicative first. In Category Theory, a Monad is definitely a Functor first. Thus, most experts want to honor that and transfer this notion to Haskell as well. Thus, it is reasonable to expect that in future versions of Haskell, a Monad will have to be a Functor and an Applicative first. Thus, I expect the future declaration of the typeclass Monad in Haskell to be: class (Applicative m) => Monad m where

As it is now, Haskell does not require Monads to be Applicatives or Functors. It is best that they are, but, again, Haskell does not require that. Indeed, as it is now, an instance of Monad has to have the return function defined, which provides the elevation of types a to m a  and also the >>= function defined, which provides the composition of functions of type a -> m b. And this is what a Monad m is in Haskell: a way to compose functions of type a -> m b.

Advertisements

About Dimitrios Kalemis

I am a systems engineer specializing in Microsoft products and technologies. I am also an author. Please visit my blog to see the blog posts I have written, the books I have written and the applications I have created. I definitely recommend my blog posts under the category "Management", all my books and all my applications. I believe that you will find them interesting and useful. I am in the process of writing more blog posts and books, so please visit my blog from time to time to see what I come up with next. I am also active on other sites; links to those you can find in the "About me" page of my blog.
This entry was posted in Development. Bookmark the permalink.