Mark, On Sep 21, 2005, at 8:12 PM, Mark Carter wrote:
instance Monad SM where -- defines state propagation SM c1 >>= fc2 = SM (\s0 -> let (r,s1) = c1 s0 SM c2 = fc2 r in c2 s1) return k = SM (\s -> (k,s))
just confuses me no end.
I think, Philippa already did a good job explaining what goes on here. If I may add to that, I myself often find it quite helpful to first try to implement the function myself and then have a look at the provided implementation to see where it coincides with my attempt and, more importantly, where differences occur. For the bind operator, (>>=), of the state monad, SM, you then start with what you already know, i.e., the types: data SM a = SM (S -> (a, S)) (>>=) :: SM a -> (a -> SM b) -> SM b (For some abstract type S representing the state.) Then , you try to write down your own definition of (>>=) without looking at the provided implementation. The left-hand side is fairly easy, for SM has only one constructor: SM h >>= f = ... Keep in mind the types of h and f: h :: S -> (a, S) f :: a -> SM b Our goal is to produce a value of type SM b. Again, since SM has only one constructor, there's no doubt on the form of such a value: SM h >>= f = SM g With g :: S -> (b, S) It remains to find a suitable definition of the function g. By its type, we know that g should take an argument of type S, so we have: SM h >>= f = SM g where g s = ... To construct the right-hand side of g, we have available the functions h and f. Arguably the only useful thing you can do with a function is applying it. Here, h is the only function that can be applied to a value of type S, so let's apply it to s. Then, by the type of h, we obtain a pair (a, s') with a :: a and s' :: S: SM h >>= f = SM g where g s = let (a, s') = h s in ... The first component of the pair, a, can now be fed as an argument to the function f to obtain a a value of type SM b. Once again, because SM has only one constructor, the form of this value is obvious: SM h >>= f = SM g where g s = let (a, s') = h s SM k = f a in ... With k :: S -> (b, S) Note that the the result type of k is exactly the result type we need for g. So all that's left is supplying k with an argument of type S. Choosing s', we obtain: SM h >>= f = SM g where g s = let (a, s') = h s SM k = f a in k s' Rewriting this a bit will give you the provided definition for (>>=). Note how we have let the types guide the construction of (>>=). Of course, it's not all that simple. For instance, choosing the original state s to be passed to the function k in the last step would have also given us a type-correct program. However, that definition would not have captured the concept of sequencing, for the intermediate state s' would have been discarded. So, although following the types can make defining functions that seem complicated at first sight more easy, you still have to be aware of what you are defining. However, as soon as you get a bit more familiar with the concept of a monad and, more particular, the bind operation, understanding non-trivial monads like the state monad turns out to be not that hard after all. HTH, Stefan