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