What is exactly an indexed functor in Haskell and what are its usages?

Question

When studying functors in Haskell I came up with Functor.Indexed type of functor. This functor defines an operation called imap. I didn't understood its definition and imap signature: imap :: (a -> b) -> f j k a -> f j k b. I tried to find it s formal definition and found only this: http://ncatlab.org/nlab/show/indexed+functor . But it really didn't help me at all. So can someone clarify in more simple words this kind of functor and in what cases should I use it? Thanks.

Answer 1

An indexed functor is, to use spacesuitburritoesque wording, “a container that also contains a mapping”. I.e. a value f j k a will “contain” some sort of morphism(s) j -> k ^{(not necessarily functions, can be more general arrows)} and also values of type a.

For those a values, the container is a functor in the obvious way. In fact the IxFunctor class on its own is pretty boring – an

instance IxFunctor f

is basically the same as

instance Functor (f j k)

Now, where it gets interesting is when you consider the more specific functor classes. This monad one isn't actually in the Indexed module, but I think it makes the point best clear:

class IxPointed f => IxMonad f where
  ijoin :: m j k (m k l a) -> m j l a

compare this side-by-side:

(>>>) ::  (j->k) -> (k->l)   ->   j->l
ijoin :: m j  k   (m k  l a) -> m j  l a
join  :: m        (m      a) -> m      a

So what we do is, while joining the “container-layers”, we compose the morphisms.

The obvious example is IxState. Recall the standard state monad

newtype State s a = State { runState :: s -> (a, s) }

This, when used as a monad, simply composes the s -> s aspect of the function:

  join (State f) = State $ \s -> let (State f', s') = f s in f' s'

so you thread the state first through f, then through f'. Well, there's really no reason we need all the states to have the same type, right? After all, the intermediate state is merely passed on to the next action. Here's the indexed state monad,

newtype IxState i j a = IxState { runIxState :: i -> (a, j) }

It does just that:

  ijoin (IxState f) = IxState $ \s -> let (IxState f', s') = f s in f' s'