How to implement index-core style indexed continuation monad

Question

I have been looking at (and trying to understand) indexed monads recently. I think I have got my head around one style of indexed monad, as described here: A Neighbourhood of Infinity: Beyond Monads.

However, I have found a different style of indexed monad in index-core, which has some parts that seem to correspond to this indexed monad bind with two indexes, for example a similar bind operator !>=. While it clearly has similar changes to the indexes, I can't quite understand how to use these indexes, for example, to control the return types in a continuation monad as with the other style. I would be interested in this style of indexed monad, primarily because it seems to work a lot better for monad transformers - in fact I have not seen an indexed monad transformer (of indexed monads) defined in the other style, only an indexed transformer of regular monads.

I am wondering if anyone could please provide an example of the two result type continuation monad implemented as this style of continuation monad, or point me to other examples of the use of this module to define other indexed monads that make use of two indexes (for instance, the form of the state monad where the type of the state may change). I have been searching for such an example, without much luck, and I haven't managed to successfully implement it myself. I have a feeling it should be obvious, but I've got a bit tied up in the different constructors.

See also a similar question: stackoverflow.com/questions/23887237/… — Tom Ellis

Gabriella Gonzalez Gabriella Gonzalez · Accepted Answer · 2012-12-24T14:52:28

I'm the author of the index-core package, and the answer is that you can. Here's the solution:

{-# LANGUAGE TypeOperators, RankNTypes #-}

import Control.Category.Index
import Control.IMonad
import Data.Functor.Identity

newtype ICont f a i = ICont { runICont :: (a :-> f) -> f i }

Note that I use f instead of r. The rs are going to be the indices.

The implementation of IFunctor and IMonad are identical to the implementation of the ordinary monad (just like the blog post's versions):

instance IFunctor (ICont f) where
    fmapI f m = bindI (returnI . f) m

instance IMonad (ICont f) where
    returnI a = ICont $ \k -> k a
    bindI f m = ICont $ \k -> runICont m $ \a -> runICont (f a) k

The trick is to realize that it reduces to the version you saw in the blog post when f = Identity

  (a -> r2) -> r1
~ (a -> Identity r2) -> Identity r1
~ ((a := r2) r2 -> Identity r2) -> Identity r1
~ ((a := r2) :-> Identity) -> Identity r1
~ ICont Identity (a := r2) r1
~ R ICont Identity r1 r2 a

The only difference is the extra R and Identity noise, which you can abstract away if you choose to match the blog post's version:

type ICont' r1 r2 a = ICont Identity (a := r2) r1

Here's an example of a function written using ICont

-- example ~ (String -> Int) -> Char
-- example ~ ((String := Int) Int -> Identity Int) -> Identity Char
example :: ICont' Char Int String
example = ICont $ \k -> Identity $
    case runIdentity (k (V "Hello")) of
        0 -> 'A'
        _ -> 'B'

The index-core library was inspired by Conor McBride's paper: Kleisli Arrows of Outrageous Fortune. Note that Conor's approach requires greater verbosity than the one in the blog post, but it affords extra features that the one in the blog post does not, mainly in the ability to store more powerful information in the indices that offer even greater flexibility.

What that means for you is that if you do not need those extra features then you should probably use the one you saw in the blog post. However, I highly recommend that you read Conor's paper no matter what you choose, because it is a really excellent paper and shows how powerful Haskell's type system can be.

I didn't implement any of the indexed monads for index-core, mainly because I wrote that library to scratch an itch of mine for another library I wrote. If you want to see the concrete code that uses index-core, just check out version 2.2.0 of the pipes package where I used index-core to implement the indexed free monad transformer. However, I no longer use that type any longer, although I still maintain the index-core package.

If you have any other questions, feel free to ask!

How to implement index-core style indexed continuation monad

1 Answers