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