How to construct an Applicative instance with constraints (similarly to constructing Monad instances using ContT)

Question

This question deals with constructing a proper Monad instance from something that is a monad, but only under certain constraints - for example Set. The trick is to wrap it into ContT, which defers the constraints to wrapping/unwrapping its values.

Now I'd like to do the same with Applicatives. In particular, I have an Applicative instance whose pure has a type-class constraint. Is there a similar trick how to construct a valid Applicative instance?

(Is there "the mother of all applicative functors" just as there is for monads?)

Sort of guessing at your use-case, but could you make use of the Apply type class, i.e. class Apply f where apply :: f (a->b) -> f a -> f b ? — John L
@JohnL Looks like a good idea, I didn't know about the package. — Petr
Thanks for the link, I was unable to find it last night. One common use case is for DSL's, where you can implement apply and bind easily but it's not possible to lift arbitrary values in, which seems like it might be related to what you're doing. — John L

leftaroundabout leftaroundabout · Accepted Answer · 2014-01-15T00:51:23

What may be the most consistent way available is starting from Category, where it's quite natural to have a restriction to objects: Object!

class Category k where
  type Object k :: * -> Constraint
  id :: Object k a => k a a
  (.) :: (Object k a, Object k b, Object k c)
     => k b c -> k a b -> k a c

Then we define functors similar to how Edward does it

class (Category r, Category t) => Functor f r t | f r -> t, f t -> r where
  fmap :: (Object r a, Object t (f a), Object r b, Object t (f b))
             => r a b -> t (f a) (f b)

All of this works nicely and is implemented in the constrained-categories library, which – shame on me! – still isn't on Hackage.

Applicative is unfortunately a bit less straightforward to do. Mathematically, these are monoidal functors, so we first need monoidal categories. categories has that class, but it doesn't work with the constraint-based version because our objects are always anything of kind * with a constraint. So what I did is make up a Curry class, which kind of approximates this.

Then, we can do Monoidal functors:

class (Functor f r t, Curry r, Curry t) => Monoidal f r t where
  pure :: (Object r a, Object t (f a)) => a `t` f a
  fzipWith :: (PairObject r a b, Object r c, PairObject t (f a) (f b), Object t (f c))
              => r (a, b) c -> t (f a, f b) (f c)

This is actually equivalent to Applicative when we have proper closed cartesian categories. In the constrained-categories version, the signatures unfortunately look very horrible:

  (<*>) :: ( Applicative f r t
           , MorphObject r a b, Object r (r a b)
           , MorphObject t (f a) (f b), Object t (t (f a) (f b)), Object t (f (r a b))
           , PairObject r (r a b) a, PairObject t (f (r a b)) (f a)
           , Object r a, Object r b, Object t (f a), Object t (f b))
       => f (r a b) `t` t (f a) (f b)

Still, it actually works – for the unconstrained case, duh! I haven't yet found a convenient way to use it with nontrivial constraints.

But again, Applicative is equivalent to Monoidal, and that can be used as demonstrated in the Set example.

How to construct an Applicative instance with constraints (similarly to constructing Monad instances using ContT)

3 Answers