Abstracting over Applicative, Alternative, Divisible, and Decidable

Justin Le recently put out a two-part series on “Enhancing Functor Structures Step-By-Step” (Part 1, Part 2). In the footnotes of Part 2, he mentions there’s no combined Applicative/Divisible class:

class DivisibleApplicative f where
  conquerpure :: a -> f a
  divideAp :: (a -> (b, c)) -> (b -> c -> a) -> f b -> f c -> f a

Let’s see if we can build one.

In Ed Kmett’s 2015 talk, Discrimination is Wrong: Improving Productivity, he shows the similarities between Applicative/Alternative/Divisible/Decidable using Day convolution, where *1 and *2 are two different tensor products:

-- Adapted from the slide at 18:10 or so in the video
data Day f g a where
  Day :: ((a *1 b) -> c) *2 f a *2 g b -> Day f g c

data ContraDay f g a where
  ContraDay :: (c -> (a *1 b)) *2 f a *2 g b -> ContraDay f g c

Then:

• Applicative comes from covariant Day convolution with *1 = (,) and *2 = (,)
• Alternative comes from covariant Day convolution with *1 = Either and *2 = (,)
• Divisible comes from contravariant Day convolution with *1 = (,) and *2 = (,)
• Decidable comes from contravariant Day convolution with *1 = Either and *2 = (,)

pure, empty, and conquer can be rearranged so that they each mention the unit of their *1 tensor, and then lined up to reveal a pattern:

-- At 25:00 or so in the video
pureish    :: Applicative f => (()   ->    a) -> f a
emptyish   :: Alternative f => (Void ->    a) -> f a
conquerish :: Divisible   f => (a    ->   ()) -> f a
lose       :: Decidable   f => (a    -> Void) -> f a

And you can do the same with the “liftA2-equivalent” of each class:

-- Not in the video
liftA2 (,)                         :: Applicative f => f a -> f b -> f (a, b)
\l r -> Left <$> l <|> Right <$> r :: Alternative f => f a -> f b -> f (Either a b)
divided                            :: Divisible   f => f a -> f b -> f (a, b)
chosen                             :: Decidable   f => f a -> f b -> f (Either a b)

Bartosz Milewski has a 2018 blogpost where he stands up a class Monoidal and claims that it’s equivalent to Applicative:

class Monoidal f where
  unit :: f ()
  (>*<) :: f x -> f y -> f (x, y)

That claim doesn’t sound quite right to me: without a Functor superclass constraint, any Divisible can also be written in terms of this Monoidal class. If we choose other biendofunctors inside f, we can abstract over Alternative and Decidable too:

{-# LANGUAGE FlexibleContexts, FunctionalDependencies #-}
import qualified Control.Category.Monoidal as C -- From `categories`

class C.Monoidal (->) p => Monoidal f p | f -> p where
  unit :: f (C.Id (->) p)
  mult :: f a -> f b -> f (p a b)
  lunit :: f (C.Id (->) p) -> f a -> f a
  runit :: f a -> f (C.Id (->) p) -> f a

You can define newtype wrappers which show that if you have any of Applicative/Alternative/Divisible/Decidable, you can get a Monoidal instance.

An interesting application is bidirectional parsing/printing. The following type cannot have Functor/Contravariant/Applicative/Alternative/Divisible/Decidable instances, but can have Invariant and Monoidal instances:

-- With Functor/Applicative/Alternative instances
data Parser a

-- With Contravariant/Divisible/Decidable instances
data PrettyPrinter a

data Bidirectional a = B (Parser a) (PrettyPrinter a)

Operations built using Monoidal end up putting (,)s and Eithers all over the place, so generics-eot turns out to be a pretty neat way of building Bidirectionals for any data type with a Generic instance.

I have a library implementing this machinery about 80% ready to publish to Hackage, but I first want to get the core abstraction right. The questions I want to answer:

1. What is this Monoidal class, exactly? I think the instances are lax monoidal functors f from (Hask, p, C.Id (->) p) to either (Hask, (,), ()) or (Hask^op, (,), ()). Is Monoidal a good name for this class? Is there a better one?

2. I don’t especially like the fundep | f -> p, but if I drop it GHC complains. Is there a better way?

3. For types with a Monoidal instance but no Applicative/Alternative/Divisible/Decidable instance, we can’t fmap nor contramap. The Bidirectional type above would admit an Invariant instance, and I feel like most practical uses of this class will be for types which have Invariant instances. Maybe I should just make Invariant f a superclass of Monoidal f p, which would let me default the lunit and runit methods?

4. The Monoidal class feels stuck in-between committing to Haskell-as-it-is-used and trying to be quite general. Control.Category.Monoidal is a little awkward to use because there aren’t many instances, and it’s generalised across other types of arrows so we have to pass in (->) explicitly. The class Assoc from the assoc package is almost what we want, but doesn’t have a subclass with unitors. If it did, we could define Monoidal in terms of that, which is probably more practical.

5. If I break off a unitless superclass from Monoidal (like the classes you find in semigroupoids), I think the result is a lax semi-monoidal functor, which could then abstract over Apply and Alt from semigroupoids, as well as Divise and Decide from functor-combinators. That seems nifty; maybe I should do that before an initial release?

If you have thoughts about this, please share them on the reddit thread.

Update (2020-08-23): After some excellent comments on reddit, I have decided not to push a monoidal functors library to Hackage, for a few reasons:

• It appears that there isn’t a lot of other uses for Invariant functors, and requiring them here is a bit of a kludge.

• Bidirectional parsing/printing can be done with Profunctors, where you work with a data PrinterParser a b = PrinterParser (PrettyPrinter a) (Parser b). The product-profunctors package provides ProductProfunctor and SumProfunctor classes.

  • There is also the work of Xia, Orchard, and Wang on composing bidirectional programs monadically. This work uses a profunctor p a b, where p a is also a Monad.

  • If you have an existing Divisible f and an Applicative g, you can assemble such a Profunctor via Product (Clown f) (Joker g).

• Asad Saeeduddin already has a more mature and more mathematically-thorough library of monoidal functors. It is not yet on Hackage, but includes Semigroupal functors, support for varying both the input and output tensors and support for oplax (semi-)monoidal functors as well (going e.g., f (a, b) -> (f a, f b)).

Update (2020-11-03): I just found the 2004 Pickler Combinators functional pearl. Many of the functions they use can be found in the typeclasses we’ve been discussing (e.g. wrap is invmap), but the paper relies heavily on invmapping partial functions like fromJust. A parser/printer profunctor would probably give us a better way to handle failures.