120
$\begingroup$

I'm learning Haskell and I'm fascinated by the language. However I have no serious math or CS background. But I am an experienced software programmer.

I want to learn category theory so I can become better at Haskell.

Which topics in category theory should I learn to provide a good basis for understanding Haskell?

$\endgroup$
  • 1
    $\begingroup$ Also see relating category theory to programming language theory. $\endgroup$ – Kaveh Aug 13 '12 at 5:25
  • 1
    $\begingroup$ I appreciate that you distinguish programming and cs. $\endgroup$ – jmite Oct 31 '13 at 1:31
  • 4
    $\begingroup$ "Learning Category Theory to become better in Haskell" is a bit like "Learning physics to become better in tennis" $\endgroup$ – user26756 Oct 21 '15 at 13:08
117
$\begingroup$

In a previous answer in the Theoretical Computer Science site, I said that category theory is the "foundation" for type theory. Here, I would like to say something stronger. Category theory is type theory. Conversely, type theory is category theory. Let me expand on these points.

Category theory is type theory

In any typed formal language, and even in normal mathematics using informal notation, we end up declaring functions with types $f : A \to B$. Implicit in writing that is the idea that $A$ and $B$ are some things called "types" and $f$ is a "function" from one type to another. Category theory is the algebraic theory of such "types" and "functions". (Officially, category theory calls them "objects" and "morphisms" so as to avoid treading on the set-theoretic toes of the traditionalists, but increasingly I see category theorists throwing such caution to the wind and using the more intuitive terms: "type" and "function". But, be prepared for protests from the traditionalists when you do so.)

We have all been brought up on set theory from high school onwards. So, we are used to thinking of types such as $A$ and $B$ as sets, and functions such as $f$ as set-theoretic mappings. If you never thought of them that way, you are in good shape. You have escaped set-theoretic brain-washing. Category theory says that there are many kinds of types and many kinds of functions. So, the idea of types as sets is limiting. Instead, category theory axiomatizes types and functions in an algebraic way. Basically, that is what category theory is. A theory of types and functions. It does get quite sophisticated, involving high levels of abstraction. But, if you can learn it, you will acquire a deep understanding of types and functions.

Type theory is category theory

By "type theory," I mean any kind of typed formal language, based on rigid rules of term-formation which make sure that everything type checks. It turns out that, whenever we work in such a language, we are working in a category-theoretic structure. Even if we use set-theoretic notations and think set-theoretically, still we end up writing stuff that makes sense categorically. That is an amazing fact.

Historically, Dana Scott may have been the first to realize this. He worked on producing semantic models of programming languages based on typed (and untyped) lambda calculus. The traditional set-theoretic models were inadequate for this purpose, because programming languages involve unrestricted recursion which set theory lacks. Scott invented a series of semantic models that captured programming phenomena, and came to the realization that typed lambda calculus exactly represented a class of categories called cartesian closed categories. There are plenty of cartesian closed categories that are not "set-theoretic". But typed lambda calculus applies to all of them equally. Scott wrote a nice essay called "Relating theories of lambda calculus" explaining what is going on, parts of which seem to be available on the web. The original article was published in a volume called "To H. B. Curry: Essays on Combinatory Logic, Lambda Calculus and Formalism", Academic Press, 1980. Berry and Curien came to the same realization, probably independently. They defined a categorical abstract machine (CAM) to use these ideas in implementing functional languages, and the language they implemented was called "CAML" which is the underlying framework of Microsoft's F#.

Standard type constructors like $\times$, $\to$, $List$ etc. are functors. That means that they not only map types to types, but also functions between types to functions between types. Polymorphic functions preserve all such functions resulting from functor actions. Category theory was invented in 1950's by Eilenberg and MacLane precisely to formalize the concept of polymorphic functions. They called them "natural transformations", "natural" because they are the only ones that you can write in a type-correct way using type variables. So, one might say that category theory was invented precisely to formalize polymorphic programming languages, even before programming languages came into being!

A set-theoretic traditionalist has no knowledge of the functors and natural transformations that are going on under the surface when he uses set-theoretic notations. But, as long as he is using the type system faithfully, he is really doing categorical constructions without being aware of them.


All said and done, category theory is the quintessential mathematical theory of types and functions. So, all programmers can benefit from learning a bit of category theory, especially functional programmers. Unfortunately, there do not seem to be any text books on category theory targeted at programmers specifically. The "category theory for computer science" books are typically targeted at theoretical computer science students/researchers. The book by Benjamin Pierce, Basic category theory for computer scientists is perhaps the most readable of them.

However, there are plenty of resources on the web, which are targeted at programmers. The Haskellwiki page can be a good starting point. At the Midlands Graduate School, we have lectures on category theory (among others). Graham Hutton's course was pegged as a "beginner" course, and mine was pegged as an "advanced" course. But both of them cover essentially the same content, going to different depths. University of Chalmers has a nice resource page on books and lecture notes from around the world. The enthusiastic blog site of "sigfpe" also provides a lot of good intuitions from a programmer's point of view.

The basic topics you would want to learn are:

  • definition of categories, and some examples of categories
  • functors, and examples of them
  • natural transformations, and examples of them
  • definitions of products, coproducts and exponents (function spaces), initial and terminal objects.
  • adjunctions
  • monads, algebras and Kleisli categories

My own lecture notes in the Midlands Graduate School covers all these topics except for the last one (monads). There are plenty of other resources available for monads these days. So that is not a big loss.

The more mathematics you know, the easier it would be to learn category theory. Because category theory is a general theory of mathematical structures, it is helpful to know some examples to appreciate what the definitions mean. (When I learnt category theory, I had to make up my own examples using my knowledge of programming language semantics, because the standard text books only had mathematical examples, which I didn't know anything about.) Then came the brilliant book by Lambek and Scott called "Introduction to categorical logic" which related category theory to type systems (what they call "logic"). It is now possible to understand category theory just by relating it to type systems even without knowing a lot of examples. A lot of the resources I mentioned above use this approach to explain category theory.

$\endgroup$
  • 3
    $\begingroup$ @UdayReddy I strongly disagree with your identification of category theory with type theory. Modern type theory is sustantially about types for concurrency processes, e.g. the theory tradition of session types. To the best of my knowledge there is no categorical understanding of such typing systems. $\endgroup$ – Martin Berger Jan 9 '13 at 3:34
  • 6
    $\begingroup$ @MartinBerger I think your interpretation of "type theory" is a bit narrow. However, I agree that a proper type-theoretic and category-theoretic understanding of session types is currently a good research challenge, one that I intend to spend time on. $\endgroup$ – Uday Reddy Jan 9 '13 at 7:07
  • 2
    $\begingroup$ @MartinBerger. To see how category theory applies to richer notions of computation, I invite you to look at how it has been applied to the theory of imperative programming and to games semantics (which again can encode imperative computations quite well). So, I don't believe that functional programming has a monopoly on category theory. $\endgroup$ – Uday Reddy Jan 10 '13 at 16:04
  • 1
    $\begingroup$ @nicolas, fibrations are a way to do indexed categories, which model dependent types. Fibrations can also be viewed as a very general form of program logic, where $f : P \to Q$ means that $f$ maps $P$-satisfying values to $Q$-satisfying values. $\endgroup$ – Uday Reddy Mar 17 '17 at 17:59
  • 2
    $\begingroup$ "Unfortunately, there do not seem to be any text books on category theory targeted at programmers specifically." Such a "text book" now more-or-less exists in Bartosz Milewski's Category Theory for Programmers. Bartosz has also created an accompanying lecture series. $\endgroup$ – alx9r Jan 10 at 15:46
31
$\begingroup$

I'm going to try and keep it short and sweet. There is an informal correspondence between Haskell programs and certain classes of categories, which can be made more formal with some work. This correspondence is known as the Curry-Howard-Lambek correspondence and relates:

  1. Haskell types with objects of the category
  2. Terms of type $A\rightarrow B$ with morphisms $f\colon A\rightarrow B$ (note the similar notations)
  3. Algebraic datatypes with initial objects
  4. Type constructors with functors
  5. etc

The list goes on and on, but one crucial point is that you can define things like monads and algebras in category theory and come up with notions that are both useful to mathematicians but also pervasive in the practice of Haskell programming.

I'm not sure which book to recommend, as I haven't found a completely satisfactory introductory book on categories for computer scientists. You can try Categories, Types and Structues by Asperti and Longo. The idea is to learn basic definitions up to adjunctions, and then maybe try and read some of the excellent blogs out there to try and understand these concepts.

$\endgroup$
  • 1
    $\begingroup$ "come up with notions that are both useful to mathematicians but also pervasive in the practice of Haskell programming" -- can you give an example, or would that require too much prior knowledge? $\endgroup$ – Raphael Aug 11 '12 at 11:08
  • 7
    $\begingroup$ @Raphael: Monads. Arrows. Algebras. Coalgebras. $\endgroup$ – Dave Clarke Aug 11 '12 at 12:10
  • 6
    $\begingroup$ Functors, duality, the Kleisli category, the Yoneda lemma... $\endgroup$ – cody Aug 12 '12 at 9:25
  • 4
    $\begingroup$ Cartesion closed categories. Currying. $\endgroup$ – Dave Clarke Aug 12 '12 at 18:04
  • 2
    $\begingroup$ "An introduction to Category Theory for Software Engineers", cs.toronto.edu/~sme/presentations/cat101.pdf $\endgroup$ – Vladimir Alexiev Oct 3 '14 at 10:18
29
$\begingroup$

Echoing @AJed advice, I recommend to turn your statement

I want to learn category theory so I can become better at Haskell.

on its head: learn Haskell, building on your programming intuition. Once you are an FP guru, it might be easier to pick up category theory (if you still care).

Category theory is simple for somebody with broad mathematical education (groups, rings, modules, vector spaces, topology etc). Lacking this background, category theory is nearly impenetrable. The beauty of category theory is that it unifies a lot of seemingly unrelated things (e.g. left adjoints of forgetful functors include free groups, universal enveloping algebras, Stone-Cech compactifications, abelianisations of groups, ...), and so reduces complexity. But if you are not familiar with the multiple examples that category theory unifies, category theory is just an additional layer of complexity that makes your life harder.

In my experience, learning is easier by building on things one already knows. As a software developer, you know a lot about programming, and Haskell programming is not that different from other programming, so my recommendation is to approach Haskell from a pragmatic programming point of view, ignoring category theory. The bit of category theory that is in Haskell, e.g. some support for monads, is much easier for a programmer to grasp without taking a detour via category theory. After all, monads are merely generalised composition (and you will have used monads in your programming practise already -- albeit without knowing you did), and Haskell doesn't really support monads for real, as it does not enforce the monadic laws.

$\endgroup$
  • 7
    $\begingroup$ No, to be honest Haskell really is that different from most other programming languages, to the point that getting past preconceived notions is often the biggest challenge. Experienced software developers seem to have more trouble than people who've never programmed before. $\endgroup$ – C. A. McCann Jan 9 '13 at 14:31
  • 5
    $\begingroup$ @C.A.McCann I agree that some experienced programmes appear to have a hard time moving from e.g. Java or C# to Haskell, but I don't think it's because there's something fundamentally different about Haskell. I think it's in part because it appears to be different. The idea that you need to learn category theory in order to appreciate Haskell has probably prevented quite a few experienced software developers from achieving Haskell mastery. (Cf. why F# doesn't have monads.) I certainly find it hard to think of many Haskell features that don't also have resemblances in other languages. $\endgroup$ – Martin Berger Jan 9 '13 at 14:54
  • 5
    $\begingroup$ Knowing Category Theory might help a bit, but not all that much, and learning it is certainly much harder than learning Haskell. There are pretty fundamental differences compared to most languages (purity, non-strict evaluation, the type system), and removing all the CT terms doesn't make these any more familiar. On the other hand, learning Haskell motivates some people to learn some CT, because the ideas borrowed are useful. F#'s limited type system and avoidance of a perfectly good existing term are flaws, not features. $\endgroup$ – C. A. McCann Jan 9 '13 at 15:02
  • 1
    $\begingroup$ I don't know of any language other than Scala with a type system really comparable to Haskell's. From empirical observation, purity is not immediately grasped, and non-strict evaluation (which you skipped over) is even harder. Finally, I am a working programmer and I dispute that anyone in the field is going to be intimidated by a name. The software development industry is full of opaque jargon already. Also, F#'s type system cannot express monads directly--computation expressions are not first class, which limits their use significantly. $\endgroup$ – C. A. McCann Jan 9 '13 at 16:28
  • 2
    $\begingroup$ CBN is also conceptually easy, for example by analogy with thunking, a concept that most working programmers will have used before. Purity is something that every working programmer understands. Haskell is used in undergraduate education in the UK. When my students ask me how to get into functional programming, I often recommend learning Haskell first, but students are intimidated by its reputation, as was the originator of the question. I believe the main reason for this is Haskell's association with category theory. $\endgroup$ – Martin Berger Jan 10 '13 at 0:02
13
$\begingroup$

A short answer: no [but this is only an opinion]

Don't go to Category Theory or any other theoretical domain to become good in Haskell. Learn functional programming techniques, such as tail recursion, map, reduce, and others. Read as much code as you can. Implement as many ideas as you can. If you have issues, read and read.

If you want a good theoretical reference to learn Haskell and other functional programming paradigms then have a look at: An Introduction to Functional Programming Through Lambda Calculus, Greg Michaelson (available online). ... There are other similar books.

$\endgroup$
  • 1
    $\begingroup$ I raise an eyebrow at this, because "tail recursion" is usually not important to programming in Haskell due to laziness. Nevertheless, "learn by doing" is almost always good advice. $\endgroup$ – Dan Burton Oct 30 '13 at 16:57
  • $\begingroup$ @DanBurton .. interesting observation. Let's say then, instead of Haskell, learn erlang or scheme :). [I am not an expert in Haskell, I just picked it because it sounds cool] $\endgroup$ – AJed Oct 30 '13 at 22:38
1
$\begingroup$

Here is a (long) blog post, that gives motivation on how category theory ideas are relevant for practical programming: http://cdsmith.wordpress.com/2012/04/18/why-do-monads-matter/

$\endgroup$
0
$\begingroup$

Category theory is a very sophisticated branch of mathematics and mastering it will unify most of your previous learnings by making them instances of same abstract objects. So it is very useful and very intuitive. But it is vast and broad, and you will find yourself in a plenty of new concepts that will don't even know which one is suitable for your needs and which one you should skip. So your purposeful approach needs choice among concepts, otherwise mastering in it inevitably needs long time and is really not a self study domain.

By the way, I suggest a very well start point for your purpose to be here.

$\endgroup$
  • $\begingroup$ This doesn't really answer the question: is it useful for learning functional programming? Which topics in category theory are useful for Haskell? $\endgroup$ – David Richerby Mar 6 '15 at 22:50
0
$\begingroup$

Category theory has certain but limited use for learning functional programming or in actual practice of functional programming. I recently made a presentation to answer that question. https://www.youtube.com/watch?v=Zau8CxsfxOo

Summary:

  • Functional programmers do not require category theory in order to master the main features and design patterns that FP uses to write better code. For example, one can (and should) first learn how to use monads, functors, liftings, map/filter/fold, etc., in a concrete programming language with specific examples. Category theory will not help master these techniques even though the words "functor" and "monad" originally come from category theory.
  • At a certain point, programmers will encouter examples of typeclasses with laws, and understand why those laws are important in practice.
  • There will be lots of laws. To make some order and system among those laws, we can formulate the laws as a generalized "lifting" type signature with "twisted" function types.
  • We can then use the definitions of category and functor as generalizations that cover the laws of functors, contrafunctors, filterable functors, filterable contrafunctors, monads, applicative functors, applicative contrafunctors, comonads, and perhaps other type classes.
  • I show some examples of categories that are used to describe functors, monads, applicatives, and filterable functors.
  • I cover filterable functors in more detail, with backdrop of category theory, because filterable functors are rarely explained as a separate typeclass.
  • Another example where category theory is useful: "type constructor libraries", i.e. libraries with functions parameterized by a type constructor. Examples of these are free functor / free monad / etc., and Church encoding of types (including recursive type constructors, e.g. the Church encoding of a free monad). Programmers who need to implement these libraries will need to understand how these constructions are defined and what laws need to hold. Category theory provides some limited guidance about that.
  • Conclusion 1: programmers need to learn functional programming and not category theory. The special knowledge required in functional programming (e.g., how to implement and use a free applicative functor in your programming language) is not going to be covered by any book in category theory.
  • Conclusion 2: basic definitions of category theory (category, functor) are useful as condensed formulations of general laws for a number of typeclasses. Unless a programmer has experience dealing with all the different laws of those typeclasses, it is unlikely that the appreciation of category theory will be of much help. At the same time, beyond the five or so basic concepts and definitions (category, functor, natural transformation, monoid, Yoneda identities), any further study of category theory is not likely to be of any use for a practicing functional programmer.
  • Conclusion 3: knowledge of category theory will not help us derive or prove laws for specific typeclasses, and will not help us implement those typeclasses correctly in code. The reason is that category theory is so general that it only talks about laws that apply generally to a large number of very different typeclasses (functor, contrafunctor, monad, filterable, applicative, pointed, etc.). For practical coding, e.g. to verify that our implementation of a specific monad is lawful, we need to learn not category theory but the techniques of symbolic derivation and proof. I am writing a new free textbook ("Science of Functional Programming", https://github.com/winitzki/sofp) to develop and explain these techniques with practical programmers in mind. My book is going to be very light on category theory, because I'm not going to use any advanced abstract concepts unless there is a significant gain for practical work.
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy