19

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.

MainstreamDeveloper00
  • 8,436
  • 15
  • 56
  • 102
  • 7
    My feeling is that the motivation behind indexed functors can be understood only by looking at indexed _applicative_ functors, or indexed monads. These are just like their non-indexed parts, except that the type (in its index) is allowed to change when using `<*>` or `>>=`. The index can therefore be used e.g. to keep track of how many side effects you have: `allocSomeData :: M Zero One T1` and `allocSomeOtherData :: M One Two T2` then `do d1 <- allocSomeData; d2 <- allocSomeOtherData; return (d1,d2) :: M Zero Two (T1,T2)` and the double allocation is reflected in the type. – chi Jan 04 '15 at 23:46

1 Answers1

20

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'
Community
  • 1
  • 1
leftaroundabout
  • 117,950
  • 5
  • 174
  • 319