Examples of Functors in Haskell

Title: Examples of Functors in Haskell
Alternative title: Practical Functors in Haskell

In previous posts, I have talked about Functors a lot. It is high time to put what we have learned to practice. It is high time to show you proof-of-concept programs that create and use Functors. This blog post will do exactly that: it will give you examples of Functors in real programs that work, but are minimal, in order to demonstrate the concepts, all of the concepts and nothing but the concepts.

To recapitulate what we have learned from previous posts, Functors are introduced in Category Theory and their concept is put to use in Haskell (as well as in a lot of branches of Mathematics). A Functor in Category Theory is a mapping. This mapping maps dots from a source Category to a destination Category, and also maps arrows from the source Category to the destination Category. A Functor in Haskell is such a mapping. In Haskell, dots are types and arrows are functions from one type to another type. In Haskell, the source and destination Category contain types. Also, the source and destination Categories can be thought of as being the same.

Thus, if I have a type a, a type b and an arrow (i.e. function) a -> b, then a Functor f does the following mappings:
i)  f maps type a to type f a.
ii) f maps type b to type f b.
iii) f maps function a -> b to function f a -> f b.
Please note that the types a and b can be the same type or different types. Also, please note that here, f represents the Functor and not a function. The functions here are denoted by ->. Also please note that, here, an equivalent word for “maps” is “elevates”.

As we have seen in previous posts, a Functor in Haskell is represented by a type constructor armed with a function mapping mechanism. The type constructor does the mapping of the types (points i and ii in the previous paragraph)  and the function mapping mechanism does the mapping of the functions (point iii in the previous paragraph).

So, here is a program that creates and uses a Functor:

module Main where

data MyFunctor a = MySomething a deriving (Show)

instance Functor MyFunctor where
   fmap f (MySomething x) = MySomething (f x)

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

      let thing1 = MySomething 45
      print thing1
      print (fmap (*2) thing1)
      print (fmap (+1) thing1)
      print (fmap (:[]) thing1)
      print (fmap (\x -> 2*x+1:[]) thing1)
      print thing1

      putStrLn "Program ends."

Here is the output of this program:

Program begins.
MySomething 45
MySomething 90
MySomething 46
MySomething [45]
MySomething [91]
MySomething 45
Program ends.

In the previous program, the data MyFunctor … statement declares/creates a type constructor. This type constructor is called MyFunctor (perhaps a misnomer, perhaps not). As a type constructor, MyFunctor maps a type a to the type MyFunctor a. In this example, MyFunctor a is always equal to MySomething a. Also, as a type constructor, MyFunctor maps a type b to the type MyFunctor b. In this example, MyFunctor b is always equal to MySomething b.

So what is missing is a way to map a function a -> b to MyFunctor a -> MyFunctor b for our Functor to be complete. This remaining ingredient is provided by the statement instance Functor MyFunctor …,where we provide the definition for the fmap function.

Now, Haskell already knows about the fmap function. Haskell already has built-in the declaration of this function:
class Functor f where
   fmap :: (a -> b) -> f a -> f b
or equivalently:
fmap :: Functor f => (a -> b) -> f a -> f b
and all that remains is for us to provide its definition. Only we know how we want to implement fmap in order for it to take a function a -> b and an object of type MyFunctor a as input, and provide an object of type MyFunctor b as output. MyFunctor is our data type constructor, so we have to say how a function a -> b will behave as a MyFunctor a -> MyFunctor b function.

In the previous program, we implement the function fmap as follows:

fmap f (MySomething x) = MySomething (f x)

Here f denotes a function a -> b (f does not denote a Functor here! Please be careful!). So, what we are saying to Haskell here is that we want to map functions a -> b in such a way so that they operate on the value after MySomething. Thus, a function f :: a->b that operates on a MyFunctor a type, will give as output a MyFunctor b type such that the function f will operate on the type that exists on the right of MySomething.

To be very specific, the Haskell built-in declaration of fmap is

fmap :: Functor f => (a -> b) -> f a -> f b

and our definition of fmap in the case of MyFunctor is

fmap f (MySomething x) = MySomething (f x).

The correspondence here is the following: The function (a -> b) in the declaration corresponds to the function f in our definition. The Functor f in the declaration corresponds to the data type constructor value MySomething in our definition. The type a in the declaration corresponds to the type x in our definition. The type b in the declaration corresponds to the type f x in our definition. The type f a in the declaration corresponds to the type MySomething x in our definition. The type f b in the declaration corresponds to the type MySomething (f x) in our definition. From the declaration, we see that fmap takes two arguments, a function (a -> b) and an object of type f a and returns an object of type of f b as output. From our definition, we correspondingly see that indeed fmap takes two arguments, a function f and an object of type MySomething x and returns an object of type of MySomething (f x) as output.

Let us study the examples that are given for the use of MyFunctor in the main program.

First of all, we create thing1 which is equal to MySomething 45 and thus is of type MyFunctor. Here we made use of the type constructor in order to map 45 (which is an Integer) to MySomething 45 which is an object of type MyFunctor (and, especially, MySomething). So, we have a mapping of type Int to MySomething Int.

Then, we print thing1, just to see that everything is OK. This is possible because we used the deriving (Show) sub-statement in the declaration of MyFunctor.

Then, we print the result of fmap (*2) thing1, which is the result of applying the function (*2) to thing 1thing1 is of type MyFunctor and (*2) is a function Int -> Int. We can rewrite (*2) as (\x -> x*2) for more clarity.we have already told fmap how to function in such a case:

fmap f (MySomething x) = MySomething (f x)

fmap is to take our (*2) function and apply it to thing1 such that MySomething 45 will become MySomething ((*2) 45), thus MySomething 90.

The same holds true for the next statement,where we apply the function (+1) to thing1. Again, the definition for fmap that we have provided will give the result MySomething 46.

Now, the next statement is a little bit more interesting. It prints the result of fmap (:[]) thing1, which is the result of applying the function :[] to thing1. This function has different types for its input and output. :[] is a function of Int -> [Int], thus from Int to a list of Ints. But as in the previous two statements, fmap knows to apply :[] to the Int after MySomething. Thus the result is MySomething [45].

The last statement prints the result of fmap (\x -> 2*x+1:[]) thing1, thus of applying a function that does all the previous operations to thing1. The function is of type Int -> [Int] and the result is MySomething [91].

At the end of the program, we print thing1 again, in order to show that it has not changed. We have immutability in Haskell and, anyway, thing1 was only used as input to the fmap function during the course of the program.

OK, let us see a program with a more complex data constructor. Again I am going to call the data constructor MyFunctor and I am going to provide a corresponding fmap function:

module Main where

data MyFunctor a = MySomething a
                 | MySomethingElse [a]
                 | MySomethingOther (a,a)
                 | MyYetAnother a
                 deriving (Show)

instance Functor MyFunctor where
   fmap f (MySomething x)      = MySomething (f x)
   fmap f (MySomethingElse xs) = MySomethingElse (map f xs)
   fmap f (MySomethingOther x) = MySomethingOther (f (fst x), f (snd x))
   fmap f (MyYetAnother x)     = MySomething (f x)

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

      let thing1 = MySomething 10
      print thing1
      print (fmap (*2) thing1)
      print thing1

      let thing2 = MySomethingElse [100,1000,10000,100000]
      print thing2
      print (fmap (*2) thing2)
      print thing2

      let thing3 = MySomethingOther (400,500)
      print thing3
      print (fmap (*2) thing3)
      print thing3

      let thing4 = MyYetAnother 200
      print thing4
      print (fmap (*2) thing4)
      print thing4

      putStrLn "Program ends."

Here is the output of this program:

Program begins.
MySomething 10
MySomething 20
MySomething 10
MySomethingElse [100,1000,10000,100000]
MySomethingElse [200,2000,20000,200000]
MySomethingElse [100,1000,10000,100000]
MySomethingOther (400,500)
MySomethingOther (800,1000)
MySomethingOther (400,500)
MyYetAnother 200
MySomething 400
MyYetAnother 200
Program ends.

In the previous program, I created a data type constructor that has four types: MySomething, MySomethingElse, MySomethingOther and MyYetAnother, but each has its idiosyncrasies: MySomething and MyYetAnother have an object at their end, MySomethingElse has a list and MySomethingOther has a 2-tuple.

The corresponding fmap function is created such that functions operate on the object, list or 2-tuple inside the MyFunctor types. If we have an object, the function operates on the object. If we have a list, the function operates on every element of the list. If we have a 2-tuple, the function operates on each element of the 2-tuple. And there is also a twist: Whenever a function is applied to a MyYetAnother, the type is changed to a MySomething. Some rules are sane, some rules are crazy, but they are the rules I set up.

Now, in the main program, we start by created a thing1 of type MyFunctor and equal to MySomething 10. Here the type constructor elevates the integer 10 to a MySomething 10.

Then we apply the function (*2) to MySomething 10. The fmap function elevates this Int -> Int function into a MySomething Int -> MySomething Int function. Indeed, the function (*2) when applied to MySomething 10 provides as result the MySomething 20, just as fmap instructed. (And we programmed fmap to instruct so.)

Then we create a thing2 as MySomethingElse [100,1000,10000,100000]. The type constructor gets into gear and does so. Them we map the function (*2) on thing2. Again, fmap provides the way to do this mapping. It instructs that (*2) will operate on every element of the list.

Then we create a thing3 as MySomethingOther (400,500). The type constructor accepts this as valid and allows us to create it. Then we apply the function (*2) to thing3. fmap tells the program how to apply it. In this case, it applies it on every element of the tuple.

At the end, we create a thing4 as MyYetAnother 200. The type constructor data MyFunctor … allows it as valid. Then we map the function (*2) to thing4. The definition instance Functor myFunctor … instructs that (*2) will be applied to the integer 200, but also that the type will change to MySomething. Thus, the result will be MySomething 400.

Here is another program that demonstrates the use of Functors. In the following program, I took a type constructor from a previous blog post: the one about trees in Haskell. This type constructor creates MyTrees out of Haskell types. It thus elevates some Haskell type a to a MyTree a type and some Haskell type b to a MyTree b type. And what about functions a -> b? Well, for that I provided the instance Functor MyTree … statement where I define how fmap will map functions a -> b to the MyTree “realm”, thus to MyTree a -> MyTree b. As you will notice in the code, I apply fmap recursively. “Recursive types call for recursive handling”, that is what I say.

module Main where

data MyTree a = MyEmptyNode
              | MyFilledNode a (MyTree a) (MyTree a)
              deriving (Show)

instance Functor MyTree where
   fmap f MyEmptyNode          = MyEmptyNode
   fmap f (MyFilledNode x y z) = MyFilledNode (f x) (fmap f y) (fmap f z)

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

      let tree1 = MyFilledNode 5 (MyFilledNode 3 MyEmptyNode MyEmptyNode) (MyFilledNode 2 MyEmptyNode MyEmptyNode)
      print tree1
      print (fmap (*2) tree1)
      print tree1

      let tree2 = MyFilledNode "ABC" (MyFilledNode "AB" MyEmptyNode MyEmptyNode) (MyFilledNode "ABCDEF" MyEmptyNode MyEmptyNode)
      print tree2
      print (fmap length tree2)
      print tree2

      putStrLn "Program ends."

Here is the output of this program:

Program begins.
MyFilledNode 5 (MyFilledNode 3 MyEmptyNode MyEmptyNode) (MyFilledNode 2 MyEmptyNode MyEmptyNode)
MyFilledNode 10 (MyFilledNode 6 MyEmptyNode MyEmptyNode) (MyFilledNode 4 MyEmptyNode MyEmptyNode)
MyFilledNode 5 (MyFilledNode 3 MyEmptyNode MyEmptyNode) (MyFilledNode 2 MyEmptyNode MyEmptyNode)
MyFilledNode "ABC" (MyFilledNode "AB" MyEmptyNode MyEmptyNode) (MyFilledNode "ABCDEF" MyEmptyNode MyEmptyNode)
MyFilledNode 3 (MyFilledNode 2 MyEmptyNode MyEmptyNode) (MyFilledNode 6 MyEmptyNode MyEmptyNode)
MyFilledNode "ABC" (MyFilledNode "AB" MyEmptyNode MyEmptyNode) (MyFilledNode "ABCDEF" MyEmptyNode MyEmptyNode)
Program ends.

In the previous program, we create a MyTree of integers. In other words, we elevate the Int data type to the MyTree Int data type. The data MyTree a … constructor allows us to do this.

Then we apply the function (*2) to this MyTree. The instance Functor MyTree ... allows us to do this by specifying how fmap will do this application. As instructed, fmap will apply the function to every integer in the tree. Thus, I have already explained, the function (*2) is elevated from an Int -> Int function to a MyTree Int -> MyTree Int function.

The next section of the main program is way more interesting. Here we create a MyTree of Strings. The type constructor allows us to do this. Then we apply the function length to the tree. The function length has a type signature of String -> Int. Indeed, when operating on a String, length returns its length (i.e. the number of characters that the Sting contains.) fmap allows us to apply length to the tree of strings and get as result a tree of integers. Each string in the original tree has been replaced in the output tree with its length. Thus, with our fmap definition, the function length with a type signature of  String -> Int has been elevated to a function MyTree String -> MyTree Int.

And there you have it. A Functor is made of a type constructor and of a definition of fmap for this type constructor. The type constructor maps/elevates types and the fmap function maps/elevates functions to the “realm” of the corresponding type constructor.

I will finish this blog post with some advice. When dealing with Functors in Haskell, always try to spot what are the underlying types and functions and to what they are elevated. In the last example, the type Int is elevated to the type MyTree Int, the type String is elevated to the type MyTree String, and the function length with type String -> Int is elevated to a function MyTree String -> MyTree Int, so that each string in the input MyTree is replaced with its length in the output MyTree.

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.