Abstracting over Applicative, Alternative, Divisible, and Decidable

Posted on August 19, 2020 by Jack Kelly
Tags: haskell, coding

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


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 (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?

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:

Previous Post
All Posts | RSS | Atom
Next Post
Copyright © 2020 Jack Kelly
Site generated by Hakyll (source)