[Haskell-cafe] Categorical description for vector-space instance of AdditiveGroup (Maybe a)

[Jason McCarty]

Warning: the following post contains graphic abstract algebra and
category theory, and may not be suitable for all viewers. This post is
literate Haskell.

I want to revisit our bogus instances for Maybe v and provide some
partial resolutions. The IMO best one is given by an operator (*.^) near
the end.

I'll abbreviate the categories AdditiveSemigroup, AdditiveMonoid,
AdditiveGroup as S, M, G.

The package vector-space has the instance

  instance AdditiveGroup v => AdditiveGroup (Maybe v)

which we found was bogus because Just zeroV /= Nothing, so Maybe v
doesn't have well-defined negation.

Let's pretend the class hierarchy is the following.

> {-# LANGUAGE FlexibleContexts, FlexibleInstances, TypeFamilies #-}
> module Maybe where
> import Control.Monad (join)

> class AdditiveSemigroup a where
>   (^+^) :: a -> a -> a -- commutative, associative operator

> class AdditiveSemigroup a => AdditiveMonoid a where
>   zeroV :: a -- unit for (^+^)

> class AdditiveMonoid a => AdditiveGroup a where
>   negateV :: a -> a -- inverse for (^+^) and zeroV

> class Semigroup a where
>   (^*^) :: a -> a -> a -- associative operator

> class Semigroup a => Monoid a where
>   oneV :: a -- unit for (^*^)

> class (AdditiveGroup a, Monoid a) => Ring a
> -- (^*^) distributes over (^+^)

> class (AdditiveMonoid a, Monoid a) => Semiring a
> -- (^*^) distributes over (^+^) and zeroV ^*^ x == zeroV == x ^*^ zeroV

> class (AdditiveSemigroup a, Monoid a) => WeakSemiring a
> -- (^*^) distributes over (^+^)

We can give Hom_C(u, v) some algebraic structure depending on the
category C.

> -- represents Hom_C(u, v) for any concrete category C, which is
> -- unfortunate but too annoying to fix here
> type Hom u v = u -> v
> type End v = Hom v v -- represents End_C(v) = Hom_C(v, v)

Morphisms can be added pointwise:

> instance AdditiveSemigroup v => AdditiveSemigroup (Hom u v) where
>   f ^+^ g = \x -> f x ^+^ g x

> instance AdditiveMonoid v => AdditiveMonoid (Hom u v) where
>   zeroV = const zeroV

> instance AdditiveGroup v => AdditiveGroup (Hom u v) where
>   negateV f = negateV . f

We can view End_C(v) as a monoid with composition:

> instance Semigroup (End v) where
>   f ^*^ g = f . g

> instance Monoid (End v) where
>   oneV = id

(^*^) distributes over (^+^) in End_C(v):

> instance AdditiveSemigroup v => WeakSemiring (End v)

> instance AdditiveMonoid v => Semiring (End v)
>   -- zeroV ^*^ y = zeroV = x ^*^ zeroV too

> instance AdditiveGroup v => Ring (End v)

With this in place, if c, d are objects in categories C, D, then an
action of c on d can be viewed as an element of Hom_C(c, End_D(d)),
provided End_D(d) can be viewed as an object in C. In particular, a
field f acts on a vector space v by a ring morphism f -> End_G(v). For
the purpose of this discussion, we ignore multiplicative inverses; our
scalars can be any ring.

> class Action v where
>   type Scalar v
>   (*^) :: Scalar v -> End v

> class (Action v, Ring (Scalar v), AdditiveGroup v) => VectorSpace v
>   -- (*^) must be a ring morphism

Our structure on Maybe v is:

> instance AdditiveSemigroup v => AdditiveSemigroup (Maybe v) where
>   x ^+^ Nothing = x
>   Nothing ^+^ y = y
>   Just x ^+^ Just y = Just $ x ^+^ y

> instance AdditiveSemigroup v => AdditiveMonoid (Maybe v) where
>   zeroV = Nothing

Since Maybe v isn't a group, we can't define an instance
VectorSpace (Maybe v). But Maybe v is a monoid, so End_M(Maybe v) is a
semiring. So I figured I could just weaken vector spaces a little:

> class (Action v, Semiring (Scalar v), AdditiveMonoid v) => SemiVectorSpace v
>   -- (*^) must be a semiring morphism

I guessed that fmap :: End_M(v) -> End_M(Maybe v) would be a semiring
morphism, which gives:

> instance Action v => Action (Maybe v) where
>   type Scalar (Maybe v) = Scalar v
>   (*^) = fmap . (*^)

  instance SemiVectorSpace v => SemiVectorSpace (Maybe v)
    -- (*^) = fmap . (*^) is a composite of semiring morphisms?

I was wrong about fmap: although fmap preserves (^+^), (^*^), and oneV,
the Just zeroV /= Nothing problem strikes again! We have
fmap (zeroV :: End_M(v)) = fmap (const zeroV), but
(zeroV :: End_M(Maybe v)) = const Nothing.

I should have known better: fmap actually has type
End_S(v) -> End_M(Maybe v), so there's no reason to expect it to
preserve zeroV, even if v happens to have it.

That forces you to weaken things even further:

> class (Action v, WeakSemiring (Scalar v), AdditiveSemigroup v) => WeakSemiVectorSpace v
>   -- (*^) must be a weaksemiring morphism

> instance WeakSemiVectorSpace v => WeakSemiVectorSpace (Maybe v)
> -- (*^) = fmap . (*^) is a composite of weaksemiring morphisms

So this is one "solution," but to me not very satisfying.

Then I thought that, since Maybe is a monad, perhaps Hom_M(v, Maybe v)
and/or Hom_S(v, Maybe v) are monoids under Kleisli composition. Are
these semigroups under Kleisli composition?

> instance Semigroup (Hom v (Maybe v)) where
>   f ^*^ g = join . fmap f . g -- = \x -> g x >>= f

Here join is a semigroup morphism and fmap f is a monoid morphism if f
is a semigroup morphism. In fact, join (zeroV :: Maybe (Maybe v))
== zeroV :: Maybe v, so join is also a monoid morphism. Hence f ^*^ g is
a composite of appropriate morphisms, making Hom_M(v, Maybe v) and
Hom_S(v, Maybe v) semigroups. 

To make this a monoid, we'd have to have oneV = Just, which is a
semigroup morphism, but not a monoid morphism.

> instance Monoid (Hom v (Maybe v)) where
>   oneV = return -- only valid for Hom_S(v, Maybe v)!

This also makes (^*^) distribute over (^+^), so Hom_S(v, Maybe v) is a
semiring if v is an additive semigroup, and Hom_M(v, Maybe v) is a
semiring without one if v is an additive monoid (this is called a
semirng because the "i" in "ring" supposedly stands for "multiplicative
identity!").

> instance AdditiveSemigroup v => Semiring (Hom v (Maybe v))
>   -- only valid for Hom_S(v, Maybe v)

> class (AdditiveMonoid v, Semigroup v) => Semirng v
>   -- (^*^) distributes over (^+^)

> instance AdditiveMonoid v => Semirng (Hom v (Maybe v))
>   -- valid for Hom_M(v, Maybe v)

Now we can hypothetically define a semiring morphism
f -> Hom_S(v, Maybe v) if v is a SemiVectorSpace over f; we just need a
semiring morphism End_M(v) -> Hom_S(v, Maybe v).

> kleisli :: SemiVectorSpace v => (End v -> Hom v (Maybe v)) -> Scalar v
>   -> Hom v (Maybe v)
> kleisli mor = mor . (*^)

This would also define a semirng morphism f -> Hom_M(v, Maybe v) from a
semirng morphism End_M(v) -> Hom_M(v, Maybe v).

Only problem: I can't think of any natual semiring morphism
End_M(v) -> Hom_S(v, Maybe v) or semirng morphism
End_M(v) -> Hom_M(v, Maybe v), except for const (const Nothing).
Perhaps this would be useful if you have such a map handy, but not in
general. If you only want a weaksemir(i)ng morphism, you can use
mor f = Just . f, but this is no better than the WeakVectorSpace
instance above.

What about the CoKleisli category? Maybe isn't just a monad on S, it's
also a comonad on M! In fact, let's look at arbitrary comonads on M.

> class Functor m => MonoidComonad m where
>   coreturn :: AdditiveMonoid v => Hom (m v) v
>   cojoin :: AdditiveMonoid v => Hom (m v) (m (m v))
>   -- cojoin and coreturn must be monoid morphisms
>   -- fmap must take monoid morphisms to monoid morphisms
>   -- cojoin, coreturn, and fmap must satisfy the comonad laws

Hopefully Hom_M(m v, v) is a monoid under CoKleisli composition.

> instance (MonoidComonad m, AdditiveMonoid v)
>   => Semigroup (Hom (m v) v) where
>      f ^*^ g = f . fmap g . cojoin

This is a composite of monoid morphisms if f and g are. The map coreturn
is also a monoid morphism, so Hom_M(m v, v) is a monoid.

> instance (MonoidComonad m, AdditiveMonoid v)
>   => Monoid (Hom (m v) v) where
>      oneV = coreturn

This also implies that (^*^) distributes over (^+^), so I would expect
this to be a semiring. It's easy to check that zeroV ^*^ g == zeroV, but
f ^*^ zeroV doesn't necessarily equal zeroV when v is not cancellative
(m = Maybe and v = Bool with (^+^) = (||) is a counterexample). So this
isn't necessarily a semiring when v is just a monoid.

However, all groups are cancellative, so we get the following better
result.

> instance (MonoidComonad m, AdditiveGroup v) => Ring (Hom (m v) v)

Hom_M(m v, v) is a ring when v is an additive group! Finally, we can get
a ring morphism f -> Hom_M(m v, v) if v is a vector space over f, given
a ring morphism End_G(v) -> Hom_M(m v, v).

> coKleisliWith :: (MonoidComonad m, VectorSpace v)
>   => (End v -> Hom (m v) v) -> Scalar v -> Hom (m v) v
> coKleisliWith mor = mor . (*^)

The obvious candidate for such a morphism is mor f = f . coreturn, and
it's easy to see that mor preserves zeroV and oneV. Moreover,

mor (f ^+^ g) = (f ^+^ g) . coreturn
              = \x -> (f ^+^ g) (coreturn x)
              = \x -> f (coreturn x) ^+^ g (coreturn x)
              = f . coreturn ^+^ g . coreturn
              = mor f ^+^ mor g

mor f ^*^ mor g = (f . coreturn) ^*^ (g . coreturn)
                = f . coreturn . fmap (g . coreturn) . cojoin
                = f . g . coreturn . coreturn . cojoin
                = f . g . coreturn
                = (f ^*^ g) . coreturn
                = mor (f ^*^ g)

So mor also preserves (^+^) and (^*^), making it a ring morphism. Let's
give the result a slick name.

> (*.^) :: (MonoidComonad m, VectorSpace v) => Scalar v -> Hom (m v) v
> (*.^) = coKleisliWith (. coreturn)

Actually, this simplifies a lot:
  s *.^ x = s *^ coreturn x

Since (*.^) is a ring morphism, this satisfies a modified version of the
vector space laws:
  1. oneV *.^ x        = coreturn x
  2. (s1 ^*^ s2) *.^ x = ((*.^) s1 ^*^ (*.^) s2) x
                       = s1 *.^ ((s2 *^) <$> x)
  3. s *.^ (x ^+^ y)   = (s *.^ x) ^+^ (s *.^ y)
  4. (s1 ^+^ s2) *.^ x = (s1 *.^ x) ^+^ (s2 *.^ x)

So what comonads are there on M? Any adjunction (F: C -> M, G: M -> C)
gives rise to a comonad FG: M -> M. The Maybe comonad comes from an
adjunction of semigroups and monoids, where F adds a new zeroV, and G
forgets that a monoid has a zeroV.

> instance MonoidComonad Maybe where
>   coreturn = maybe zeroV id
>   cojoin = fmap return

It seems reasonable to use lists as well, since we all know [v] is the
free monoid on v, giving an adjunction between Haskell types and
monoids. But [v] isn't commutative, you say. It doesn't matter. We can
just use Hom_M'([v], v) instead, where M' is the category of all
monoids. Everything else stays the same.

> instance MonoidComonad [] where
>   coreturn = foldr (^+^) zeroV
>   cojoin = fmap return

We can just as easily use a comonad on G or G', the category of all
groups. For example, the free group functor, the free abelian group
functor, the free abelian monoid functor, and tensoring with a fixed
abelian group are all left adjoints with codomain G', G, M, and G,
respectively, so they give rise to comonads on these categories.
Although, to implement these in Haskell, I think you need an Ord/Eq
constraint (you might get away without it if you restrict to finite-
dimensional vector spaces over finite fields, in which case you also get
the free vector space functor). Abelianization is also a left adjoint,
but it's the identity on vector spaces, so that's rather pointless.
There are probably lots of other examples.

I suspect you could get a monadic version with Kleisli composition to
work too. The problem with Maybe was that it's a monad on S, not M.

In summary, the (*.^) operator is the most flexible and principled
approach I can think of to treat Maybe v like a vector space. Is it
useful? I don't know!

-- 
Jason McCarty <jmccarty at sent.com>