Re: [Haskell-beginners] Capture the notion of invertible

Hi Javran, On Thu, Mar 20, 2014 at 04:25:07PM -0400, Javran Cheng wrote:

I thought every Monad is a Category because I see "instance Monad m => Category (Kleisli m)" in Control.Category,

This does not say "every Monad is a Category". It says "Kleisli m is a Category whenever m is a Monad". So you could say "every Monad *gives rise to* (not *is*) a Category".

So what are the other ways?

There is another construction called the Eilenberg-Moore category of a monad. I have never seen anyone encode it in Haskell; it would actually be difficult since the objects of the category would not be Haskell types but monad algebras (though I'm sure it is possible). The Category class can only encode categories whose objects are Haskell types.

I tried to do the exercise:

newtype Endomorphism cat a = E { runE :: cat a a }

instance Category cat => Monoid (Endomorphism cat a) where mempty = E id (E g) `mappend` (E f) = E (g . f)

Is this what you meant?

Yes, exactly right. -Brent

...

Date: Thu, 20 Mar 2014 09:47:30 -0400 From: Brent Yorgey To: beginners@haskell.org Subject: Re: [Haskell-beginners] Capture the notion of invertible Message-ID: <20140320134730.GA4285@seas.upenn.edu> Content-Type: text/plain; charset=us-ascii

On Thu, Mar 20, 2014 at 02:18:12AM -0400, Javran Cheng wrote:

...

Off topic:

This is not off topic for the beginners list at all. =)

...

This comment makes perfect sense to me, because "monoid-like" reminds me of Data.Monoid, which does not totally capture what I know about monoid: monad is "just a monoid in the category of endofunctors"

The "monoid" being referred to here is a very generalized sense of the word, and is quite different from (though distantly related to) Haskell's Monoid type class.

...

but Monad is not in any sense fit into a Monoid. Here I find that when I talk about "monoid-like", I actually refer to Category, and Monad is an instance of Category, which backs up my guess.

"Monad is an instance of Category" --- this doesn't really make sense as stated. It's certainly not true that every instance of Monad is also an instance of Category; the kinds don't even match. It is true that you can build a Category out of a Monad, though there are actually several ways to do so. The most well-known in the Haskell world is Kleisli, but there are other ways.

...

In a word, can I say that when talking about reducing data (Sum, Product, etc.), I'm referring to Monoid, and when I talking about monoid-like composition, I'm referring to Category?

"monoid-like composition" can refer to Monoid too. The essential difference is *types*: in particular you can think of a Category as a "typed Monoid": with a Monoid, *any* two things can be composed. With a Category, you can only compose things whose types match. So conversely you can also think of a Monoid as a "Category with only one type". As an (easy) exercise:

newtype Endomorphism cat a = E (cat a a)

instance Category cat => Monoid (Endomorphism cat a) where ...

-Brent

...

Javran

...

Date: Tue, 18 Mar 2014 02:48:21 +0700 From: Kim-Ee Yeoh To: The Haskell-Beginners Mailing List - Discussion of primarily beginner-level topics related to Haskell Subject: Re: [Haskell-beginners] Capture the notion of invertible functions Message-ID: Content-Type: text/plain; charset="iso-8859-1"

...

When you're talking about invertible functions, the idea you're probably reaching for is an isomorphism -- that is, we want the function to have certain nice properties on top of just being a map from a -> b with an inverse map from b -> a.

The usual meaning of 'f is invertible' is that it is both left- and right-invertible, thus making it bijective: see first bullet in [1].

Here you're alluding to f being merely left-invertible, something I don't see mentioned in OP.

...

You also want the function to be a bijection, which is captured in the notion of an isomorphism.

I'm reminded of a reddit convo where the idea was tossed out that semigroups should always be promoted to monoids [2].

I argued no. I also cited a case where a supposedly nicer monoid causes more problems for a ghc hacker than the true semigroup [3].

Having structure is nice. And sometimes we just have to work with what's given to us.

Category theory calls a /monomorphism/ something that's strictly weaker than left-invertible. An arrow that's (additionally) left-invertible corresponds to a /split mono/.

Hence in order of _decreasing_ niceness: Iso, Split mono, Mono. As research uncovers more interesting phenomena, this sequence will continuing growing to the right.

We can't always impose that niceness because that nukes whatever we're studying. So we gotta respect the situation. And given lemons, make lemonade.

[1] http://en.wikipedia.org/wiki/Bijection,_injection_and_surjection#Bijection

[2] http://www.reddit.com/r/haskell/comments/1ou06l/improving_applicative_donota...

[3] http://www.reddit.com/r/haskell/comments/1ou06l/improving_applicative_donota...

-- Javran (Fang) Cheng _______________________________________________ Beginners mailing list Beginners@haskell.org http://www.haskell.org/mailman/listinfo/beginners

---

Beginners mailing list Beginners@haskell.org http://www.haskell.org/mailman/listinfo/beginners