Can an Applicative instance for this type be created?

Question

As an exploration of how variance works, I've come up with this type that could be both a Functor and a Contravariant depending on its arguments:

newtype Shift f g a = Shift { runShift :: f a -> g a }

It's similar to Endo, except with extra type variables to make the variance of the type ambiguous.

If f is covariant and g is contravariant, then Shift f g is contravariant:

instance (Functor f, Contravariant g) => Contravariant (Shift f g) where
    contramap f (Shift g) = Shift (contramap f . g . fmap f)

And if f is contravariant and g is covariant, then Shift f g is covariant:

instance (Contravariant f, Functor g) => Functor (Shift f g) where
    fmap f (Shift g) = Shift (fmap f . g . contramap f)

It is my understanding that Divisible (from Data.Functor.Contravariant.Divisible from the contravariant package) is to Contravariant as Applicative is to Functor. Using this, Shift can be extended to be an instance of Divisible as well:

instance (Functor f, Divisible g) => Divisible (Shift f g) where
    conquer = Shift (const conquer)
    divide f (Shift g) (Shift h) = Shift $
        \x -> case unzipF (fmap f x) of
            (b,c) -> divide f (g b) (h c)
unzipF :: Functor f => f (a,b) -> (f a,f b)
unzipF x = (fmap fst x, fmap snd x)

Because the constraint on Divisible (Shift f g) is (Functor f, Divisible g), I would expect this to "flip" accordingly for an Applicative instance, e.g.

instance (Contravariant f, Applicative g) => Applicative (Shift f g) where { ... }

However, I can't figure out how to fill in the details. My unfinished implementation requires a function like this:

unzipC :: Contravariant f => f (a,b) -> (f a,f b)

but I can't think of a solution to this that doesn't use fmap.

Here's the implementation in full:

instance (Contravariant f, Applicative g) => Applicative (Shift f g) where
    pure x = Shift (const (pure x))
    liftA2 f (Shift g) (Shift h) = Shift $
        \x -> case unzipC (contramap (uncurry f) x) of
            (a,b) -> liftA2 f (g a) (h b)

So, does such an unzipC even exist? If not, is it still possible to salvage an Applicative (Shift f g) instance?

user_7509065 · Answer

No, such a (total) function can't exist. Observe that it would allow you to construct a value of type Void:

import Data.Functor.Contravariant
import Data.Void

unzipC :: Contravariant f => f (a,b) -> (f a,f b)
unzipC = undefined

uhoh :: Void
uhoh = getOp (fst $ unzipC $ Op snd) ()

I'm not sure whether there's another way to write the instance you want yet. I'll edit this answer when/if I figure that out.

Can an Applicative instance for this type be created?

1 Answers