Problems in defining an applicative instance

Question

Suppose that I'm wanting to define a data-type indexed by two type level environments. Something like:

data Woo s a = Woo a | Waa s a

data Foo (s :: *) (env :: [(Symbol,*)]) (env' :: [(Symbol,*)]) (a :: *) =
     Foo { runFoo :: s -> Sing env -> (Woo s a, Sing env') }

The idea is that env is the input environment and env' is the output one. So, type Foo acts like an indexed state monad. So far, so good. My problem is how could I show that Foo is an applicative functor. The obvious try is

instance Applicative (Foo s env env') where
    pure x = Foo (\s env -> (Woo x, env))
    -- definition of (<*>) omitted.

but GHC complains that pure is ill-typed since it infers the type

    pure :: a -> Foo s env env a

instead of the expected type

    pure :: a -> Foo s env env' a

what is completely reasonable. My point is, it is possible to define an Applicative instance for Foo allowing to change the environment type? I googled for indexed functors, but at first sight, they don't appear to solve my problem. Can someone suggest something to achieve this?

Answer 1

Your Foo type is an example of what Atkey originally called a parameterised monad, and everyone else (arguably incorrectly) now calls an indexed monad.

Indexed monads are monad-like things with two indices which describe a path through a directed graph of types. Sequencing indexed monadic computations requires that the indices of the two computations line up like dominos.

class IFunctor f where
    imap :: (a -> b) -> f x y a -> f x y b

class IFunctor f => IApplicative f where
    ipure :: a -> f x x a
    (<**>) :: f x y (a -> b) -> f y z a -> f x z b

class IApplicative m => IMonad m where
    (>>>=) :: m x y a -> (a -> m y z b) -> m x z b

If you have an indexed monad which describes a path from x to y, and a way to get from y to z, the indexed bind >>>= will give you a bigger computation which takes you from x to z.

Note also that ipure returns f x x a. The value returned by ipure doesn't take any steps through the directed graph of types. Like a type-level id.

A simple example of an indexed monad, to which you alluded in your question, is the indexed state monad newtype IState i o a = IState (i -> (o, a)), which transforms the type of its argument from i to o. You can only sequence stateful computations if the output type of the first matches the input type of the second.

newtype IState i o a = IState { runIState :: i -> (o, a) }

instance IFunctor IState where
    imap f s = IState $ \i ->
        let (o, x) = runIState s i
        in (o, f x)

instance IApplicative IState where
    ipure x = IState $ \s -> (s, x)
    sf <**> sx = IState $ \i ->
        let (s, f) = runIState sf i
            (o, x) = runIState sx s
        in (o, f x)

instance IMonad IState where
    s >>>= f = IState $ \i ->
        let (t, x) = runIState s i
        in runIState (f x) t

---

Now, to your actual question. IMonad, with its domino-esque sequencing, is a good abstraction for computations which transform a type-level environment: you expect the first computation to leave the environment in a state which is palatable to the second. Let us write an instance of IMonad for Foo.

I'm going to start by noting that your Woo s a type is isomorphic to (a, Maybe s), which is an example of the Writer monad. I mention this because we'll need an instance for Monad (Woo s) later and I'm too lazy to write my own.

type Woo s a = Writer (First s) a

I've picked First as my preferred flavour of Maybe monoid but I don't know exactly how you intend to use Woo. You may prefer Last.

I'm also soon going to make use of the fact that Writer is an instance of Traversable. In fact, Writer is even more traversable than that: because it contains exactly one a, we won't need to smash any results together. This means we only need a Functor constraint for the effectful f.

-- cf. traverse :: Applicative f => (a -> f b) -> t a -> f (t b)
traverseW :: Functor f => (a -> f b) -> Writer w a -> f (Writer w b)
traverseW f m = let (x, w) = runWriter m
                in fmap (\x -> writer (x, w)) (f x)

Let's get down to business.

Foo s is an IFunctor. The instance makes use of Writer s's functor-ness: we go inside the stateful computation and fmap the function over the Writer monad inside.

newtype Foo (s :: *) (env :: [(Symbol,*)]) (env' :: [(Symbol,*)]) (a :: *) =
    Foo { runFoo :: s -> Sing env -> (Woo s a, Sing env') }

instance IFunctor (Foo s) where
    imap f foo = Foo $ \s env ->
        let (woo, env') = runFoo foo s env
        in (fmap f woo, env')

We'll also need to make Foo a regular Functor, to use it with traverseW later.

instance Functor (Foo s x y) where
    fmap = imap

Foo s is an IApplicative. We have to use Writer s's Applicative instance to smash the Woos together. This is where the Monoid s constraint comes from.

instance IApplicative (Foo s) where
    ipure x = Foo $ \s env -> (pure x, env)
    foo <**> bar = Foo $ \s env ->
        let (woof, env') = runFoo foo s env
            (woox, env'') = runFoo bar s env'
        in (woof <*> woox, env'')

Foo s is an IMonad. Surprise surprise, we end up delegating to Writer s's Monad instance. Note also the crafty use of traverseW to feed the intermediate a inside the writer to the Kleisli arrow f.

instance IMonad (Foo s) where
    foo >>>= f = Foo $ \s env ->
        let (woo, env') = runFoo foo s env
            (woowoo, env'') = runFoo (traverseW f woo) s env'
        in (join woowoo, env'')

---

Addendum: The thing that's missing from this picture is transformers. Instinct tells me that you should be able to express Foo as a monad transformer stack:

type Foo s env env' = ReaderT s (IStateT (Sing env) (Sing env') (WriterT (First s) Identity))

But indexed monads don't have a compelling story to tell about transformers. The type of >>>= would require all the indexed monads in the stack to manipulate their indices in the same way, which is probably not what you want. Indexed monads also don't compose nicely with regular monads.

All this is to say that indexed monad transformers play out a bit nicer with a McBride-style indexing scheme. McBride's IMonad looks like this:

type f ~> g = forall x. f x -> g x

class IMonad m where
    ireturn :: a ~> m a
    (=<?) :: (a ~> m b) -> (m a ~> m b)

Then monad transformers would look like this:

class IMonadTrans t where
    ilift :: IMonad m => m a ~> t m a

Answer 2

Essentially, you're missing a constraint on Sing env' - namely that it needs to be a Monoid, because:

• you need to be able to generate a value of type Sing env' from nothing (e.g. mempty)
• you need to be able to combine two values of type Sing env' into one during <*> (e.g. mappend).

You'll also need to the ability combine s values in <*>, so, unless you want to import SemiGroup from somewhere, you'll probably want that to be a Monoid too.

{-# LANGUAGE KindSignatures #-}
{-# LANGUAGE DataKinds #-}
{-# LANGUAGE FlexibleContexts #-}
{-# LANGUAGE DeriveFunctor #-}
module SO37860911 where
import GHC.TypeLits (Symbol)
import Data.Singletons (Sing)

data Woo s a = Woo a | Waa s a 
  deriving Functor

instance Monoid s => Applicative (Woo s) where
  pure = Woo 
  Woo f <*> Woo a = Woo $ f a 
  Waa s f <*> Woo a = Waa s $ f a 
  Woo f <*> Waa s a = Waa s $ f a 
  Waa s f <*> Waa s' a = Waa (mappend s s') $ f a 

data Foo (s :: *) (env :: [(Symbol,*)]) (env' :: [(Symbol,*)]) (a :: *) =
     Foo { runFoo :: s -> Sing env -> (Woo s a, Sing env') }
  deriving Functor

instance (Monoid s, Monoid (Sing env')) => Applicative (Foo s env env') where
  pure a = Foo $ \_s _env -> (pure a, mempty)
  Foo mf <*> Foo ma = Foo $ \s env -> case (mf s env, ma s env) of
    ((w,e), (w',e')) -> (w <*> w', e `mappend` e')