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.