reperiendi

Haskell monads for the category theorist

Posted in Category theory, Math, Programming by reperiendi on 2008 January 1

A monad in Haskell is about composing almost-compatible morphisms. Typically you’ve got some morphism f:A\to B and then you think of a reason that you’d rather have f':A \to TB, where T:{\rm Data} \to {\rm Data} is a functor. In Haskell, though, you don’t define functors right out: you define type constructors, which are like the map of objects in a functor. You have to define the map of morphisms separately.

To define the map of morphisms, we have to define unit (aka return) and bind. We define {\rm unit}:(A \multimap B) \to (A \multimap TB) to be the category-theorist’s unit \eta composed with the input. Applying {\rm unit} to f gives

A\xrightarrow{f} B \xrightarrow{\eta} TB.

To compose “half-functored” morphisms like f', we define {\rm bind}:TA \times (A\multimap TB)\to TB like this: given an input a:TA and a morphism like f', bind produces

TA \xrightarrow{Tf'} TTB \xrightarrow{\mu_B} TB.

So a “monad” in Haskell is always the monad for categories, except the lists are of bindable half-functored morphisms like f' rather than lists of composable morphisms.

A side-effect monad has T(A) = A\times E, where E is the data type for the environment on which the morphism is to act. The IO monad is a specific instance of a side-effect monad with the environment being the keyboard queue, disk drive, network, etc.

6 comments

6 Responses

Subscribe to comments with RSS.

  1. sigfpe said, on 2008 January 13 at 9:11 am

    T(A)=AxE isn’t quite the side effect monad. It’s the “constant environment” monad where E contains what you might call “global data”. For side effects you need a mechanism for updating E, so you’d use T(A)=E->AxE.

  2. sigfpe said, on 2008 January 13 at 11:33 am

    Stop programming for a few weeks and I forget everything. Scratch that. You’re right, AxE *is* the side effect monad where you just want to have a writable, but not readable, side effect. E->AxE is the state monad. I just usually think of the state monad as readable and writable side effect.

  3. reperiendi said, on 2008 January 14 at 8:31 am

    Why do you say it’s not readable? A function AxE->AxE is read-write (because it can both depend on E and affect E), and we get that from bind (or, equivalently, from T and mu).

  4. sigfpe said, on 2008 January 22 at 5:47 pm

    When dealing with monads we use ‘bind’ to compose Kleisli arrows A -> T(B).

    For the monad T(A)=AxE a Kleisli arrow is an ordinary arrow A->BxE. That can’t read side effects, only write them.

    For the monad T(A)=E->AxE a Kleisli arrow is A->T(B) = A->(E->BxE) = AxE -> BxE so it can read and write an E.

  5. reperiendi said, on 2008 January 22 at 5:53 pm

    Ah, OK, I see now. Thanks!

  6. reperiendi said, on 2008 October 30 at 9:30 am

    In fact, this monad arises from the adjunction between the functors
    FX = X x E and GX = E -> X
    which give the currying relation
    hom(X x E, Y) =~ hom(X, E -> Y).

    So when I made the mistake of currying above, it wasn’t so far off.


Leave a Reply

You must be logged in to post a comment.