[Haskell-beginners] Relation between monads and computations

[Brent Yorgey]

On Wed, Feb 15, 2012 at 10:31:03PM +0300, Dmitriy Matrosov wrote:
> Hi Brent, thanks for the answer!
> 
> > On Thu, Feb 09, 2012 at 02:02:59PM +0300, Dmitriy Matrosov wrote:
> > > Hi, everyone!
> > >
> > > Not so long ago i started to learn haskell, and now i have a question
> > > about relation between monads and computations. In fact, i think, that
> > > i understand it and write some explanation for myself, but i'm not
> > > sure whether my explanation is correct or not, and will be very
> > > thankful if someone check it :) Here it is (i don't know category
> > > theory and my math knowledge is poor, so if i accidently use some
> > > terms from them incorrectly - it was just my understanding).
> >
> > You say you have a question, but from reading the below I am not sure
> > what your question is...
> 
> The original question was: "Am i right?". I just try to understand what monad
> is, and, because it is referred as computations, i try to understand why.
> E.g. from [2], end of section 2.1:
> "Just as the type Value represents a value, the type M Value can be thought of
> as representing a computation. The purpose of unitM is to coerce a value into
> computation; the purpose of bindM is to evaluate a computation, yielding a
> value."

"The purpose of bindM is to evaluate a computation, yielding a value"
-- I have the greatest respect for Phil Wadler, but this is simply
wrong.  From this description one would expect bindM to have the type

  bindM :: M a -> a

but it does not.

> Similarly, it often referred as computation in [1]. (Though, i don't finish
> reading both of these papers).

Referring to values of type M a as "computations" is just supposed to
give some intuition, it is not a precise statement or a definition in
any sense.  Monads are one possible formal framework for *defining*
what we mean by "computation".  So trying to understand how monads are
computations will not get you anywhere.  Instead, you should just try
to understand various examples of monads, and eventually you may get
some insight into how they can be thought of as "computations".

> May i ask you then, what is the precise definition of monad? The only other
> definition besides "the computation", which i know, is "a triple of (M, unitM,
> bindM)" (from [2]),

Yes. A monad is a triple (M, unitM, bindM) satisfying a certain set of
equational laws.

> but it does not explain to me what this may have common
> with computations.

Of course it doesn't.  The definition of the Peano naturals does not
explain what they have to do with counting.  The definition of a group
does not explain what it has to do with symmetry.  Etc.

> Definition of computation, which i assume, is something (may be better to say
> triple), which have initial value, some transformation (function? or action?)
> and the result. Is this definition correct?

No.  If you want to *define* computation, then in this context one
should say "the definition of computation is a value of type M a,
where M is a monad"!  The word "computation" has been chosen because
this turns out to correspond to certain intuitive ideas people have
about that word but to really understand which intuitive ideas are
meant you will have to study the definition and examples of monads.

> >
> > In this case a function of type  a -> [b]  might produce a list
> > containing multiple values of type b.  There is no single value of
> > type b which is the "result", and there is no constructor which wraps
> > a single value of type b into a list.
> 
> Well, you're right, this should be rewritten. Here i just try to recognise in
> monad all three parts of my computation definition. Then: "the result of
> computation is values E1,.. En of type b from which using constructors
> ConstrM1,.. ContrMk may be made computation C of type M b". Is the
> idea right?

Not really.  I advise you to forget the idea of defining what the
"result" of a computation is.  As I said above, the quote from Phil
Wadler about running a computation and extracting its result is wrong
(or at the very least, extremely unhelpful).

> 
> > >
> > > Now, using fucntions unitM and bindM there is possibly to convert arbitrary
> > > function (k :: a -> b), which makes from initial value of type a value of type
> > > b, into terms of general computation (represented by type M).
> >
> > Yes, (k :: a -> b) can be converted into a function of type  (a -> M
> > b), but I think you have made it more complicated than necessary.  All
> > you need to do is  (unitM . k).
> 
> Hmm, so i was wrong here. Initially, i suppose, that the purpose of bindM is
> to convert function of type (a -> b) into function of type (a -> M b), but now
> i see it is wrong. Mentioned above quote from [2] says, that "the purpose of
> bindM is to evaluate a computation, yielding a value.", which sounds a little
> unfinished to me.  Then may be: the purpose of bindM is to make composition
> of functions of type (a -> M b) and (b -> M c) possible. Is this
> right?

Yes!  In fact, there is a standard operator

  (>=>) :: Monad m => (a -> m b) -> (b -> m c) -> (a -> m c)

which is defined in terms of bind.  Implementing it is a good
exercise.

By the way, you may be interested in reading the Typeclassopedia:

  http://www.haskell.org/haskellwiki/Typeclassopedia

-Brent