Sunday, March 28, 2010

A Partial Ordering of some Category Theory applied to Haskell

I've had a few requests from people wanting to teach themselves applications of Category Theory to Haskell based on posts I've made. I've made things difficult by posting stuff at random levels of difficulty and without any kind of organising thread through them. So here's an attempt to list a bunch of posts related to aspects of category theory. I've grouped them by themes and within each theme I've tried to list the articles in order of difficulty. Unfortunately there can be big gaps between one article and the next as none of this material was intended to be linked together continuously. Nonetheless, I hope this is of some help.

First a warning: Category Theory Screws You Up!.

The first theme has to be monads of course. But don't forget: monads don't do anything. They're simply an interface to something that you must already have implemented some other way. So don't believe all that hype about how monads are what allow Haskell to use side effects and I/O.
  1. If you just want to use IO and don't care about monads: The IO Monad for People who Simply Don't Care

  2. This gets more hits than anything else on my blog: You Could Have Invented Monads! (And Maybe You Already Have.)

  3. The Trivial Monad

  4. Homeland Security Threat Level Monad

  5. Monads, Kleisli Arrows, Comonads and other Rambling Thoughts

  6. The idea that monads give a way to describe substitutions in a tree forms the basis for this and the next two posts: Variable substitution gives a...

  7. Monads are Trees with Grafting

  8. Where do monads come from?

  9. From Monoids to Monads

  10. Some thoughts on reasoning and monads

  11. The Mother of all Monads

  12. Beyond Monads

Fold and Unfold
I think this is one of the great applications of Category Theory to Computer Science. Structural recursion can be characterised really nicely in terms of F-algebras. That's cool. But even cooler is that when you dualise the definitions you get a great way to look at non-terminating computations on things like streams.
  1. Data and Codata

  2. Coalgebras and Automata

  3. Purely functional recursive types in Haskell and Python

Commutative Monads and Vector Spaces
Trying to order these is tricky. I'm not sure I define the term commutative monad until the talk.
  1. I realised a while back that the operation to build a vector space from a basis is a monad. In fact, like many well known algebraic structures, we get a commutative monad. Monads for vector spaces, probability and quantum mechanics pt. I

  2. Monads, Vector Spaces and Quantum Mechanics pt. II

  3. Trace Diagrams with Monads

  4. A talk this time: Commutative Monads, Diagrams and Knots

  5. And what happens when you try to use a non-commutative monad when a commutative monad is expected: Why isn't ListT a monad?

I'm not sure the killer application for comonads has been found yet. But I do think they're good for things like dataflow and cellular automata fit the comonad model very well:
  1. Evaluating cellular automata is comonadic

  2. Comonadic Arrays

  3. Comonads and reading from the future

  4. The Monads Hidden Behind Every Zipper

  5. Categories of polynomials and comonadic plumbing

Category Theory
And these are generally categorical articles
  1. You Could Have Defined Natural Transformations

  2. Reverse Engineering Machines with the Yoneda Lemma

  3. A Yonedic Addendum

  4. Applying the Yoneda lemma to memoize functions that at first seem unmemoizable: Memoizing Polymorphic Functions with High School Algebra and Quantifiers

  5. Products, Limits and Parametric Polymorphism

  6. Dinatural Transformations and Coends

  7. The goal here was not to understand what Category Theory applies to Haskell, but how Haskell code can be interpreted in other categories: "What Category do Haskell Types and Functions Live In?"

  8. A first step towards 2-category theory: The Interchange Law


Patai Gergely said...

IMHO there are at least two posts missing from this collection: Rewriting Monadic Expressions with Template Haskell and Programming with impossible functions, or how to get along without monads.

Patai Gergely said...

IMHO there are at least two posts missing from this collection: Rewriting Monadic Expressions with Template Haskell and Programming with impossible functions, or how to get along without monads.

sigfpe said...

I left those out as they're drifting away from the category theoretical aspects. But I am about to add another link...

idlecycle said...

Great stuff, Dan! On behalf of all the people who have been nagging.. err, I mean asking you on Haskell Café to compile your Monad tutorials I wanna say thanks :)

Blog Archive