Haskell today

The Haskell programming language stems from Category Theory.  And it suffers form the same misunderstanding that plagued Category Theory in the beginning.

“Abstract nonsense”. That is what they used to call Category Theory. Nowadays, it is one of the most discussed and researched areas of Mathematics. People finally understood Category Theory’s great usefulness.

“Useless”. This is what they call Haskell today. Of course, some people might do it in a tongue-in-cheek manner. You see, as a purely functional language, Haskell eliminates side-effects. Taking that to the extreme, some people may also imply that Haskell eliminates all effects. Thus, it does nothing, so it is useless. But this is a major exaggeration, of course and can only serve as a joke.

Mathematicians and logicians studied all advances in the areas of Lambda Calculus and Functional Programming. Then they were inspired from the concepts of Category Theory and created the language of their dreams. This language is Haskell. And more than the other functional languages which are implementations of Lambda Calculus, Haskell is an implementation of Category Theory.

To realize the power and importance of Haskell, you first have to realize the power and importance of Category Theory. In Category Theory, the goal and practice is to start from simple entities and concepts and compose complex ones and study their relationships. The same formalism and findings occur throughout all areas of Mathematics and this is intriguing. An underlying formalism and conceptual context underlies all areas of Mathematics and this formalism and context are exposed via Category Theory.

In my humble opinion, Category Theory is the Grand Unification Theory of Mathematics. Category Theory is the G.U.T. of Mathematics. And Haskell implements Category Theory. Therefore, Haskell enables us to use the formalism and findings of Category Theory in order to create programs.

The programs we create with Haskell can have all the great power that stems from Category Theory. From simple entities and concepts (functions), we can compose complex ones with mathematical certainty as to their functionality and validity. We can reason about our programs and be confident that they can stand up to the most abstract theoretical validations. We can be mathematically sure that our programs work. Or, rather, it is up to us to adhere to the Category Theory’s standards and create our programs in such a way that they fulfill its requirements. If we do this, our programs will be correct, functional (you may assign any meaning to this word, scientific or not) and extensible and we will have mathematics on our side proving that.

Haskell puts the power of Category Theory into the programmer’s hands. So, it is one of the most important languages today.

People talk about Category Theory concepts and about Haskell. People write books, articles, blog posts about them. But I fear that not many do a good job explaining the concepts that need to be explained.

Most people try to explain concepts in Haskell as fast as possible, in order to make it easy for their audience to grasp the material. So, they try to explain concepts without referring to Category Theory. And this is where I think the problem lies. You should learn the Haskell concepts that come from Category Theory, by learning Category Theory. Trying to avoid it, trying to circumvent it might lead to partial understanding, or worse.

Actually, since Haskell is an implementation of Category Theory, I would suggest that not only those that study Haskell learn Category Theory, but also those that study Category Theory should learn Haskell as well.

Unfortunately, it is difficult, if not impossible, to find material that puts Category Theory and Haskell side by side. Let me give you an example of this problem; let me discuss Functors.

One of the first (if not the first) things you learn when you study Category Theory is Functors.  Functors are great; they have enormous power; they allow you to “lift” a function into working in a more advanced context; blah blah blah; and so on; and all that jazz.

Yes, Functors are great. And you will understand all their greatness if you learn about them in Category Theory as an abstract idea, and at the same time learn to implement them in Haskell in a tangible program. (And the same goes for all the other concepts, like Monads for example.) Then you have the best of both worlds. Study Category Theory and implement what you learned in Haskell. I think these two should go hand-in-hand.

Well, if you take the definition of a Functor from Category Theory and try to compare it to the definition of a Functor in Haskell, you might be in for a surprise. Even though Haskell respects the definition of a Functor and even though a Functor in Haskell is the same entity as in Category Theory, you may have a hard time identifying a Functor in Haskell as a Functor in Category Theory.

But the worst part is that none of the material out there tries to explain why a Functor in Haskell is indeed a Functor per Category Theory’s standards. All authors try to do is explain what a Functor in Haskell is and how to make use of it.

Here you may be, knowing what a Functor is in Category Theory, knowing what a Functor is in Haskell, but having no way of identifying these two concepts as the same one. Instead, a Functor in Category Theory and a Functor in Haskell may seem worlds apart; they may seem like two different concepts.

If that is the problem, do not worry. I intend to clarify and explain everything by the end of this post.

An excellent definition for Functors exists in Wikipedia. I took a screenshot from http://en.wikipedia.org/wiki/Functors, kept just the definition and this I provide below:

Functor definition in Category Theory

The same definition can be found in the definite book about Category Theory titled “Categories for the Working Mathematician” by Category Theory’s cofounder Saunders Mac Lane. Thankfully, Wikipedia has this definition neatly and rigorously presented.

The definite Haskell reference exists in Haskell.org. So, I also took a screenshot from http://www.haskell.org/haskellwiki/Functor for the definition of a Functor in Haskell and this I present below:

Functor definition in Haskell

All right, then… Wait, what?!!!

What is this definition from Haskell.org? How does it relate to the one from Wikipedia? When you first look at the two definitions, they seem to each refer to very different things. (But in reality they refer to the same thing, as I will soon explain.) The two definitions seem (when you first look at them) completely unrelated.

Compare the definition from Haskell.org to the one from Wikipedia. Where are the categories? Where are the Categories, indeed? And what are those Categories?

From Wikipedia, we see that we must have two Categories, namely C and D. and the Functor provides a mapping from C to D. Ok, but what are those Categories in the definition from Haskell.org?

A naïve first approach might lead us to the following thinking: From the definition from Haskell.org we have the types a and b. But since Functor f is a type constructor, we also have the types f a and f b. So we have a mapping from a to b, but we also have a mapping from f a to f b. Is it possible that we have not two but four Categories in the definition from Haskell.org? Is it possible that we have the following four Categories: the Category of objects of type a, the Category of objects of type b, the Category of objects of type f a and the Category of objects of type f b? If so, which two Categories form these four should we select? We should select only two, because the definition of a Functor from Wikipedia is specific: we need to have two categories, C and D. So, which is the category C and which is the category D?

No matter which two Categories of the four we choose, we will be leaving the other two behind; we will be ignoring them. This does not seem to be correct.

Let us try another approach. Let us again examine the Functor definition from Haskell.org. And let us study the function fmap. This function has the following type:

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

Hmmm, the parentheses (a -> b) suggests that we have three things to consider (instead of the four we considered previously). We have (a -> b), f a and f b.

So, from this definition we have that fmap takes a function a -> b and an f a and returns an f b. But we can also describe fmap as taking a function a -> b and returning a function f a -> f b.

We can write the type of fmap as follows:

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

The two ways of writing fmap are equivalent. But the latter shows that we have only two things to consider: a function a – > b and a function f a -> f b.

So that is it! We found our two Categories! Category C is the category of functions (a.k.a. morphisms) of type a -> b and Category D is the category of functions (morphisms) of type f a -> f  b. Category C has the types a and b as elements and Category D has the types f a and f b as elements.

So the Functor f maps functions of type a -> b to functions of type f a -> f b. And it does so with the function fmap, which has to be implemented accordingly. fmap has to be able to take a function such as a -> b and use it in such a way so as to map f a to f b. You have to provide a specific fmap function that does this for each particular Functor that you create. And by doing so, you help lift, elevate the function with type a -> b to operate in the context of the type constructor (and Functor) f. f as a type constructor creates the new context, the new types f a and f b from the types a and b. fmap elevates the function type a -> b to f a -> f b, thus elevating the mapping from to a b to a mapping from f a to f b.

There are many examples of Functors in Haskell, but I consider the examples from Peteris Krumins’ blog post about functors to be the best. Peteris Krumins, who I admire very much and I am an avid reader of his blog, provides an example of a list Functor and an example of a tree Functor. These two examples should provide valuable insight and should help clarify any issues you may have with Functors in Haskell.

It is a shame that when Haskell concepts and definitions are presented, they are not tied to the corresponding Category Theory concepts. We miss important insight this way. Haskell and Category Theory go hand in hand. Haskell is inseparable from Category Theory and should be thought and taught this way.

Update October 31st, 2013: Saunders Mac Lane gives the definition of a Functor in page 13 of his book “Categories for the Working Mathematician”, Second Edition.  I would really like to provide a photograph from his book of his definition, but I should not infringe the book’s copyright. I will just reiterate here what he writes, changing his symbolism, in order to coincide with the symbolism from Wikipedia.

So, if I were to paraphrase Saunders Mac Lane only a little bit, a Functor f : C -> D consists of two related functions: a) the object function, which assigns to each object of Category C an object of Category D and b) the arrow function, which assigns to each arrow of Category C an arrow of Category D. These assignments are made in such a way that identity morphisms are preserved and composition of morphisms are also preserved.

OK, so how does this definition relate to the Functor definitions that we studied in this blog post? Well, the object function is the type constructor f and the arrow function is the fmap function.

If we want to find the connection between Peteris Krumins’ examples, here it is: The list Functor has the list type constructor [] as the object function and the fmap function (equal in the list case to the map function) as the arrow function. The tree Functor has the Tree type constructor as the object function and the fmap function that Peteris Krumins provides for this case as the arrow function.

So all roads lead to Rome and all Functor definitions amount to the same thing. So, we arrive at the end of this update. Just one more thing; I cannot resist the urge to tell you that if you want to get started in Haskell, there exists a great blog post for beginners: Haskell newbie attempts a Haskell quick start guide.

Update November 1st, 2013: So, what are Functors, anyway?

Well, Functors provide a way for us to take a function and have it operate in a higher context. The function is the (a -> b) and the higher context is the f type constructor.

In Peteris Krumins’ list example, the function is the (+ 1) and the higher context is the list. In Peteris Krumins’ tree example, the function is the calculation of the length of the string and the higher context is the tree.  In both examples, we have to create the fmap function that makes this possible. In the list example, things are easy because the fmap function is just the map function. But on the tree example, we have to create the fmap function such that it knows how to handle tree nodes and tree leafs.

In the list example, the fmap function lifts the (+1) function from the single integer world to the list world. In the tree example, the fmap function lifts the function of calculation of the length of the string from the single string world to the tree world.

Another insightful view of Functors comes from Miran Lipovača. In the chapter titled “A fistful of Monads” from his book “Learn You a Haskell for Great Good!”, Miran Lipovača explains that Functors help us provide the answer to the question: “when we have a function of type a -> b and some data type f a, how do we map that function over the data type to end up with f b?”

Not to exclude Saunders Mac Lane from this update, in page 16 of his book, he talks about Natural Transformations. There he writes that we can think of a Functor from C to D as giving a picture in D of (all the objects and arrows of) C.

So, there you have it: a blog post that began as a description of Haskell today and ended as being an analysis about Functors.

Anyway, this is my preferred way of learning Haskell: go from the Category Theory definition of the concept to its implementation on Haskell. Only then do we have the full “story” and a clear understanding of what the concept is and what we are trying to achieve.

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.