[Haskell-beginners] Capture the notion of invertible

Thu Mar 20 21:04:43 UTC 2014

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 <byorgey at seas.upenn.edu>
> > To: beginners at haskell.org
> > Subject: Re: [Haskell-beginners] Capture the notion of invertible
> > Message-ID: <20140320134730.GA4285 at 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 <ky3 at atamo.com>
> >> > To: The Haskell-Beginners Mailing List - Discussion of primarily
> >> >         beginner-level topics related to Haskell <beginners at haskell.org>
> >> > Subject: Re: [Haskell-beginners] Capture the notion of invertible
> >> >         functions
> >> > Message-ID:
> >> >         <CAPY+ZdTyj81gcUaZJfHGeta8rbjxup8ReKHJ=iy7ePzKkQPomQ at mail.gmail.com>
> >> > 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_donotation/ccvtqot?context=1
> >> >
> >> > [3]
> >> > http://www.reddit.com/r/haskell/comments/1ou06l/improving_applicative_donotation/ccy4n2d
> >>
> >>
> >>
> >>
> >>
> >> --
> >> Javran (Fang) Cheng
> >> _______________________________________________
> >> Beginners mailing list
> >> Beginners at haskell.org
> >> http://www.haskell.org/mailman/listinfo/beginners
> >>
> _______________________________________________
> Beginners mailing list
> Beginners at haskell.org
> http://www.haskell.org/mailman/listinfo/beginners