[Haskell-beginners] Relation between monads and computations

[Dmitriy Matrosov]

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."
Similarly, it often referred as computation in [1]. (Though, i don't finish
reading both of these papers).

> Let me say first that while "monad" has a precise technical
> definition, "computation" does not.  So "the relation between monads
> and computations" is not well-defined unless it is specified what you
> mean by "computation".  There are many ways to model different ideas
> of "computation"; one of them is monads, but that is not the only way.

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]), but it does not explain to me what this may have common
with computations.

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?

> > Monads and computations.
> >
> > Generally computation consists of initial value, computation itself and the
> > result. So it can be illustrated as:
> >
> >     type    a         (M b)            b
> >     data    I ------>   C   <--------- E
> >                  f            ConstrM
> >
> >     I :: a
> >     f :: a -> M b
> >     data M a = ContrM a | ...
> >     E :: b
> >
> > Let's see what happens: i take initial value I of type a and map it to some
> > computation C (of type (M b)) using function f. Then, exist such value E of
> > type b, that C = (ConstrM E). This value E will be the result of
> > computation.
>
> That last part ("there exists a value E of type b ...") doesn't seem
> right to me.  There is no guarantee or requirement that a monad M be
> defined so there is a constructor wrapping the "result".  For example,
> consider the list type:
>
>   data [a] = [] | (a : [a])
>
> 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?

> >
> > 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?

References:
[1] Hal Daume III, "Yet another haskell tutorial"
[2] Philip Wadler, "The essence of functional programming"

--
    Dmitriy Matrosov