# Abstracting over Applicative, Alternative, Divisible, and Decidable

Posted on August 19, 2020 by Jack Kelly

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 `Either`s all over the place, so `generics-eot` turns out to be a pretty neat way of building `Bidirectional`s 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 (Haskop, `(,)`, `()`). 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?

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 `Profunctor`s, 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 `invmap`ping partial functions like `fromJust`. A parser/printer profunctor would probably give us a better way to handle failures.