Don't know your monads from your monoids?

A book on Functional programming in Scala is on the tracks, by the authors of Scalaz. A lot of people here have high expectations in terms of improving our functional knowledge through the language.

2011/9/10 Tim P <tim.pigden@optrak.com>

The recent spat following Tony Morris's addendum to the scalaz video
raises a general point:

There are a lot of people like me, coming into the Scala arena from a
java programming background and quite probably no exposure to
functional programming at all or any related mathematical concepts. We
don't know our monads from our monoids.

So what do we do about it?

We can just use scala as a better java (or whatever). Master the
basics of maps, filters passing functions around and use of immutable
data structures. Our programming and our programs will benefit and
we'll confident in the new medium and happily productive.

But sometimes you come on something where you just can't get things to
work. You're pretty sure you ought to be able to do it - you can
always drop in some form of type cast or whatever and carry on and
you're still doing better than you would in java. Or you can start
trying to figure out what it's all about.

For me this happened when I started trying to do a DSL, for others it
may be when they want to remove code smell of code duplication or
think "there must be a better way".

So what do you do?

Asking on this list is one thing. And there's no shortage of "helpful"
responses. But if the people responding are experts already totally
fluent in the domain, and they are giving of their time for no
personal benefit, then it's unreasonable to expect them not to respond
in the vocabulary appropriate to the domain. So when Tony says
something like " For-comprehensions denote monadic computation, while
applicative functors are more general. Let's be clear on that: The
applicative functor interface provides a strict subset of the derived
operations of the monad interface"
he is probably making a perfectly reasonable statement that we might
just find utterly incomprehensible.

So what are we going to do about?

There is a fundamental problem here, none of the available books
really explain this stuff on the scala platform to people who don't
know it already. They'll talk in java-ish friendly terms for most of
it, then maybe drop a little bit in (p 496 in Odersky mentions monads
but it's hardly a proper definition, monoids and applicative functors
don't get a look in). If you're very keen, very smart and very
persistent you can probably work it all out for yourself, in here, in
scala. Maybe the promised book I've seen referenced will help. But I'd
be very surprised if many of the people who "get" scalaz didn't have
an alternative route to this knowledge.

So I think we do have a couple of options: stay as a general, better-
than-java user, or cast around for ways to master some of this arcana.
Personally, I'm learning Haskell (or what might be considered by some
an act of child cruelty, i'm actually learning it with my 14-year
son). I'm not just dipping in, as Tony suggests is possible  - because
I think he's underestimating the difficulties for people like me of
making the paradigm shift. I'm learning it properly. And I'm flagging
up the apparently gnomic utterances of people like Tony and occasional
code fragments (the thread on "occult" scala was excellent in this
respect) so that when I'm happier with the medium I can go back to see
if it's all sunk in.

I guess another option is to go on a course (SkillsMatter in the UK do
some advanced ones) but that's way out of my budget.

If anyone has alternative suggestions for making the transition from
java programmer to someone who gets scalaz it might be useful to share
them. I know this crops up periodically- usually in response for "best
book" suggestions but it might be worth focussing particularly on
learning the hard stuff.


Tim

--
Alex REPAIN
ENSEIRB-MATMECA - student
TECHNICOLOR R&D - intern
BORDEAUX I      - master's student
SCALA           - enthusiast

On Sat, Sep 10, 2011 at 11:26 AM, Tim P wrote:
> I guess another option is to go on a course (SkillsMatter in the UK do
> some advanced ones) but that's way out of my budget.

Much as I'd love to sell you a place on my Advanced Scala course at
Skillsmatter, here's a zero cost option (same venue, Chris Marshall
(aka @oxbow_lakes) speaking),

http://www.meetup.com/london-scala/events/29555921/

In general I'd recommend participating in the London Scala User Group
and any other Scala or FP related groups that you can get to ... you'd
be amazed how much easier monads and monoids are to grasp after a beer
or two ;-)

Cheers,

Miles

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

On 09/10/2011 08:26 PM, Tim P wrote:
> The recent spat following Tony Morris's addendum to the scalaz video
> raises a general point:
>
> There are a lot of people like me, coming into the Scala arena from a
> java programming background and quite probably no exposure to
> functional programming at all or any related mathematical concepts. We
> don't know our monads from our monoids.
>

Interestingly, it is perfectly possible (and easy) to represent the
monoid interface in Java's type system, but absolutely impossible to
represent the monad interface,

> So what do we do about it?

Party! Oh wait.

>
> We can just use scala as a better java (or whatever). Master the
> basics of maps, filters passing functions around and use of immutable
> data structures. Our programming and our programs will benefit and
> we'll confident in the new medium and happily productive.

If you were to truly master this, you've arrived at your destination.
There is no disconnection between, say, "mastering immutable data
structures" and the generalisations you might find in Scalaz.

>
> But sometimes you come on something where you just can't get things to
> work. You're pretty sure you ought to be able to do it - you can
> always drop in some form of type cast or whatever and carry on and
> you're still doing better than you would in java. Or you can start
> trying to figure out what it's all about.

You and I both know that you're just planting a bomb and it will explode
in your face when you're not looking.

The cast operation is (trivially) provably inconsistent under
intuitionistic logic. If you build a proof on a lie, you still have a
lie, even though almost all of the proof is perfectly solid.

>
> For me this happened when I started trying to do a DSL, for others it
> may be when they want to remove code smell of code duplication or
> think "there must be a better way".
>
> So what do you do?
>
> Asking on this list is one thing. And there's no shortage of "helpful"
> responses. But if the people responding are experts already totally
> fluent in the domain, and they are giving of their time for no
> personal benefit, then it's unreasonable to expect them not to respond
> in the vocabulary appropriate to the domain. So when Tony says
> something like " For-comprehensions denote monadic computation, while
> applicative functors are more general. Let's be clear on that: The
> applicative functor interface provides a strict subset of the derived
> operations of the monad interface"
> he is probably making a perfectly reasonable statement that we might
> just find utterly incomprehensible.

We can pull it apart! Sure it might be overwhelming at first. Go as far
as you can, then stop and ask. I hope you'll at least agree that when
these "incomprehensible" statements are made, it is you who is
over-estimating the difficulty of them. Once you comprehend it, you
think, "boy wasn't I making a big deal out of that?" -- right?

>
> So what are we going to do about?
>
> There is a fundamental problem here, none of the available books
> really explain this stuff on the scala platform to people who don't
> know it already. They'll talk in java-ish friendly terms for most of
> it, then maybe drop a little bit in (p 496 in Odersky mentions monads
> but it's hardly a proper definition, monoids and applicative functors
> don't get a look in). If you're very keen, very smart and very
> persistent you can probably work it all out for yourself, in here, in
> scala. Maybe the promised book I've seen referenced will help. But I'd
> be very surprised if many of the people who "get" scalaz didn't have
> an alternative route to this knowledge.
>
> So I think we do have a couple of options: stay as a general, better-
> than-java user, or cast around for ways to master some of this arcana.
> Personally, I'm learning Haskell (or what might be considered by some
> an act of child cruelty, i'm actually learning it with my 14-year
> son). I'm not just dipping in, as Tony suggests is possible - because
> I think he's underestimating the difficulties for people like me of
> making the paradigm shift.

To be clear, I certainly do not recommend "dipping in" to Haskell, but
to learn concepts thoroughly -- these concepts are independent of any
language. This recommendation often attracts hellfire accompanied with
poor advice which potentially misleads observers -- it's a fine line.

Haskell is a great learning tool because when you make a mistake, you
can argue with a machine (e.g. the type-checker) instead of getting
personal (arguing with me). It takes a lot of the burden away from me
and stops it from getting personal :) Although, in practice, it doesn't
completely stop it.

If you only intend to learn a concept, and "syntax" is a barrier, then
this is easily overcome. Only then do I recommend "dipping in" -- when
the short-term objective is ulterior to the overall one.

I'm learning it properly. And I'm flagging
> up the apparently gnomic utterances of people like Tony and occasional
> code fragments (the thread on "occult" scala was excellent in this
> respect) so that when I'm happier with the medium I can go back to see
> if it's all sunk in.

It's best to "iterate" on this. Constantly revisit it. Ask questions as
you go.

>
> I guess another option is to go on a course (SkillsMatter in the UK do
> some advanced ones) but that's way out of my budget.

If you're on the eastern seaboard of Australia at the end of the year,
let me know.
http://www.yowconference.com.au/YOW2011/general/workshopDetails.html?eve...

>
> If anyone has alternative suggestions for making the transition from
> java programmer to someone who gets scalaz it might be useful to share
> them. I know this crops up periodically- usually in response for "best
> book" suggestions but it might be worth focussing particularly on
> learning the hard stuff.

Focus not on Scalaz, not on the popularity contests of open source
projects, not on the bitter princesses coming to terms with various
anxieties, but nail down and learn. Lots of people are around to pick
you up when you fall and many people have trodden down *the exact same*
path that you intend to and they all cringe in empathy each time you
might stumble, mostly because there is nothing they can do but watch and
hope.

You are not alone.

>
>
> Tim

If asking questions is the key, how about we set up a few pages for this on our confluence wiki?

Even a simple FAQ for the core concepts (functor, pointed, applicative, monad, monoid) would offer a massive leap in availability for some of this information.

One of the biggest hurdles, currently, is learning the ideas from e.g "learn you a haskell", but not being able to figure out how scalaz encodes the same concepts. It would be an understatement to say that the source is spectacularly unhelpful here.

On Sep 10, 2011 11:45 AM, "Tony Morris" <tonymorris@gmail.com> wrote:
>
> -----BEGIN PGP SIGNED MESSAGE-----
> Hash: SHA1
>
> On 09/10/2011 08:26 PM, Tim P wrote:
> > The recent spat following Tony Morris's addendum to the scalaz video
> > raises a general point:
> >
> > There are a lot of people like me, coming into the Scala arena from a
> > java programming background and quite probably no exposure to
> > functional programming at all or any related mathematical concepts. We
> > don't know our monads from our monoids.
> >
>
> Interestingly, it is perfectly possible (and easy) to represent the
> monoid interface in Java's type system, but absolutely impossible to
> represent the monad interface,
>
> > So what do we do about it?
>
> Party! Oh wait.
>
> >
> > We can just use scala as a better java (or whatever). Master the
> > basics of maps, filters passing functions around and use of immutable
> > data structures. Our programming and our programs will benefit and
> > we'll confident in the new medium and happily productive.
>
> If you were to truly master this, you've arrived at your destination.
> There is no disconnection between, say, "mastering immutable data
> structures" and the generalisations you might find in Scalaz.
>
> >
> > But sometimes you come on something where you just can't get things to
> > work. You're pretty sure you ought to be able to do it - you can
> > always drop in some form of type cast or whatever and carry on and
> > you're still doing better than you would in java. Or you can start
> > trying to figure out what it's all about.
>
> You and I both know that you're just planting a bomb and it will explode
> in your face when you're not looking.
>
> The cast operation is (trivially) provably inconsistent under
> intuitionistic logic. If you build a proof on a lie, you still have a
> lie, even though almost all of the proof is perfectly solid.
>
> >
> > For me this happened when I started trying to do a DSL, for others it
> > may be when they want to remove code smell of code duplication or
> > think "there must be a better way".
> >
> > So what do you do?
> >
> > Asking on this list is one thing. And there's no shortage of "helpful"
> > responses. But if the people responding are experts already totally
> > fluent in the domain, and they are giving of their time for no
> > personal benefit, then it's unreasonable to expect them not to respond
> > in the vocabulary appropriate to the domain. So when Tony says
> > something like " For-comprehensions denote monadic computation, while
> > applicative functors are more general. Let's be clear on that: The
> > applicative functor interface provides a strict subset of the derived
> > operations of the monad interface"
> > he is probably making a perfectly reasonable statement that we might
> > just find utterly incomprehensible.
>
> We can pull it apart! Sure it might be overwhelming at first. Go as far
> as you can, then stop and ask. I hope you'll at least agree that when
> these "incomprehensible" statements are made, it is you who is
> over-estimating the difficulty of them. Once you comprehend it, you
> think, "boy wasn't I making a big deal out of that?" -- right?
>
> >
> > So what are we going to do about?
> >
> > There is a fundamental problem here, none of the available books
> > really explain this stuff on the scala platform to people who don't
> > know it already. They'll talk in java-ish friendly terms for most of
> > it, then maybe drop a little bit in (p 496 in Odersky mentions monads
> > but it's hardly a proper definition, monoids and applicative functors
> > don't get a look in). If you're very keen, very smart and very
> > persistent you can probably work it all out for yourself, in here, in
> > scala. Maybe the promised book I've seen referenced will help. But I'd
> > be very surprised if many of the people who "get" scalaz didn't have
> > an alternative route to this knowledge.
> >
> > So I think we do have a couple of options: stay as a general, better-
> > than-java user, or cast around for ways to master some of this arcana.
> > Personally, I'm learning Haskell (or what might be considered by some
> > an act of child cruelty, i'm actually learning it with my 14-year
> > son). I'm not just dipping in, as Tony suggests is possible  - because
> > I think he's underestimating the difficulties for people like me of
> > making the paradigm shift.
>
> To be clear, I certainly do not recommend "dipping in" to Haskell, but
> to learn concepts thoroughly -- these concepts are independent of any
> language. This recommendation often attracts hellfire accompanied with
> poor advice which potentially misleads observers -- it's a fine line.
>
> Haskell is a great learning tool because when you make a mistake, you
> can argue with a machine (e.g. the type-checker) instead of getting
> personal (arguing with me). It takes a lot of the burden away from me
> and stops it from getting personal :) Although, in practice, it doesn't
> completely stop it.
>
> If you only intend to learn a concept, and "syntax" is a barrier, then
> this is easily overcome. Only then do I recommend "dipping in" -- when
> the short-term objective is ulterior to the overall one.
>
> I'm learning it properly. And I'm flagging
> > up the apparently gnomic utterances of people like Tony and occasional
> > code fragments (the thread on "occult" scala was excellent in this
> > respect) so that when I'm happier with the medium I can go back to see
> > if it's all sunk in.
>
> It's best to "iterate" on this. Constantly revisit it. Ask questions as
> you go.
>
> >
> > I guess another option is to go on a course (SkillsMatter in the UK do
> > some advanced ones) but that's way out of my budget.
>
> If you're on the eastern seaboard of Australia at the end of the year,
> let me know.
> http://www.yowconference.com.au/YOW2011/general/workshopDetails.html?eventId=3552
>
> >
> > If anyone has alternative suggestions for making the transition from
> > java programmer to someone who gets scalaz it might be useful to share
> > them. I know this crops up periodically- usually in response for "best
> > book" suggestions but it might be worth focussing particularly on
> > learning the hard stuff.
>
> Focus not on Scalaz, not on the popularity contests of open source
> projects, not on the bitter princesses coming to terms with various
> anxieties, but nail down and learn. Lots of people are around to pick
> you up when you fall and many people have trodden down *the exact same*
> path that you intend to and they all cringe in empathy each time you
> might stumble, mostly because there is nothing they can do but watch and
> hope.
>
> You are not alone.
>
> >
> >
> > Tim
>
>
> - --
> Tony Morris
> http://tmorris.net/
>
> -----BEGIN PGP SIGNATURE-----
> Version: GnuPG v1.4.11 (GNU/Linux)
> Comment: Using GnuPG with Mozilla - http://enigmail.mozdev.org/
>
> iQEcBAEBAgAGBQJOaz/XAAoJEPxHMY3rBz0PSqQIAIfgNzJNc7pgAucU9y5oiIoD
> PZzZgmcQQH4b/JXw+lmOc1w/FWmTOdLZ2i0b7mT2v4LbBUBaKBSbqPY49aOyc6oK
> eGs7r2h2DUZ+yc2hEweNm48EMu52bPRHeb/vhEwpwIz+RrosLrWV8/Pq+9iiBmsE
> cY6MHzW2sa6NxuReeWEn8g+f26kanjgPaYkkMJm7vcDQf6b/eG/pcP84CChAleC8
> 7jKIBBGvpohiNUxiJWDrXeUJkoEZu1WUIcLpUP47jWcel9zjzl8KuhNWdb+cHDEy
> l8+VLBhI7RtwPZ0F2dJQWjwyxOy/XlZERZa2fBD0bTKZgFXNjZfrM+TKxZHHRkA=
> =obq0
> -----END PGP SIGNATURE-----

So far as I can tell, there's very little happening around Bangalore, India, when it comes to fp. There is a JUG which touches on Scala occasionaly, but that's not quite the same thing.

"In general I'd recommend participating in the London Scala User Group
and any other Scala or FP related groups that you can get to ... you'd
be amazed how much easier monads and monoids are to grasp after a beer
or two ;-)"

On Sat, Sep 10, 2011 at 12:44 PM, William la Forge wrote:
> So far as I can tell, there's very little happening around Bangalore, India,
> when it comes to fp. There is a JUG which touches on Scala occasionaly, but
> that's not quite the same thing.

There appears to be a FP group,

https://groups.google.com/groups/bangalore-fp

And according to this,

http://scala.meetup.com/

there appears to be interest in getting a Scala-specific group up and
running in Bangalore,

I'm sure there are readers of this list who would know more ...

Cheers,

Miles

Thanks! I joined bangalore-fp. The correct link is http://groups.google.com/group/bangalore-fp --b

On Sat, Sep 10, 2011 at 5:55 PM, Miles Sabin <miles@milessabin.com> wrote:

On Sat, Sep 10, 2011 at 12:44 PM, William la Forge <laforge49@gmail.com> wrote:
> So far as I can tell, there's very little happening around Bangalore, India,
> when it comes to fp. There is a JUG which touches on Scala occasionaly, but
> that's not quite the same thing.

There appears to be a FP group,

 https://groups.google.com/groups/bangalore-fp

And according to this,

 http://scala.meetup.com/

there appears to be interest in getting a Scala-specific group up and
running in Bangalore,

I'm sure there are readers of this list who would know more ...

Cheers,


Miles

--
Miles Sabin
tel: +44 7813 944 528
gtalk: miles@milessabin.com
skype: milessabin
http://www.chuusai.com/
http://twitter.com/milessabin

That would be great, if there are people who are willing and able to do this. In one of the spirited conversations I was in awhile ago in this group on the same topic (learning scalaz), I and a few others took the view that asking people to learn a language most don't want to learn or don't have time to learn (Haskell) in order to learn the scalaz concepts, and then having to transfer those concepts to Scala, simply raises the bar too high for many individuals who would otherwise learn scalaz. Hopefully the scalaz book will change this. In the interim, a good, Scala-based general intro would be a real help.
Ken

I think the more important question is, do you know your monads from
your gonads?

(Sorry, but the question was just begging to be asked.)

You might be on to something there... Gonads, containing gametes, can be said to contain the partial "state" of the individual. Perhaps a gonad is a species of state monad... The internal state of two gonads are combinable to form the state of a new individual, containing its own gonads. Perhaps that indicates some deeper monadic nature to genetic recombining...

--
Brian Maso
@bmaso on Twitter
brian@blumenfeld-maso.com

On Sat, Sep 10, 2011 at 11:29 PM, Russ P. <russ.paielli@gmail.com> wrote:

I think the more important question is, do you know your monads from
your gonads?

(Sorry, but the question was just begging to be asked.)

On Sun, 2011-09-11 at 11:34 -0700, Brian Maso wrote:
> You might be on to something there... Gonads, containing gametes, can
> be said to contain the partial "state" of the individual. Perhaps a
> gonad is a species of state monad... The internal state of two gonads
> are combinable to form the state of a new individual, containing its
> own gonads. Perhaps that indicates some deeper monadic nature to
> genetic recombining...
>
On the other hand, some people need to get out more ;-)

On Sat, Sep 10, 2011 at 12:26 PM, Tim P <tim.pigden@optrak.com> wrote:

If anyone has alternative suggestions for making the transition from
java programmer to someone who gets scalaz it might be useful to share
them. I know this crops up periodically- usually in response for "best
book" suggestions but it might be worth focussing particularly on
learning the hard stuff.

My current approach is to start from nLab ( http://ncatlab.org/nlab/show/HomePage ) and basically derive Scalaz (or something very similar) directly from the source.

To make sure I'm not just transliterating definitions I don't understand I also try to explain the concept I'm working on in a blog (not publishied yet).

To make things easy for me I started with the algebraic definition of a Monoid (a concept I find is easy to 'get' based on previous experiences), and now I have moved on to the category theoretic concept of Monoid. I must say that it was a surprisingly abstract concept once entering the world of categories.

To understnad Monoids in terms of CT you need to understand categories (which I think I'm starting to get as a simple generalisation of algebraic monoids to a "less closed" construction) and functors.

Functors seems reachable to me now, I think I have an intuitive hand wavy understanding of what it means for two categories to be related by a functor but it haven't clicked into an understanding of the full impact of the relationship.

Btw, here's my definitions of Category and Functor, I think it differs somewhat from Scalaz

trait Category {
  type ⊤
  type →[_ <: ⊤, _ <: ⊤]
  def id[A <: ⊤]: A → A
  def compose[A <: ⊤, B <: ⊤, C <: ⊤]: (A → B, B → C) ⇒ A → C
}
abstract class Functor(val c: Category, val d: Category) {
  import c.→, d.{ → ⇒ ↠ }
  type F[_] <: d.⊤
  def fmap[A <: c.⊤, B <: c.⊤]: (A → B) ⇒ F[A] ↠ F[B]
}

Now I just have to grok natural transformations and monoidal categories and I have Monoids nailed ;-)

Next step: Monads !

BR,
John

Dear John, et al,
This is a wonderful thread! i'm heartened to see people looking in this direction! Monadic Design Patterns for the Web will provide some of these. You can see some of the material in my blog at biosimilarity.blogspot.com. For example, the relationship between monoid and monad is actually very multifaceted. It's not just that the monad is the categorification of monoid (a kind of parameterized version of monoid), but also that monoid is an algebra and every algebra has a monadic presentation. The monadic characterization of universal algebra (covering monoids, groups, rings, fields, vector spaces, ...) is particularly useful for understanding what constitutes a specification of a domain specific language. It also goes the other way, for example, once you understand how a monad is the categorification of a monoid you can ask about the categorification of other algebras (aka data structures). For example, Hopf-like structures categorify the notion of group. These are particularly interesting because they support a natural semantics for transactions -- every action has a corresponding undo -- but in the categorical setting we have polymorphic interpretations of that undo.
Of course, it doesn't stop there! What is most vitally important to understand is the composition of monads and other categorified data structures to which we associate computational interpretations. Monad transformers are only one approach. Personally, i like the distributive law approach identified by Eugenia Cheng. A distributive law is a natural transformation between the type constructors of a pair of monads, satisfying certain conditions. When we work with versions of distributive laws supporting a certain hexagonal condition we automatically get nice properties of compositions of monads. The primary reason i like this way of organizing is that it smoothly extends to pairing monads with comonads and other similar situations.
What a more enlightened user of scalaz could tell me is what support is provided for the understanding, characterization and reasoning about the different levels of structure preservation. Specifically, each level of categorical composition (0-cells, 1-cells, 2-cells, ...) comes with a notion of what structure is preserved. At the level of categories, we have the notion of functoriality. This can be expressed as requirements on fmap (abusing notation only slightly)

• fmap( f o g ) = fmap( f ) o fmap( g )
• fmap( id[A] ) = id[fmap( A )]

At the levels of maps between functors, i.e. natural transformations (morphisms in 2-Categories) we have

• T( f ) o a = a o S( f )

And then when we have multiple maps as part of our API -- such as with monads where we have two natural transforms (the unit and the mult) -- we have coherence -- making sure all the pieces work well together. In the case of a monad, these correspond to the "monad laws". This is really just a special case of a general set of requirements that a given functional API is well behaved at each required level of structure and structure preservation. Having a working knowledge of the different levels of structure and structure preservation and how they ought to play together nicely and under what conditions they will auto-magically unburdens the programmer from stress and worry! ("Aha! i know i'm guaranteed this will work because this category supports limits and colimits!")
Best wishes,
--greg

On Sun, Sep 11, 2011 at 1:46 PM, John Nilsson <john@milsson.nu> wrote:

On Sat, Sep 10, 2011 at 12:26 PM, Tim P <tim.pigden@optrak.com> wrote:

If anyone has alternative suggestions for making the transition from
java programmer to someone who gets scalaz it might be useful to share
them. I know this crops up periodically- usually in response for "best
book" suggestions but it might be worth focussing particularly on
learning the hard stuff.

My current approach is to start from nLab ( http://ncatlab.org/nlab/show/HomePage ) and basically derive Scalaz (or something very similar) directly from the source.

To make sure I'm not just transliterating definitions I don't understand I also try to explain the concept I'm working on in a blog (not publishied yet).

To make things easy for me I started with the algebraic definition of a Monoid (a concept I find is easy to 'get' based on previous experiences), and now I have moved on to the category theoretic concept of Monoid. I must say that it was a surprisingly abstract concept once entering the world of categories.

To understnad Monoids in terms of CT you need to understand categories (which I think I'm starting to get as a simple generalisation of algebraic monoids to a "less closed" construction) and functors.

Functors seems reachable to me now, I think I have an intuitive hand wavy understanding of what it means for two categories to be related by a functor but it haven't clicked into an understanding of the full impact of the relationship.

Btw, here's my definitions of Category and Functor, I think it differs somewhat from Scalaz

trait Category {
  type ⊤
  type →[_ <: ⊤, _ <: ⊤]
  def id[A <: ⊤]: A → A
  def compose[A <: ⊤, B <: ⊤, C <: ⊤]: (A → B, B → C) ⇒ A → C
}
abstract class Functor(val c: Category, val d: Category) {
  import c.→, d.{ → ⇒ ↠ }
  type F[_] <: d.⊤
  def fmap[A <: c.⊤, B <: c.⊤]: (A → B) ⇒ F[A] ↠ F[B]
}

Now I just have to grok natural transformations and monoidal categories and I have Monoids nailed ;-)

Next step: Monads !

BR,
John

--
L.G. Meredith
Managing Partner
Biosimilarity LLC
7329 39th Ave SWSeattle, WA 98136

+1 206.650.3740

http://biosimilarity.blogspot.com

Greg I think you just summarised the topics of several books into a hand full of sentences. I hope I will reach a level of understanding to be able to read what you just wrote. =D

B.t.w. I love the videos you've made for channel nine. They have been very helpful to help me understand these topics. I think you and Brian should compose an entire series of this stuff!

One topic that would be helpful for me is that of naturality. In one of the monadic design pattern lectures you mention important naturalities but kind of skimmed the topic, and I haven't found a good text about it online.

I've also seen somewhere (was it you?)  a statement of the effect that in the study of categories has moved on from functors to natural transformations as a more interesting view of things to study?

BR,
John

On Mon, Sep 12, 2011 at 12:17 AM, Meredith Gregory <lgreg.meredith@gmail.com> wrote:

Dear John, et al,
This is a wonderful thread! i'm heartened to see people looking in this direction! Monadic Design Patterns for the Web will provide some of these. You can see some of the material in my blog at biosimilarity.blogspot.com. For example, the relationship between monoid and monad is actually very multifaceted. It's not just that the monad is the categorification of monoid (a kind of parameterized version of monoid), but also that monoid is an algebra and every algebra has a monadic presentation. The monadic characterization of universal algebra (covering monoids, groups, rings, fields, vector spaces, ...) is particularly useful for understanding what constitutes a specification of a domain specific language. It also goes the other way, for example, once you understand how a monad is the categorification of a monoid you can ask about the categorification of other algebras (aka data structures). For example, Hopf-like structures categorify the notion of group. These are particularly interesting because they support a natural semantics for transactions -- every action has a corresponding undo -- but in the categorical setting we have polymorphic interpretations of that undo.
Of course, it doesn't stop there! What is most vitally important to understand is the composition of monads and other categorified data structures to which we associate computational interpretations. Monad transformers are only one approach. Personally, i like the distributive law approach identified by Eugenia Cheng. A distributive law is a natural transformation between the type constructors of a pair of monads, satisfying certain conditions. When we work with versions of distributive laws supporting a certain hexagonal condition we automatically get nice properties of compositions of monads. The primary reason i like this way of organizing is that it smoothly extends to pairing monads with comonads and other similar situations.
What a more enlightened user of scalaz could tell me is what support is provided for the understanding, characterization and reasoning about the different levels of structure preservation. Specifically, each level of categorical composition (0-cells, 1-cells, 2-cells, ...) comes with a notion of what structure is preserved. At the level of categories, we have the notion of functoriality. This can be expressed as requirements on fmap (abusing notation only slightly)

• fmap( f o g ) = fmap( f ) o fmap( g )
• fmap( id[A] ) = id[fmap( A )]

At the levels of maps between functors, i.e. natural transformations (morphisms in 2-Categories) we have

• T( f ) o a = a o S( f )

And then when we have multiple maps as part of our API -- such as with monads where we have two natural transforms (the unit and the mult) -- we have coherence -- making sure all the pieces work well together. In the case of a monad, these correspond to the "monad laws". This is really just a special case of a general set of requirements that a given functional API is well behaved at each required level of structure and structure preservation. Having a working knowledge of the different levels of structure and structure preservation and how they ought to play together nicely and under what conditions they will auto-magically unburdens the programmer from stress and worry! ("Aha! i know i'm guaranteed this will work because this category supports limits and colimits!")
Best wishes,
--greg

On Sun, Sep 11, 2011 at 1:46 PM, John Nilsson <john@milsson.nu> wrote:

On Sat, Sep 10, 2011 at 12:26 PM, Tim P <tim.pigden@optrak.com> wrote:

If anyone has alternative suggestions for making the transition from
java programmer to someone who gets scalaz it might be useful to share
them. I know this crops up periodically- usually in response for "best
book" suggestions but it might be worth focussing particularly on
learning the hard stuff.

My current approach is to start from nLab ( http://ncatlab.org/nlab/show/HomePage ) and basically derive Scalaz (or something very similar) directly from the source.

To make sure I'm not just transliterating definitions I don't understand I also try to explain the concept I'm working on in a blog (not publishied yet).

To make things easy for me I started with the algebraic definition of a Monoid (a concept I find is easy to 'get' based on previous experiences), and now I have moved on to the category theoretic concept of Monoid. I must say that it was a surprisingly abstract concept once entering the world of categories.

To understnad Monoids in terms of CT you need to understand categories (which I think I'm starting to get as a simple generalisation of algebraic monoids to a "less closed" construction) and functors.

Functors seems reachable to me now, I think I have an intuitive hand wavy understanding of what it means for two categories to be related by a functor but it haven't clicked into an understanding of the full impact of the relationship.

Btw, here's my definitions of Category and Functor, I think it differs somewhat from Scalaz

trait Category {
  type ⊤
  type →[_ <: ⊤, _ <: ⊤]
  def id[A <: ⊤]: A → A
  def compose[A <: ⊤, B <: ⊤, C <: ⊤]: (A → B, B → C) ⇒ A → C
}
abstract class Functor(val c: Category, val d: Category) {
  import c.→, d.{ → ⇒ ↠ }
  type F[_] <: d.⊤
  def fmap[A <: c.⊤, B <: c.⊤]: (A → B) ⇒ F[A] ↠ F[B]
}

Now I just have to grok natural transformations and monoidal categories and I have Monoids nailed ;-)

Next step: Monads !

BR,
John

--
L.G. Meredith
Managing Partner
Biosimilarity LLC
7329 39th Ave SWSeattle, WA 98136

+1 206.650.3740

http://biosimilarity.blogspot.com

This is a wonderful thread! i'm heartened to see people looking in this direction! Monadic Design Patterns for the Web will provide some of these. You can see some of the material in my blog at biosimilarity.blogspot.com. For example, the relationship between monoid and monad is actually very multifaceted. It's not just that the monad is the categorification of monoid (a kind of parameterized version of monoid), but also that monoid is an algebra and every algebra has a monadic presentation. The monadic characterization of universal algebra (covering monoids, groups, rings, fields, vector spaces, ...) is particularly useful for understanding what constitutes a specification of a domain specific language. It also goes the other way, for example, once you understand how a monad is the categorification of a monoid you can ask about the categorification of other algebras (aka data structures). For example, Hopf-like structures categorify the notion of group. These are particularly interesting because they support a natural semantics for transactions -- every action has a corresponding undo -- but in the categorical setting we have polymorphic interpretations of that undo.
...

I just wanted to chime in with a bit on FP theory, and what it will take for it to become widely used in the Scala community, vs. being relegated to an unimportant niche (just as Haskell was relegated to an unimportant niche in the production programming community because, IMHO, the academic world simply didn't understand real-world needs. For the record, I was a grad student in FP at the time Haskell was in its early years.)
I'm not picking on this thread because the people are saying anything wrong, simply because its fairly jargon-heavy, which is what I think the proponents of FP theory need to guard against.
Let me start off by saying I used to love Math for Math's sake; as an undergrad I filled my electives not with history, but with vector calculus, real and complex analysis, matrix algebra, differential equations, and topology. And got, for the most part, top marks. So I understand the love of the concepts and the enthusiasm for digging ever deeper.
However, I've been a tech writer for many years now, most often documenting complex technical systems (mostly APIs and general system design) for developers. I've done it very well. And my experience is that while formal definitions are sometimes needed, it's really applicable examples that will make a developer _want_ to learn an API, as opposed to just needing to learn it. In the case of scalaz and related packages, I think this is even more important, since learning them isn't mandatory.
My real worry is that since so many developers and users of scalaz are very enthusiastic about the conceptual background, they will assume other people will become similarly interested, and will write documentation for scalaz that explains it in an academic, mathematical way, rather than in a practical, "look at what it can do for you" way. However, the large number of programmers out there are not interested in learning pure math--CS is an applied discipline. If readers of scalaz documentation don't get to concrete, useful examples pretty quickly, they will probably go to look at one of the many other interesting tools becoming available in the Scala world.
So I'm just putting this out there in hopes that it will get some scalaz/FP theory enthusiasts about the way they might attract a larger audience.

Cheers,Ken

On Sun, Sep 11, 2011 at 10:46 PM, John Nilsson <john@milsson.nu> wrote:

Btw, here's my definitions of Category and Functor, I think it differs somewhat from Scalaz

trait Category {
  type ⊤
  type →[_ <: ⊤, _ <: ⊤]
  def id[A <: ⊤]: A → A
  def compose[A <: ⊤, B <: ⊤, C <: ⊤]: (A → B, B → C) ⇒ A → C
}
abstract class Functor(val c: Category, val d: Category) {
  import c.→, d.{ → ⇒ ↠ }
  type F[_] <: d.⊤
  def fmap[A <: c.⊤, B <: c.⊤]: (A → B) ⇒ F[A] ↠ F[B]
}

Just thought I'd mention this. One important AHA moment for me was the realisation of how general this definition is. Both in the flexibility of the Scala type-system, but also how the arrowness of categories doesn't really imply that much pointingness.

Defining this category was the trigger:
class Monoid[T](id: T, op: (T, T) ⇒ T) extends Category {
  type →[A, B] = T
  def id[A] = id
  def compose[A, B, C] = op
}

and here's an example

  object IntAddition extends Monoid[Int](0,_+_)

Not that this is the algebraic definition of monoids, the category one is far more generic.

BR,

John

Dear John,
Thanks for the feedback about the videos! In answer to your questions about a reference for natural transformations: the wikipedia article about natural transformations is adequate. You could do far worse than read Barr & Wells, Category Theory for the Working Computer Scientist. Regarding a shift in emphasis, i think the main shift in emphasis has to do with N-categories. If you want to understand the current thinking on N-categories, you might take a look at Tom Leinster's PhD thesis. 
The principle idea is that morphism is a relative idea, 0-cells are objects, 1-cells are morphisms between 0-cells, 2-cells are morphisms between 1-cells, 3-cells are morphisms between 2-cells, etc. In an ordinary category, 1-cells would be the morphisms (structure preserving maps between objects, like functions between sets or homomorphisms between groups or homeomorphisms between topological spaces). In the category Cat, of small categories, 1-cells are functors, and then 2-cells would be natural transformations, etc. One of the tricky bits is that as n gets larger there are more and more ways to compose. To see the different ways to compose the 2-cells take a look at the Godement calculus (you can find a decent presentation in Barr & Wells). There are other desiderata, like the fact that each level is just an algebraic theory and so you want it to fall out as an algebra of a monad.
Personally, my own sense is that the clear lack of a single compelling definition of N-category is a critique of the current presentation of category theory. In my experience i have grown to evaluate theories in terms of whether they can support being their own meta-theories. When a theory has this property the N-generalization is natural and compelling. In discussion with John Baez, he has expressed a counterpoint to my intuition, suggesting that Leinster's presentation is compelling enough. You would have to judge for yourself!
i suspect that it is possible to redo category theory from the ground up using monads as the core building block. The evidence i have for this point of view is that monads are effectively generalized comprehensions (see Wadler's comprehending monads as support for this view). Since we know that we can bootstrap category theory from set theory (then build topos theory on top of category theory -- replacing the notion of set -- and kick away the scaffolding, just like building gcc from the native c compiler then recompiling it with itself), and comprehensions are what make set theory tick, from an operational perspective (i.e., in set theory you do all your coding with comprehensions), a generalized, polymorphic notion of comprehension should more than suffice. 
More than you asked for, i'm sure, but not without some interest, i hope.
Best wishes,
--greg

On Sun, Sep 11, 2011 at 3:40 PM, John Nilsson <john@milsson.nu> wrote:

Greg I think you just summarised the topics of several books into a hand full of sentences. I hope I will reach a level of understanding to be able to read what you just wrote. =D

B.t.w. I love the videos you've made for channel nine. They have been very helpful to help me understand these topics. I think you and Brian should compose an entire series of this stuff!

One topic that would be helpful for me is that of naturality. In one of the monadic design pattern lectures you mention important naturalities but kind of skimmed the topic, and I haven't found a good text about it online.

I've also seen somewhere (was it you?)  a statement of the effect that in the study of categories has moved on from functors to natural transformations as a more interesting view of things to study?

BR,
John

On Mon, Sep 12, 2011 at 12:17 AM, Meredith Gregory <lgreg.meredith@gmail.com> wrote:

Dear John, et al,
This is a wonderful thread! i'm heartened to see people looking in this direction! Monadic Design Patterns for the Web will provide some of these. You can see some of the material in my blog at biosimilarity.blogspot.com. For example, the relationship between monoid and monad is actually very multifaceted. It's not just that the monad is the categorification of monoid (a kind of parameterized version of monoid), but also that monoid is an algebra and every algebra has a monadic presentation. The monadic characterization of universal algebra (covering monoids, groups, rings, fields, vector spaces, ...) is particularly useful for understanding what constitutes a specification of a domain specific language. It also goes the other way, for example, once you understand how a monad is the categorification of a monoid you can ask about the categorification of other algebras (aka data structures). For example, Hopf-like structures categorify the notion of group. These are particularly interesting because they support a natural semantics for transactions -- every action has a corresponding undo -- but in the categorical setting we have polymorphic interpretations of that undo.
Of course, it doesn't stop there! What is most vitally important to understand is the composition of monads and other categorified data structures to which we associate computational interpretations. Monad transformers are only one approach. Personally, i like the distributive law approach identified by Eugenia Cheng. A distributive law is a natural transformation between the type constructors of a pair of monads, satisfying certain conditions. When we work with versions of distributive laws supporting a certain hexagonal condition we automatically get nice properties of compositions of monads. The primary reason i like this way of organizing is that it smoothly extends to pairing monads with comonads and other similar situations.
What a more enlightened user of scalaz could tell me is what support is provided for the understanding, characterization and reasoning about the different levels of structure preservation. Specifically, each level of categorical composition (0-cells, 1-cells, 2-cells, ...) comes with a notion of what structure is preserved. At the level of categories, we have the notion of functoriality. This can be expressed as requirements on fmap (abusing notation only slightly)

• fmap( f o g ) = fmap( f ) o fmap( g )
• fmap( id[A] ) = id[fmap( A )]

At the levels of maps between functors, i.e. natural transformations (morphisms in 2-Categories) we have

• T( f ) o a = a o S( f )

And then when we have multiple maps as part of our API -- such as with monads where we have two natural transforms (the unit and the mult) -- we have coherence -- making sure all the pieces work well together. In the case of a monad, these correspond to the "monad laws". This is really just a special case of a general set of requirements that a given functional API is well behaved at each required level of structure and structure preservation. Having a working knowledge of the different levels of structure and structure preservation and how they ought to play together nicely and under what conditions they will auto-magically unburdens the programmer from stress and worry! ("Aha! i know i'm guaranteed this will work because this category supports limits and colimits!")
Best wishes,
--greg

On Sun, Sep 11, 2011 at 1:46 PM, John Nilsson <john@milsson.nu> wrote:

On Sat, Sep 10, 2011 at 12:26 PM, Tim P <tim.pigden@optrak.com> wrote:

If anyone has alternative suggestions for making the transition from
java programmer to someone who gets scalaz it might be useful to share
them. I know this crops up periodically- usually in response for "best
book" suggestions but it might be worth focussing particularly on
learning the hard stuff.

My current approach is to start from nLab ( http://ncatlab.org/nlab/show/HomePage ) and basically derive Scalaz (or something very similar) directly from the source.

To make sure I'm not just transliterating definitions I don't understand I also try to explain the concept I'm working on in a blog (not publishied yet).

To make things easy for me I started with the algebraic definition of a Monoid (a concept I find is easy to 'get' based on previous experiences), and now I have moved on to the category theoretic concept of Monoid. I must say that it was a surprisingly abstract concept once entering the world of categories.

To understnad Monoids in terms of CT you need to understand categories (which I think I'm starting to get as a simple generalisation of algebraic monoids to a "less closed" construction) and functors.

Functors seems reachable to me now, I think I have an intuitive hand wavy understanding of what it means for two categories to be related by a functor but it haven't clicked into an understanding of the full impact of the relationship.

Btw, here's my definitions of Category and Functor, I think it differs somewhat from Scalaz

trait Category {
  type ⊤
  type →[_ <: ⊤, _ <: ⊤]
  def id[A <: ⊤]: A → A
  def compose[A <: ⊤, B <: ⊤, C <: ⊤]: (A → B, B → C) ⇒ A → C
}
abstract class Functor(val c: Category, val d: Category) {
  import c.→, d.{ → ⇒ ↠ }
  type F[_] <: d.⊤
  def fmap[A <: c.⊤, B <: c.⊤]: (A → B) ⇒ F[A] ↠ F[B]
}

Now I just have to grok natural transformations and monoidal categories and I have Monoids nailed ;-)

Next step: Monads !

BR,
John

--
L.G. Meredith
Managing Partner
Biosimilarity LLC
7329 39th Ave SWSeattle, WA 98136

+1 206.650.3740

http://biosimilarity.blogspot.com

--
L.G. Meredith
Managing Partner
Biosimilarity LLC
7329 39th Ave SWSeattle, WA 98136

+1 206.650.3740

http://biosimilarity.blogspot.com

P.S. Actually, the clear lack of a compelling definition of N-category that singles one out of the 5 or 6 proposals, taken together with the fact that Category Theory has yet to provide a compelling encoding of concurrent composition that supports both mobility and a Curry-Howard orientation (make processes be morphisms and not objects) leads me to believe that Category Theory needs some reworking as a codebase. 

On Sun, Sep 11, 2011 at 9:07 PM, Meredith Gregory <lgreg.meredith@gmail.com> wrote:

Dear John,
Thanks for the feedback about the videos! In answer to your questions about a reference for natural transformations: the wikipedia article about natural transformations is adequate. You could do far worse than read Barr & Wells, Category Theory for the Working Computer Scientist. Regarding a shift in emphasis, i think the main shift in emphasis has to do with N-categories. If you want to understand the current thinking on N-categories, you might take a look at Tom Leinster's PhD thesis. 
The principle idea is that morphism is a relative idea, 0-cells are objects, 1-cells are morphisms between 0-cells, 2-cells are morphisms between 1-cells, 3-cells are morphisms between 2-cells, etc. In an ordinary category, 1-cells would be the morphisms (structure preserving maps between objects, like functions between sets or homomorphisms between groups or homeomorphisms between topological spaces). In the category Cat, of small categories, 1-cells are functors, and then 2-cells would be natural transformations, etc. One of the tricky bits is that as n gets larger there are more and more ways to compose. To see the different ways to compose the 2-cells take a look at the Godement calculus (you can find a decent presentation in Barr & Wells). There are other desiderata, like the fact that each level is just an algebraic theory and so you want it to fall out as an algebra of a monad.
Personally, my own sense is that the clear lack of a single compelling definition of N-category is a critique of the current presentation of category theory. In my experience i have grown to evaluate theories in terms of whether they can support being their own meta-theories. When a theory has this property the N-generalization is natural and compelling. In discussion with John Baez, he has expressed a counterpoint to my intuition, suggesting that Leinster's presentation is compelling enough. You would have to judge for yourself!
i suspect that it is possible to redo category theory from the ground up using monads as the core building block. The evidence i have for this point of view is that monads are effectively generalized comprehensions (see Wadler's comprehending monads as support for this view). Since we know that we can bootstrap category theory from set theory (then build topos theory on top of category theory -- replacing the notion of set -- and kick away the scaffolding, just like building gcc from the native c compiler then recompiling it with itself), and comprehensions are what make set theory tick, from an operational perspective (i.e., in set theory you do all your coding with comprehensions), a generalized, polymorphic notion of comprehension should more than suffice. 
More than you asked for, i'm sure, but not without some interest, i hope.
Best wishes,
--greg

On Sun, Sep 11, 2011 at 3:40 PM, John Nilsson <john@milsson.nu> wrote:

Greg I think you just summarised the topics of several books into a hand full of sentences. I hope I will reach a level of understanding to be able to read what you just wrote. =D

B.t.w. I love the videos you've made for channel nine. They have been very helpful to help me understand these topics. I think you and Brian should compose an entire series of this stuff!

One topic that would be helpful for me is that of naturality. In one of the monadic design pattern lectures you mention important naturalities but kind of skimmed the topic, and I haven't found a good text about it online.

I've also seen somewhere (was it you?)  a statement of the effect that in the study of categories has moved on from functors to natural transformations as a more interesting view of things to study?

BR,
John

On Mon, Sep 12, 2011 at 12:17 AM, Meredith Gregory <lgreg.meredith@gmail.com> wrote:

Dear John, et al,
This is a wonderful thread! i'm heartened to see people looking in this direction! Monadic Design Patterns for the Web will provide some of these. You can see some of the material in my blog at biosimilarity.blogspot.com. For example, the relationship between monoid and monad is actually very multifaceted. It's not just that the monad is the categorification of monoid (a kind of parameterized version of monoid), but also that monoid is an algebra and every algebra has a monadic presentation. The monadic characterization of universal algebra (covering monoids, groups, rings, fields, vector spaces, ...) is particularly useful for understanding what constitutes a specification of a domain specific language. It also goes the other way, for example, once you understand how a monad is the categorification of a monoid you can ask about the categorification of other algebras (aka data structures). For example, Hopf-like structures categorify the notion of group. These are particularly interesting because they support a natural semantics for transactions -- every action has a corresponding undo -- but in the categorical setting we have polymorphic interpretations of that undo.
Of course, it doesn't stop there! What is most vitally important to understand is the composition of monads and other categorified data structures to which we associate computational interpretations. Monad transformers are only one approach. Personally, i like the distributive law approach identified by Eugenia Cheng. A distributive law is a natural transformation between the type constructors of a pair of monads, satisfying certain conditions. When we work with versions of distributive laws supporting a certain hexagonal condition we automatically get nice properties of compositions of monads. The primary reason i like this way of organizing is that it smoothly extends to pairing monads with comonads and other similar situations.
What a more enlightened user of scalaz could tell me is what support is provided for the understanding, characterization and reasoning about the different levels of structure preservation. Specifically, each level of categorical composition (0-cells, 1-cells, 2-cells, ...) comes with a notion of what structure is preserved. At the level of categories, we have the notion of functoriality. This can be expressed as requirements on fmap (abusing notation only slightly)

• fmap( f o g ) = fmap( f ) o fmap( g )
• fmap( id[A] ) = id[fmap( A )]

At the levels of maps between functors, i.e. natural transformations (morphisms in 2-Categories) we have

• T( f ) o a = a o S( f )

And then when we have multiple maps as part of our API -- such as with monads where we have two natural transforms (the unit and the mult) -- we have coherence -- making sure all the pieces work well together. In the case of a monad, these correspond to the "monad laws". This is really just a special case of a general set of requirements that a given functional API is well behaved at each required level of structure and structure preservation. Having a working knowledge of the different levels of structure and structure preservation and how they ought to play together nicely and under what conditions they will auto-magically unburdens the programmer from stress and worry! ("Aha! i know i'm guaranteed this will work because this category supports limits and colimits!")
Best wishes,
--greg

On Sun, Sep 11, 2011 at 1:46 PM, John Nilsson <john@milsson.nu> wrote:

On Sat, Sep 10, 2011 at 12:26 PM, Tim P <tim.pigden@optrak.com> wrote:

If anyone has alternative suggestions for making the transition from
java programmer to someone who gets scalaz it might be useful to share
them. I know this crops up periodically- usually in response for "best
book" suggestions but it might be worth focussing particularly on
learning the hard stuff.

My current approach is to start from nLab ( http://ncatlab.org/nlab/show/HomePage ) and basically derive Scalaz (or something very similar) directly from the source.

To make sure I'm not just transliterating definitions I don't understand I also try to explain the concept I'm working on in a blog (not publishied yet).

To make things easy for me I started with the algebraic definition of a Monoid (a concept I find is easy to 'get' based on previous experiences), and now I have moved on to the category theoretic concept of Monoid. I must say that it was a surprisingly abstract concept once entering the world of categories.

To understnad Monoids in terms of CT you need to understand categories (which I think I'm starting to get as a simple generalisation of algebraic monoids to a "less closed" construction) and functors.

Functors seems reachable to me now, I think I have an intuitive hand wavy understanding of what it means for two categories to be related by a functor but it haven't clicked into an understanding of the full impact of the relationship.

Btw, here's my definitions of Category and Functor, I think it differs somewhat from Scalaz

trait Category {
  type ⊤
  type →[_ <: ⊤, _ <: ⊤]
  def id[A <: ⊤]: A → A
  def compose[A <: ⊤, B <: ⊤, C <: ⊤]: (A → B, B → C) ⇒ A → C
}
abstract class Functor(val c: Category, val d: Category) {
  import c.→, d.{ → ⇒ ↠ }
  type F[_] <: d.⊤
  def fmap[A <: c.⊤, B <: c.⊤]: (A → B) ⇒ F[A] ↠ F[B]
}

Now I just have to grok natural transformations and monoidal categories and I have Monoids nailed ;-)

Next step: Monads !

BR,
John

--
L.G. Meredith
Managing Partner
Biosimilarity LLC
7329 39th Ave SWSeattle, WA 98136

+1 206.650.3740

http://biosimilarity.blogspot.com

--
L.G. Meredith
Managing Partner
Biosimilarity LLC
7329 39th Ave SWSeattle, WA 98136

+1 206.650.3740

http://biosimilarity.blogspot.com

--
L.G. Meredith
Managing Partner
Biosimilarity LLC
7329 39th Ave SWSeattle, WA 98136

+1 206.650.3740

http://biosimilarity.blogspot.com

On Sep 11, 3:48 pm, Ken McDonald wrote:
> And my experience is that while formal
> definitions are sometimes needed, it's really applicable examples that will
> make a developer _want_ to learn an API, as opposed to just needing to learn
> it.

That really resonates with me. For instance for me that gist (https://
gist.github.com/970717) from Chris is a lot easier to read than the
scalaz example (http://scalaz.github.com/scalaz/scalaz-2.9.1-6.0.2/
doc.sxr/scalaz/example/ExampleValidation.scala.html#25145) or reading
about applicative functors. I think different people learn
differently. For me, reading about the theory before I have used a
concept does not necessarily help me. In fact I tried that by reading
various sections of http://learnyouahaskell.com 8 months ago, already
forgot most of it and I don't think that helped me applied any
functional concepts since. So my path for learning applicative
functors would probably look more like:
1) use scalaz Validation for a while including various situations
where application functors are used
2) read about the theory/blogs/source code
3) hopefully light bulbs and being able to carry the experience in
step 1) to use application functors in other situations

The other thing that doesn't work for me is the "you could have
invented X" type of learning which sort of goes like this: present an
artificial use case where X is needed, then pretend in a few steps
that I could have come up with X and code it from the ground up
showing how the use case is easier, then somehow at the end of this
I'm supposed to grasp X.

With that in mind I really appreciate what Heiko and Chris are doing
to present scalaz from a practical perspective.

--Jean-Laurent

Dear Ken,
i wholeheartedly agree with you! One of the opportunities is to find ways of bridging amongst the communities of mathematicians (working in category theory), computer scientists, logicians and working programmers. Each of these communities has much to offer. Much of what comes about in practical programming can -- in my experience -- inform the mathematical discourse! i apologize that i didn't have the time or the skillful means to speak to both sides in the email below, using instead the mathematical language that comes more naturally to me. However, the blog posts i referenced attempt to speak directly to programmers.
At the end of the day there's a lot of talk about DSLs. Yet, no one seems to recognize what constitutes the specification of a (domain specific) language, or how that relates to existing specification technology. What is necessary are three things

• a grammar (which is an analog of the generators in a generators and relations presentation of universal algebra)
• a structural equivalence (which is the an analog of the relations in a generators and relations presentation)
• an operational semantics (which is a new thing, not found in universal algebra)

What the category theory community found back in the 60's was that the whole universal algebra story could be told neatly with monads. More recently Meijer and Hutton described a neat presentation of grammars in terms of monads, and there's a corresponding story for the structural equivalence (which is captured in the idea of an algebra of a monad, such as Kleisli or Eilenberg-Moore). It further turns out that rewrite systems (including nominal rewrite systems like we have in the lambda calculus) have tidy presentations in terms of monads. So, a DSL is presented cleanly and succinctly by giving an algebra of a monad ( G, g ) for the grammar and structural equivalence, together with the monad for the operational semantics.
This cleans up a lot of mess that is currently strewn about in codebases around the world. So, it is a very practical thing that would benefit a lot of programmers. It would also benefit a lot of mathematicians who are more or less in the business of designing DSLs. They intuitively understand what they are doing, but could benefit from all the advantages of automating their designs.
Best wishes,
--greg

On Sun, Sep 11, 2011 at 3:48 PM, Ken McDonald <ykkenmcd@gmail.com> wrote:

This is a wonderful thread! i'm heartened to see people looking in this direction! Monadic Design Patterns for the Web will provide some of these. You can see some of the material in my blog at biosimilarity.blogspot.com. For example, the relationship between monoid and monad is actually very multifaceted. It's not just that the monad is the categorification of monoid (a kind of parameterized version of monoid), but also that monoid is an algebra and every algebra has a monadic presentation. The monadic characterization of universal algebra (covering monoids, groups, rings, fields, vector spaces, ...) is particularly useful for understanding what constitutes a specification of a domain specific language. It also goes the other way, for example, once you understand how a monad is the categorification of a monoid you can ask about the categorification of other algebras (aka data structures). For example, Hopf-like structures categorify the notion of group. These are particularly interesting because they support a natural semantics for transactions -- every action has a corresponding undo -- but in the categorical setting we have polymorphic interpretations of that undo.
...

I just wanted to chime in with a bit on FP theory, and what it will take for it to become widely used in the Scala community, vs. being relegated to an unimportant niche (just as Haskell was relegated to an unimportant niche in the production programming community because, IMHO, the academic world simply didn't understand real-world needs. For the record, I was a grad student in FP at the time Haskell was in its early years.)
I'm not picking on this thread because the people are saying anything wrong, simply because its fairly jargon-heavy, which is what I think the proponents of FP theory need to guard against.
Let me start off by saying I used to love Math for Math's sake; as an undergrad I filled my electives not with history, but with vector calculus, real and complex analysis, matrix algebra, differential equations, and topology. And got, for the most part, top marks. So I understand the love of the concepts and the enthusiasm for digging ever deeper.
However, I've been a tech writer for many years now, most often documenting complex technical systems (mostly APIs and general system design) for developers. I've done it very well. And my experience is that while formal definitions are sometimes needed, it's really applicable examples that will make a developer _want_ to learn an API, as opposed to just needing to learn it. In the case of scalaz and related packages, I think this is even more important, since learning them isn't mandatory.
My real worry is that since so many developers and users of scalaz are very enthusiastic about the conceptual background, they will assume other people will become similarly interested, and will write documentation for scalaz that explains it in an academic, mathematical way, rather than in a practical, "look at what it can do for you" way. However, the large number of programmers out there are not interested in learning pure math--CS is an applied discipline. If readers of scalaz documentation don't get to concrete, useful examples pretty quickly, they will probably go to look at one of the many other interesting tools becoming available in the Scala world.
So I'm just putting this out there in hopes that it will get some scalaz/FP theory enthusiasts about the way they might attract a larger audience.

Cheers, Ken

--
L.G. Meredith
Managing Partner
Biosimilarity LLC
7329 39th Ave SWSeattle, WA 98136

+1 206.650.3740

http://biosimilarity.blogspot.com

On Mon, Sep 12, 2011 at 12:09 AM, Meredith Gregory <lgreg.meredith@gmail.com> wrote:

P.S. Actually, the clear lack of a compelling definition of N-category that singles one out of the 5 or 6 proposals, taken together with the fact that Category Theory has yet to provide a compelling encoding of concurrent composition that supports both mobility and a Curry-Howard orientation (make processes be morphisms and not objects) leads me to believe that Category Theory needs some reworking as a codebase. 

After reading your comments throughout this whole thread, I think if I ever talked you in person my head would explode... In a good way. 

couldn't agree more about the distributive law perspective on composing monads; there's a nice concise account in Leinster green book Higher Operads, Higher Categories p148, and in case anyone is interested Eugenia Cheng's paper is Iterated distributive laws. Street's wonderful observation (The formal theory of monads I) that distributive laws are monads in Mnd the 2-category of monads (so that you use monads to compose monads) is generalized here to the fact that a what Cheng calls a chain of distributive laws between n monads is the same as a monad in the 2-category Mnd^n (which is monads in the 2-category of monads in the 2-category of... n times). 
All of this provides strong theoretical support for the use of iterated distributive laws (distributive laws + YB-type coherence conditions) as a tool for composing several monads. 
--Eduardo Pareja-Tobeshttp://eduardo.pareja-tobes.name

On Mon, Sep 12, 2011 at 6:07 AM, Meredith Gregory <lgreg.meredith@gmail.com> wrote:

i suspect that it is possible to redo category theory from the ground up using monads as the core building block. The evidence i have for this point of view is that monads are effectively generalized comprehensions (see Wadler's comprehending monads as support for this view). Since we know that we can bootstrap category theory from set theory (then build topos theory on top of category theory -- replacing the notion of set -- and kick away the scaffolding, just like building gcc from the native c compiler then recompiling it with itself), and comprehensions are what make set theory tick, from an operational perspective (i.e., in set theory you do all your coding with comprehensions), a generalized, polymorphic notion of comprehension should more than suffice.

Hmm that sounds very interesting indeed. Do you have any sketches of how that might look?

What you just said resonated somewhat with a previous suspicion I've had while pondering on how relational theory might be improved and expanded to allow a the same declarative approach to general programming as SQL (somewhat) provides for data querying. Or in the other direction: how a query language supporting composable constructs might look. At the time I think I was reading that paper you linked to though, and I guess what my mind was telling me was that if I just understood monads well enough I could build a DBMS on monads instead of relations to achieve some of this.

In my thinking there is a problem with designing ever more powerful and abstract languages for encoding machine instructions when we are still missing adequately powerful and abstract languages for expressing formal requirements. Could it be that hidden in this wadler-paper and other generalised mathematics there is a workable foundation for working with the domain specific parts of our programs without mixing it up with execution semantics?

The path Scala is taking with language vitalisation is interesting in this regard, and then there is also the research going on at VPRI which I find very interesting.

BR,
John

Dear John,
Thanks for your note! Regarding your second point: that's called LINQ. It's got a lot going for it at this point.
Regarding the sketch, let's begin with a more pedestrian view. Monads are canonically modeled by colored braces. If we take the scala API
trait Monad[M[_]] {    def fmap [A,B] ( f : A => B ) : M[A] => M[B]    def unit [A] ( a : A ) : M[A]    def mult [A] ( mma : M[M[A]] ) : M[A]}
We can give a concrete model that is canonical -- meaning that every other interpretation factors through this interpretation.

• the endofunctor, aka type constructor, M, is the color of the braces 
• M <-> <M> ... </M>
• the unit simply wraps an element in a pair of braces
• unit( a ) <-> <M> a </M>
• the mult simply flattens nested braces
• mult( mma ) <-> <M> <M> a1 </M> <M> a2 </M> </M> |-> <M> a1, a2 </M>

Notice how this presentation is only finitary. There is no way to present infinitary objects. To extend it to infinitary objects we need comprehensions

• <M> a <- g |  P( a ) </M>, in English -- wrap all the a's coming from g (that is, generated by g) that satisfy the predicate P up in M.
• Correspondingly, in Scala we have for( a <- M( g ) if P( a ) ) yield { a }

Now, you have to ask yourself where does the language for expressing P come from? It turns out that for any (parametrically polymorphic) algebraic datatype, say A[X] (a monad!), you can generate a logic (and dually a query language) from a notion of collection, say C[X] (a monad!), and a distributive law, d [X] : A[C[X]] => C[A[X]] which tells you how to interpret expressions of the algebra over the collection into collections of elements of the algebra. Similarly, you can do the same thing for pattern-matching (which is what is happening on the left of the assignment, a <- g).
We can prove that this basic set of building blocks, polymorphic comprehensions, is functionally complete (aka Turing complete). So, we know that we have enough expressiveness here. What is needed, now, is to recover the notions

• 0-cell
• 1-cell
• ...
• n-cell

which i will leave as an exercise -- because i'm off to rehearsal!
Best wishes,
--greg

On Mon, Sep 12, 2011 at 2:06 PM, John Nilsson <john@milsson.nu> wrote:

On Mon, Sep 12, 2011 at 6:07 AM, Meredith Gregory <lgreg.meredith@gmail.com> wrote:

i suspect that it is possible to redo category theory from the ground up using monads as the core building block. The evidence i have for this point of view is that monads are effectively generalized comprehensions (see Wadler's comprehending monads as support for this view). Since we know that we can bootstrap category theory from set theory (then build topos theory on top of category theory -- replacing the notion of set -- and kick away the scaffolding, just like building gcc from the native c compiler then recompiling it with itself), and comprehensions are what make set theory tick, from an operational perspective (i.e., in set theory you do all your coding with comprehensions), a generalized, polymorphic notion of comprehension should more than suffice.

Hmm that sounds very interesting indeed. Do you have any sketches of how that might look?

What you just said resonated somewhat with a previous suspicion I've had while pondering on how relational theory might be improved and expanded to allow a the same declarative approach to general programming as SQL (somewhat) provides for data querying. Or in the other direction: how a query language supporting composable constructs might look. At the time I think I was reading that paper you linked to though, and I guess what my mind was telling me was that if I just understood monads well enough I could build a DBMS on monads instead of relations to achieve some of this.

In my thinking there is a problem with designing ever more powerful and abstract languages for encoding machine instructions when we are still missing adequately powerful and abstract languages for expressing formal requirements. Could it be that hidden in this wadler-paper and other generalised mathematics there is a workable foundation for working with the domain specific parts of our programs without mixing it up with execution semantics?

The path Scala is taking with language vitalisation is interesting in this regard, and then there is also the research going on at VPRI which I find very interesting.

BR,
John

--
L.G. Meredith
Managing Partner
Biosimilarity LLC
7329 39th Ave SWSeattle, WA 98136

+1 206.650.3740

http://biosimilarity.blogspot.com

Not that you have loads of time, but perhaps you could write up such an example, using if possible a simple but read DSL? Start off simply by showing a bit of the design of the DSL and the pitfalls and problems that happen with ad hoc design, then gradually bring in the formalisms as a way to reduce the problem. Anyone interested in good software engineering should want to read that.
Cheers,Ken

Dear Ken,
Thanks for your suggestion! If you're impatient for Monadic Design Patterns for the Web, you could look at my blog, biosimilarity.blogspot.com. Back in 2009 i gave 3 different examples, all executable as Lift applications. i'm pretty sure the code has rotted since then. It's written against Scala 2.7.7 and Lift pre 1.0. However, you're free to grab the code and update it.
Best wishes,
--greg

On Mon, Sep 12, 2011 at 7:05 PM, Ken McDonald <ykkenmcd@gmail.com> wrote:

Not that you have loads of time, but perhaps you could write up such an example, using if possible a simple but read DSL? Start off simply by showing a bit of the design of the DSL and the pitfalls and problems that happen with ad hoc design, then gradually bring in the formalisms as a way to reduce the problem. Anyone interested in good software engineering should want to read that.
Cheers,Ken

--
L.G. Meredith
Managing Partner
Biosimilarity LLC
7329 39th Ave SWSeattle, WA 98136

+1 206.650.3740

http://biosimilarity.blogspot.com

Hi!
All svn.biosim... Links are broken (404)
Reupload to github?

Regards Andreas

On 13 Sep., 09:48, Meredith Gregory wrote:
> Dear Ken,
>
> Thanks for your suggestion! If you're impatient for Monadic Design Patterns
> for the Web, you could look at my blog, biosimilarity.blogspot.com. Back in
> 2009 i gave 3 different examples, all executable as Lift
> applications.
> i'm pretty sure the code has rotted since then. It's written against Scala
> 2.7.7 and Lift pre 1.0. However, you're free to grab the code and update it.
>
> Best wishes,
>
> --greg
>
> On Mon, Sep 12, 2011 at 7:05 PM, Ken McDonald wrote:
> > Not that you have loads of time, but perhaps you could write up such an
> > example, using if possible a simple but read DSL? Start off simply by
> > showing a bit of the design of the DSL and the pitfalls and problems that
> > happen with ad hoc design, then gradually bring in the formalisms as a way
> > to reduce the problem. Anyone interested in good software engineering should
> > want to read that.
>
> > Cheers,
> > Ken
>
> --
> L.G. Meredith
> Managing Partner
> Biosimilarity LLC
> 7329 39th Ave SW
> Seattle, WA 98136
>
> +1 206.650.3740
>
> http://biosimilarity.blogspot.com

Dear Andreas,
Thanks for pointing that out! i forgot that i moved all of that over to code.google.com.

• Relatrope
• Graphatrope
• Parallelatrope

Best wishes,
--greg

On Tue, Sep 13, 2011 at 1:29 AM, Andreas Scheinert <andreas.scheinert@googlemail.com> wrote:

Hi!
All svn.biosim... Links are broken (404)
Reupload to github?

Regards Andreas

On 13 Sep., 09:48, Meredith Gregory <lgreg.mered...@gmail.com> wrote:
> Dear Ken,
>
> Thanks for your suggestion! If you're impatient for Monadic Design Patterns
> for the Web, you could look at my blog, biosimilarity.blogspot.com. Back in
> 2009 i gave 3 different examples, all executable as Lift
> applications<http://biosimilarity.blogspot.com/2009/01/3-applications-of-indexed-c...>.
> i'm pretty sure the code has rotted since then. It's written against Scala
> 2.7.7 and Lift pre 1.0. However, you're free to grab the code and update it.
>
> Best wishes,
>
> --greg
>
> On Mon, Sep 12, 2011 at 7:05 PM, Ken McDonald <ykken...@gmail.com> wrote:
> > Not that you have loads of time, but perhaps you could write up such an
> > example, using if possible a simple but read DSL? Start off simply by
> > showing a bit of the design of the DSL and the pitfalls and problems that
> > happen with ad hoc design, then gradually bring in the formalisms as a way
> > to reduce the problem. Anyone interested in good software engineering should
> > want to read that.
>
> > Cheers,
> > Ken
>
> --
> L.G. Meredith
> Managing Partner
> Biosimilarity LLC
> 7329 39th Ave SW
> Seattle, WA 98136
>
> +1 206.650.3740
>
> http://biosimilarity.blogspot.com

--
L.G. Meredith
Managing Partner
Biosimilarity LLC
7329 39th Ave SWSeattle, WA 98136

+1 206.650.3740

http://biosimilarity.blogspot.com

On Tue, Sep 13, 2011 at 2:59 AM, Meredith Gregory <lgreg.meredith@gmail.com> wrote:

Now, you have to ask yourself where does the language for expressing P come from? It turns out that for any (parametrically polymorphic) algebraic datatype, say A[X] (a monad!), you can generate a logic (and dually a query language) from a notion of collection, say C[X] (a monad!), and a distributive law, d [X] : A[C[X]] => C[A[X]] which tells you how to interpret expressions of the algebra over the collection into collections of elements of the algebra. Similarly, you can do the same thing for pattern-matching (which is what is happening on the left of the assignment, a <- g).

I was basically with you up to this part. This I'll have to let sink in slowly though, never thought about the P part in any particular depth. Do you have a link to a paper or something digging deeper into this? Or that would be the Wadler-paper again?

BR,
John

Dear John,
To the best of my knowledge, formulating a tight relationship between the language of properties used in a comprehension and the types over which the comprehensions are effected is new ground -- in the sense of carefully constructing a logic with a co-recursive relation to the notion of comprehension in operation. This is not in Wadler or anywhere else that i've researched. It may be that the algebraic set theory crowd have developed this, but i suspect not. The crucial point is that just as properties give rise to collections and collections give rise to properties, there is a corresponding polymorphic version of this.
To see an example, you can look at the discussion of 'how this stuff works' in this blog post.
Best wishes,
--greg

On Tue, Sep 13, 2011 at 2:00 PM, John Nilsson <john@milsson.nu> wrote:

On Tue, Sep 13, 2011 at 2:59 AM, Meredith Gregory <lgreg.meredith@gmail.com> wrote:

Now, you have to ask yourself where does the language for expressing P come from? It turns out that for any (parametrically polymorphic) algebraic datatype, say A[X] (a monad!), you can generate a logic (and dually a query language) from a notion of collection, say C[X] (a monad!), and a distributive law, d [X] : A[C[X]] => C[A[X]] which tells you how to interpret expressions of the algebra over the collection into collections of elements of the algebra. Similarly, you can do the same thing for pattern-matching (which is what is happening on the left of the assignment, a <- g).

I was basically with you up to this part. This I'll have to let sink in slowly though, never thought about the P part in any particular depth. Do you have a link to a paper or something digging deeper into this? Or that would be the Wadler-paper again?

BR,
John

--
L.G. Meredith
Managing Partner
Biosimilarity LLC
7329 39th Ave SWSeattle, WA 98136

+1 206.650.3740

http://biosimilarity.blogspot.com

Thanks for the examples! Being slightly out of date shouldn't be a problem.
Ken