[Haskell-beginners] Capture the notion of invertible

[Brent Yorgey]

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
>