Add `Mux` and `Demux` - Githubissues

The Applicativetypeclass can be presented in a fashion that makes the fact that it is a lax monoidal functor readily apparent:

class Functor f => Apply f
  where
  zip :: (f a, f b) -> f (a, b)

class Apply f => Applicative f
  where
  pure :: () -> f ()

Sometimes when programming with do notation, we end up using a monad to accomplish a task that requires only an applicative. The reason we can get away with this abuse is that every endofunctor on the category of typed functions is commutative strong, and a commutative strong monad is the same thing as a monoidal monad (in the sense of lax monoidal functor).

So whatever you can do with the laxities of a lax monoidal functor, you can do by jiggling around monadic binds, embeddings of values into the functor using the implicit strengths, and the projections products support.

Of course we're not really using the "monad" baggage we've accumulated in our journey through monad -> trivially commutative strong monad -> monoidal monad. All we're interested in (in this hypothetical situation) is the fact that the functor is lax monoidal.

As a result, we might be unnecessarily precluding the instantiation of our computation at some functor that is lax monoidal (as we need) but not a monad. Fortunately, we have an explicit Applicative class that lets us refine our constraints and demand only what we need.

An analogous situation sometimes exists when we move from functors to profunctors. It has entered the folklore that an Arrow is just a Strong Category (give or take a few laws). So we can use this pair of constraints when we need to use familiar Arrow operations like:

(/\) :: (Category p, Strong p) => p a b -> p c d -> p (a, c) (b, d)

We can implement this by jiggling around composition and the strengths:

l /\ r = first l >>> second r

But it turns out that not every profunctor that supports such an operation (if this is indeed all we need) is simultaneously Strong and Category. Suppose we stick this operation in a class:

class Profunctor p => Mux p
  where
  (/\) :: p a b -> p c d -> p (a, c) (b, d)

If you mentally uncurry the arguments, you can see that this is in fact describing a lax monoidal functor. The monoidal codomain is the category of typed functions under the cartesian product structure, and the monoidal domain is the product of the same monoidal category with its own dual.

Now of course whenever we do have both Strong and Category, we can instantiate this in the obvious way. But consider Kleisli m, which is only a Category when m is a Monad. To be a Mux however, all it requires is for m to be Apply:

instance Apply f => Mux (Kleisli f)
  where
  Kleisli f /\ Kleisli g = Kleisli $ \(a, c) -> liftA2 (,) (f a) (g c)

Similarly, Joker f does not support an instance of Category at all, but given Apply f, it too is an instance of Mux. I haven't done an exhaustive survey of profunctors, these are just the two I needed for my use case, but I would bet there's other examples out there where supporting Mux either admits more instances, or weakens the constraints to provide an instance.

So I think it makes sense to add a class like Mux to purescript-profunctor. I'm not sure there's any sensible way to do hierarchy gymnastics to relate Strong + Category and Mux (we're pretty lucky that in Functor land the strength is trivial and we can have a simple Functor -> Applicative -> Monad hierarchy). It would probably be too big of a breaking change anyway. At any rate, it's not too hard to give a Mux instance using splitStrong if your profunctor is already a Strong Category.

It's also worth mentioning that another useful family of lax monoidal functors is Alternative, which just relates the product and coproduct structures instead of the product structure to itself:

class Functor f => Alt f
  where
  union :: (f a, f b) -> f (Either a b)

class Alt f => Alternative f
  where
  empty :: () -> f Void

This too has a useful analog in profunctors:

class Profunctor p => Demux p
  where
  (\/) :: p a b -> p c d -> p (Either a c) (Either b d)

Which for example can be instantiated for Functor f => Kleisli f and Alt f => Joker f.

Of course there's other monoidal Functors and their Profunctor counterparts (and still more monoidal Profunctors with no Functor counterpart), but they're not as well known. Applicative and Alternative are reasonably popular ones, so I think it makes sense to have their Profunctor counterparts available.

I don't have a good name for these, but for completeness, here's the subclasses that round out the analogy to Apply <-> Applicative and Alt <-> Alternative:

class Mux p => Multiplexer p
  where
  trivial :: p a ()

class Demux p => Demultiplexer p
  where
  impossible :: p Void a

purescript / purescript-profunctor

Add `Mux` and `Demux` #32