Hi Mateusz, Can you please explain what you mean by "properly"? -Brent On Sat, Sep 13, 2014 at 3:10 PM, Mateusz Kowalczyk wrote:

On 09/13/2014 07:12 PM, trevor cook wrote:

...

Jason, John,

Thanks for the in depth descriptions, it was just what I was looking for.

Trevor

_______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe

Hi,

Please set up your client to reply to threads properly or it makes it very difficult for others to follow.

-- Mateusz K. _______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe

On 09/13/2014 10:00 PM, Tom Ellis wrote:

On Sat, Sep 13, 2014 at 03:56:32PM -0400, Brent Yorgey wrote:

...

Hi Mateusz,

Can you please explain what you mean by "properly"?

I'm not Mateusz, but from my point of view setting the "References:" and "In-Reply-To:" headers would be helpful, as would be quoting the message that is being replied to.

Tom _______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe

Precisely the above. As seen at [1], there are 3 top-level threads from the user in question and if you sort by most recent activity in thread, it makes it even harder to find the actual discussion. [1]: http://fuuzetsu.co.uk/images/1410710789.png -- Mateusz K.

On Sun, Sep 14, 2014 at 1:18 PM, Albert Y. C. Lai wrote:

It may be useful to exchange notes on which buttons to press to get which behaviour.

Probably the big obvious COMPOSE button instead of the potentially less obvious left-arrow icon at top right of the message header. -- brandon s allbery kf8nh sine nomine associates allbery.b@gmail.com ballbery@sinenomine.net unix, openafs, kerberos, infrastructure, xmonad http://sinenomine.net

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