What is a cocartesian comonoid, and what is a cocartesian comonoidal functor?

Question

I've been experimenting with monoids and Distributives lately, and I think I've found something of interest (described in my answer) - are these already known structures? (I've been unable to find any reference to them online, and I don't think I've missed some reason they would be nonsensical)

If not previously known, do they seem useful, or interesting to anyone who isn't me?

The questions that lead me here are:

1. What happens if you swap products for sums in comonoids?
2. What happens if you swap products for sums in comonoidal functors (coapplicatives, coalternatives, codivisibles, codecidables)? (Only somewhat answered for the first two)

Answer 1

The following is fairly light on the laws behind these structures, as they are a recent product of experimentation.

First, the cocartesian comagma, plus identity:

-- modified to an equivalent definition for clarity
class Semigroup a where
    (<>) :: (a,a) -> a
class Semigroup a => Monoid a where
    mempty :: () -> a

class Split a where
    split :: a -> Either a a
class Idsplit a where
    void :: a -> Void

These are datatypes with an inherent ability to branch - to be a proper comonoid, this branching should not change its value (due to a neat typeclass instance for functions), but that leads to a far less interesting typeclass for the purposes described here.

Here's that instance for functions, corresponding to the monoid-requiring Divisible instance for Op:

instance Split r => Alt ((->) r) where
    (<!>) :: (r -> a) -> (r -> a) -> (r -> a)
    f1 <!> f2 = either f1 f2 . split
instance Idsplit r => Alternative ((->) r) where
    (<|>) = (<!>)
    empty = absurd . void

This will not be associative unless Split is lawful, unfortunately - but I think its non-associative form could still be of use?

It is also possible to define an Unfoldable typeclass, similar to Foldable for monoids, Foldable1 for semigroups, and their theoretical further family members:

class Unfoldable l where
    unfoldMap :: Split m => (m -> e) -> (m -> l e)
instance Unfoldable [] where
    unfoldMap strat root = case strat root of
        Left m -> []
        Right m -> m : unfoldMap strat root

newtype Unfolder a = Unfolder { getUnfolder :: (a, a -> Maybe a) }
instance Split (Unfolder a) where
    
unfoldr :: (a -> Maybe (e,a)) -> (a -> [e])
unfoldr strat root = unfoldMap
    (fst . fst . getUnfolder)
    (Unfolder ((undefined, root), (strat . snd)))
-- uses Unfolder (e,a) similar to Endo a in foldr
-- the undefined will be dropped by list's instance of Unfoldable, and so is safe

Next: what I think is a "cocartesian coalternative functor":

class Functor f => Match f where
    matchWith :: (c -> Either a b) -> f c -> Either (f a) (f b)
class Match f => Matchable f where
    voidWith :: (a -> Void) -> f a -> Void

-- Maybe is a Match, but not a Matchable due to Nothing
instance Match Maybe where
    matchWith _ Nothing = Left Nothing
    matchWith choose (Just a) = bimap Just Just $ choose a
-- this won't work
instance Matchable Maybe where
    voidWith void (Just a) = void a
    voidWith void Nothing = ?????

-- Pick always needs an a value, and so is Matchable as well
data Pick a = Pick1 a | Pick2 a
    deriving Functor
instance Match Pick where
    matchWith choose (Pick1 a) = bimap Pick1 Pick1 $ choose a
    matchWith choose (Pick2 a) = bimap Pick2 Pick2 $ choose a
instance Matchable Pick where
    voidWith void (Pick1 a) = void a
    voidWith void (Pick2 a) = void a

For algebraic datatypes, Match describes functors with at most one value in each constructor (which can then be observed and pattern-matched over).

Matchable describes functors with exactly one value in each constructor (so an uninhabited value leads to an uninhabited functor).

I believe Matchable is strictly weaker than a Traversable typeclass that traverses with Functors instead of Applicatives, but have not proven this - this would correspond to all Distributives being Applicative. (All algebraic datatypes with exactly one parameter value in each constructor are both Matchable and Traversable.)

class Functor l => FTraversable l where
    ftraverse :: Functor f => (a -> f b) -> (l a -> f (l b))

instance FTraversable f => Match f where
    matchWith choose fc = 
        let fab = fmap choose fc :: f (Either a b)
            afb = fsequence fab :: Either a (f b)
            bfa = fsequence (fmap swap fab) :: Either b (f a)
        in  case (afb, bfa) of
                (Left a, Right (f a)) -> Left (f a)
                (Right (f b), Left b) -> Right (f b)
                (_, _) -> undefined -- impossible?

instance FTraversable f => Matchable f where
    voidWith void fa = (absurd1 :: forall a. V1 a -> Void) . ftraverse ((absurd :: Void -> V1 ()) . void) $ fa

instance Matchable l => FTraversable l where
    ftraverse strat la = ???

Matchables seem interesting to me, being a part of the extended applicative family that I've been unable to find any reference to, but they really come into their own with Distributive functors from the 'distributive' library (the dual of Traversables).

Normal Distributives are isomorphic to Reader r for some r, and are famously (I presume famously, at least? It seems well known) equivalent to Representable functors, or right adjoints in Hask. Interpreted for algebraic datatypes, they are the algebraic datatypes with exactly one constructor.

These can be extended beyond the Functor-based Distribute, though!

-- all defined using cotraverse instead of distribute, for clarity
-- (which is equivalent to using distribute)

-- isomorphic to Reader r (f a) for some r and Matchable f, not sure which
-- for algebraic datatypes, those with a finite constructor count
class Functor l => MatchableDistributive l where
    cotraverseMatchable :: Matchable f => (f a -> b) -> (f (l a) -> l b)

-- isomorphic to Reader r (f a) for some r and Match f, not sure which
-- for algebraic datatypes, those with a finite non-zero constructor count
class MatchableDistributive l => MatchDistributive l where
    cotraverseMatch :: Match f => (f a -> b) -> (f (l a) -> l b)

-- isomorphic to Reader r a for some r ~ Rep l
-- for algebraic datatypes, those with exactly one constructor
class MatchDistributive l => Distributive l where
    cotraverse :: Functor f => (f a -> b) -> (f (l a) -> l b)

These mirror Traversable ~ (l (), [a]), Traversable1 ~ (l (), NonEmpty a), and the much-rarer functor-traversable ~ (l (), a).

(Of interest: for algebraic datatypes, the each Traversable family member has as many records as the Distributive equivalent has constructors, and vice versa)

(Of interest: just as Coapplicatives are trivial in Hask, so are Comatchables - I expect this can be interpreted as Coapplicatives enabling the many records of Distributive, and Comatchables enabling the many constructors of Traversable?)

Matchables also act like Applicatives for defining generic instances, except that while it's products of Applicatives that have a unique Applicative instance, it's actually sums of Matchables that have a unique instance!

Cocartesian Coapplicatives act as the Alternative equivalent - Cocartesian Coapply can be interpreted as being able to choose which side to take in an 'unzip' operation, and Cocartesian Coapplicative describes a totally uninhabited functor like V1 in generics.

class Functor f => Bias f where
    biasWith :: (c -> (a,b)) -> f c -> Either (f a) (f b)
class Bias f => Biasable f where
    devoidWith :: (a -> ()) -> (f a -> Void)

-- empty analogue
devoid :: Biasable f => f a -> Void
devoid = devoidWith (const ())

-- (<|>) analogue
biasing :: Bias f => f a -> Either (f a) (f a)
biasing = biasWith (\a -> (a,a))

In summary:

• There are 4 types of monoid family here (monoid, comonoid, cocartesian monoid, cocartesian comonoid), of which the first and last are non-trivial in Hask. Maybe there are 6 if you include These as well as (,) and Either?

• There are 6 members of the applicative family here (applicative, alternative, divisible, decidable, matchable, biasable), plus the trivial coapplicative and comatchable - this could presumably be filled out further to a total of 16 members! Or 36 including These as above

• Matchable functors enable weaker versions of Distributive - where Distributive's data is always present, the data in a Match-Distributive is only sometimes present, or potentially never present in a Matchable-Distributive

(These-wise applicative = Align from the 'semialign' package, but with fewer laws? corresponding to the relationship between applicatives and zips, seen in ZipList's typeclass instances?)

Edit: A more symmetric Unfoldable instance for lists

It is possible to leave the choice to bias left or right until after-the-fact, using a similar method to the Monofoldable typeclass.

class MonoUnfoldable l e | l -> e where
    unfoldMapMono :: Split m => (m -> e) -> (m -> l)
-- this will always create an infinite list
instance MonoUnfoldable [Either a a] (Either a a) where
    unfoldMapMono strat m = strat m : unfoldMapMono strat m

pickLefts, pickRights :: [Either a a] -> [a]
pickLefts (Left a : as) = a : pickLefts as
pickLefts _ = []
pickRights (Right a : as) = a : pickRights as
pickRights _ = []

However, useful instances of Split for unfolding will be value-changing, and will have already chosen a left/right bias for these value changes. For example:

instance Num n => Split (Sum n) where
    split (Sum n)
        | n > 0     = Right $ Sum (n-1)
        | otherwise = Left  $ Sum (n-1)

unfoldMap getSum (Sum 10) = [9,8,7,6,5,4,3,2,1,0]

As such, the asymmetry is practically inherent to the process, and all that is needed is to be consistent about whether Left or Right signal an end-point for listlike (linear, finite) unfolds.

Answer 2

In this answer (which I ideally should have written some time before the first anniversary of the question, but alas), I will mostly stick to covariant monoidal functors in order to keep the scope manageable, though there will be opportunity to consider some of the other aspects of the question and of your self-answer.

Another editorial choice of mine will be exercising restraint in using "co-" to name things. That's not just because it's easy to get lost in a soup of prefixes when, as you note, there is a baseline of sixteen hypothetical monoidal functor classes, but also because for each of them there generally is more than one plausible candidate for the "co-" moniker. For instance, consider Applicative (cast into a by-the-book monoidal functor signatures):

class Functor f => Applicative f where
    zipped :: (f a, f b) -> f (a, b)
    unit :: () -> f ()
    -- zipped = uncurry (liftA2 (,))
    -- unit = const (pure ())

One might want to adopt as "coapplicative" its straightforward oplax monoidal counterpart, obtained by switching from Hask to Hask^op (and thus turning around the arrows of the methods) while keeping (,) as the tensor product:

class Functor f => Unzip f where
    unzip :: f (a, b) -> (f a, f b)
    trivialU :: f () -> ()

These combinators have a lawful implementation for every Functor, with unzip = fmap fst &&& fmap snd and trivialU = const (). Notably, this is the coapplicative alluded to by the distributive documentation when it notes that:

Due to the lack of non-trivial comonoids in Haskell, we can restrict ourselves to requiring a Functor rather than some Coapplicative class.

Besides the triviality of Unzip, another plausible objection to calling it coapplicative is that a thorough dualisation of applicative should also replace (,) (the product in Hask) with Either (the product in Hask^op). Doing so leads to your Matchable class, which I'll display here in a presentation borrowed from a post by Conor McBride :

class Functor f => Decisive f where
    orwell :: f (Either a b) -> Either (f a) (f b)
    nogood :: f Void -> Void

(It is worth noting that similar questions arise when switching from covariant to contravariant functors. While replacing Functor with Contravariant in the signatures of Applicative leads to Divisible, if the tensor products are also dualised in a compatible way we end up with Decidable instead. Furthermore, as argued in my Divisible and the monoidal quartet blog post, Decidable mirrors Applicative more closely than Divisible.)

While at first it might look like only functors holding exactly one value can be Decisive, that only holds if we require orwell to be an isomorphism. In particular, as McBride highlights, any comonad (or really, any functor with something to play the role of extract) can be made Decisive:

orwellW :: Comonad w => w (Either a b) -> Either (w a) (w b)
orwellW u = case extract u of
    Left a -> Left $ either id (const a) <$> u
    Right b -> Right $ either (const b) id <$> u

nogoodW :: Comonad w => w Void -> Void
nogoodW = extract

orwellW uses the result of extract as a default value, in order to redact one of the Either cases. For demonstrative purposes, here is how it might be deployed in implementing a filter-resembling operation which, instead of merely removing rejected, replaces them with a default:

import Data.List.NonEmpty (NonEmpty(..))
import qualified Data.List.NonEmpty as N

redact :: (a -> Bool) -> a -> [a] -> [a]
redact p d = N.tail . either id id . orwellW . (Right d :|) . map classify
    where
    classify a = if p a then Right a else Left a

ghci> redact (>= 0) 0 [5,-2,3,0,-1,4] 
[5,0,3,0,0,4]

In this implementation, classify uses the predicate to set up an Either-based cosemigroup (in other words, a lawful instance of your Split). orwellW lifts this cosemigroup to non-empty lists (assuming that, for the sake of consistency, p d is True).

(redact, by the way, also brings to mind how a padding zip can be implemented through a suitable Applicative instance for non-empty lists, as demonstrated in this answer, incidentally also written by McBride, though at the moment I'm not sure about how deep the relationship really is.)

On the connections between Decisive/Matchable, Traversable and Distributive, I believe they boil down to all functors holding exactly one value (the left adjoint Hask endofunctors, or your FTraversable) being comonads, and thus Decisive. As far as these are concerned, the less powerful distributive you propose would ultimately be just FTraversable (pushing a left adjoint inside, rather than pulling a right adjoint outside), and right now I don't see how it might generalise to Decisive.

---

Now let's look at Alternative. A by-the-book monoidal functor presentation might be:

class Functor f => Alternative f where
    combined :: (f a, f b) -> f (Either a b)
    nil :: () -> f Void
    -- combined = uncurry (<|>) . bimap (fmap Left) (fmap Right)
    -- nil = const empty

Since we'll need it in a little while, it's worth emphasising we can recover (<|>) by lifting the trivial Either-based monoid:

-- either id id :: Either a a -> a
aplus :: (f a, f a) -> f a
aplus = fmap (either id id) . combined

The straightforward oplax counterpart to Alternative happens to be something familiar:

class Functor f => Filterable f where
    partition :: f (Either a b) -> (f a, f b)
    trivialF :: f Void -> ()

This is actually equivalent to the familiar, mapMaybe-based Filterable class, as covered in detail by Is every Alternative Monad Filterable?. In particular, using the predicate cosemigroup lifting illustrated before with redact leads directly to filter.

We haven't dualised the tensors yet, though. Doing so leads to your Bias (and Biasable, but I'm giving up on the identity in order to have inhabited types):

class Functor f => Bias f where
    biased :: f (a, b) -> Either (f a) (f b)

Lifting the trivial (,)-based comonoid gives us:

biasing :: f a -> Either (f a) (f a)
biasing = biased . fmap (id &&& id)

Bias offers, at least, a classifier of shapes (whether biasing gives out Left or Right depends on the functorial shape of its argument), plus an associated choice between pair components. I say "at least" because dropping the identity leaves Bias with just an associativity law, and said law doesn't rule out changes or rearrangements of the f-shape, as long as they are idempotent and preserve the Left/Right classification.

If Bias being so light on laws is deemed a problem, there is one plausible way of tightening it up somewhat. In order to present it, let's go back to Applicative and Alternative for a moment. While in the monoidal functor formulation Alternative is in principle independent from Applicative, there are a few other possible laws that are sometimes invoked to connect the two classes and better delineate the meaning of Alternative (for commentary on that, see Antal Spector-Zabusky's answer to Confused by the meaning of the 'Alternative' type class and its relationship to other type classes). One of these laws is right distributivity of (<*>) over (<|>):

(u <|> v) <*> w = (u <*> w) <|> (v <*> w)

We can translate that to the vocabulary we're using here...

zipped (aplus (u, v), w) = aplus (zipped (u, w), zipped (v w)

... and make it pointfree, for the sake of easier manipulation:

zipped . first aplus = aplus . bimap zipped zipped . distribR

distribR :: (((a, b), c) -> ((a, c), (b, c))
distribR ((a, b), c) = ((a, c), (b, c))

Now, if Bias is dual to Alt (Alternative sans identity) and Decisive is dual to Applicative, we should be able to dualise the distributivity law for a functor which is both Decisive and Bias:

first biasing . orwell = codistribR . bimap orwell orwell . biasing

codistribR :: Either (Either a c) (Either b c) -> Either (Either a b) c
codistribR = \case
    Left (Left a) -> Left (Left a)
    Left (Right c) -> Right c
    Right (Left b) -> Left (Right b)
    Right (Right c) -> Right c

Adopting this law (and/or the analogous left distributivity law) would forbid biasing (and, by extension, biased) from changing the shape. That's because, by the identity laws of Decisive, orwell can't change shapes, which means, in particular:

first biasing (orwell (Right <$> u)) = Right u

Applying the distributive law then leads to:

codistribR (bimap orwell orwell (biasing (Right <$> u)) = Right u

Which is only possible if biasing leaves the shape untouched. The distributivity law, therefore, can ensure biased is a shape classifier with bundled with a choice between fmap fst and fmap snd. That it all works out so neatly highlights the correspondence not just between Alternative/Alt and Bias, but also between Applicative and Decisive.