Some questions about monads in Haskell

I'm learning about monads and have a few questions.

This is where I am right now. Please correct me where I am wrong.

• The >>= symbol is an infix operator. Infix operators are functions that take two arguments (left-hand side and right-hand side) and return a value.

• The >>= symbol is called th开发者_C百科e bind operator and has signature Monad m => m t -> (t -> m u) -> m u. However, the types don't seem to line up here. We get a value of type m t and the second argument is a function that takes a t. (I don't see how to connect the dots.)

• This must mean that the bind function is somehow able to remove the m from the m t in order to get the t and pass it to the function.

Here are my questions:

• Is the ability to remove the m from m t something that is only possible inside such a bind operator. Does this bind operator have some special priviliges or something?

• What does it have to do with state changes? I understand (I think) that the goal of monads is to 'wrap' side-effects so that they are isolated from the rest of the program. But what is the role of the bind operator in this?

is the ability to remove the 'M' from 'M t' something that is only possible inside such a bind operator.

Well, it is certainly possible inside the bind operator, as its type specifies:

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

The 'run' function for your monad can usually do this as well (to return a pure value from your computation).

the goal of monads is to 'wrap' side-effects so that they are isolated from the rest of the program

Hmm. No, monads let us model notions of computation. Side-effecting computations are just one such notion, as is state, backtracking, continuations, concurrency, transactions, optional results, random results, revertable state, non-determinism ... all of which can be described as a monad

The IO monad is what you're referring to, I assume. It is a slightly odd monad -- it generates sequences of abstract changes to the world's state, which are then evaluated by the runtime. Bind just lets us sequence things in the right order in the IO monad -- and the compiler will then translate all these sequenced world-modifying actions into imperative code that changes that state of the machine.

That's very specific to the IO monad though, not monads in general.

Is the ability to remove the 'M' from 'M t' something that is only possible inside such a bind operator. Does this bind operator have some special priviliges or something?

Bind is not in any way a special case, but usually it will be defined in the same module as the monads data type. Therefore it might know about (and use) details that are not exported by the module. The usual case would be that the module exports a data type, but not it's constructors or other details about the types inner structure. Then for code that uses the module the inner workings of the data type are invisible and that code cannot directly modify values of this type.

Opposed to that functions defined inside the module, like for example some bind operator >>=, can access whatever they like from the module they are defined in. So such functions might be able to do things "external" functions cannot do.

A special case is the IO monad, since it's not defined by a module, but built into the runtime system/compiler. Here the compiler knows about the inner details of it's implementation and exposes functions like IO's >>=. The implementations of these functions indeed are specially privileged since they live "outside of the program", but this is a special case and this fact should not be observable from within Haskell.

What does it have to do with state changes? I understand (I think) that the goal of monads is to 'wrap' side-effects so that they are isolated from the rest of the program. But what is the role of the bind operator in this?

It doesn't really need to have to do with state changes, this is just one problem that can be handled with moands. The IO monad is used to have IO executed in a certain order, but generally monads are just ways of combining functions together.

Generally a monad (specifically it's bind function) defines a way in which certain functions should be composed together to bigger functions. This method of combining functions is abstracted in the monad. How exactly this combining works or why you would want to combine functions in such a way is not important, a monad just specifies a way of combining certain functions in a certain way. (See also this "Monads for C# programmers" answer where I basically repeat that a few times with examples.)

The following is the definition of the type-class Monad.

class  Monad m  where

    (>>=)       :: forall a b. m a -> (a -> m b) -> m b
    (>>)        :: forall a b. m a -> m b -> m b
    return      :: a -> m a
    fail        :: String -> m a

    m >> k      = m >>= \_ -> k
    fail s      = error s

Each type-instance of type-class Monad defines its own >>= function. Here is an example from the type-instance Maybe:

instance  Monad Maybe  where

    (Just x) >>= k      = k x
    Nothing  >>= _      = Nothing

    (Just _) >>  k      = k
    Nothing  >>  _      = Nothing

    return              = Just
    fail _              = Nothing

As we can see, because the Maybe version of >>= is specially defined to understand the Maybe type-instance, and because it is defined in a place that has legal access to the data Maybe a data constructors Nothing and Just a, the Maybe version of >>= is able to unwrap the a's in Maybe a and pass them through.

To work through an example, we might take:

x :: Maybe Integer
x = do a <- Just 5
       b <- Just (a + 1)
       return b

De-sugared, the do-notation becomes:

x :: Maybe Integer
x = Just 5        >>= \a ->
    Just (a + 1)  >>= \b ->
    Just b

Which evaluates as:

  =                  (\a ->
    Just (a + 1)  >>= \b ->
    Just b) 5

  = Just (5 + 1)  >>= \b ->
    Just b

  =                  (\b ->
    Just b) (5 + 1)

  = Just (5 + 1)

  = Just 6

The types do line up, funnily enough. Here's how.

Remember that a monad is also a functor. The following function is defined for all functors:

fmap :: (Functor f) => (a -> b) -> f a -> f b

Now the question: Do these types really line up? Well, yes. Given a function from a to b, then if we have an environment f in which a is available, we have an environment f in which b is available.

By analogy to syllogism:

(Functor Socrates) => (Man -> Mortal) -> Socrates Man -> Socrates Mortal

Now, as you know, a monad is a functor equipped with bind and return:

return :: (Monad m) => a -> m a
(=<<) :: (Monad m) => (a -> m b) -> m a -> m b

You may not know that equivalently, it's a functor equipped with return and join:

join :: (Monad m) => m (m a) -> m a

See how we're peeling off an m. With a monad m, you can't always get from m a to a, but you can always get from m (m a) to m a.

Now look at the first argument to (=<<). It's a function of type (a -> m b). What happens when you pass that function to fmap? You get m a -> m (m b). So, "mapping" over an m a with a function a -> m b gives you m (m b). Notice that this is exactly like the type of the argument to join. This is not a coincidence. A reasonable implementation of "bind" looks like this:

(>>=) :: m a -> (a -> m b) -> m b
x >>= f = join (fmap f x)

In fact, bind and join can be defined in terms of each other:

join = (>>= id)

I VERY MUCH recommend that you read (http://blog.sigfpe.com/2006/08/you-could-have-invented-monads-and.html). It gives a perfect, common sense reason why monads exist.

I understand (I think) that the goal of monads is to 'wrap' side-effects so that they are isolated from the rest of the program.

Its actually a bit more subtle than that. Monads allow us to model sequencing in a very general way. Often when you talk to a domain expert you find them saying something like "first we try X. Then we try Y, and if that doesn't work then we try Z". When you come to implement something like that in a conventional language you find that it doesn't fit, so you have to write lots of extra code to cover whatever the domain expert meant by the word "then".

In Haskell you can implement this as a monad with the "then" translated into the bind operator. So for instance I once wrote a program where an item had to be assigned from pools according to certain rules. For case 1 you took it from pool X. If that was empty then you moved on to pool Y. For case 2 you had to take it straight from pool Y. And so on for a dozen or so cases, including some where you took the least recently used from either pool X or Y. I wrote a custom monad specially for that job so that I could write:

case c of
   1: do {try poolX; try poolY}
   2: try poolY
   3: try $ lru [poolX, poolY]

It worked very well.

Of course this includes conventional models of sequencing. The IO monad is the model that all other programming languages have; its just that in Haskell its an explicit choice rather than part of the environment. The ST monad gives you the memory mutation of IO, but without the actual input and output. On the other hand the State monad lets you restrict your state to a single value of a named type.

For something really brain bending, see this blog post about a backward state monad. The state propagates in the opposite direction to the "execution". If you think of this as like a state monad executing one instruction followed by the next, then a "put" will send the state value backwards in time to any preceeding "get". What actually happens is that a mutually recursive function gets set up that only terminates if there are no paradoxes. I'm not quite sure where to use such a monad, but it illustrates the point about monads being models of computation.

If you are not ready for that, then just think of bind as an overloadable semicolon. That gets you quite a long way.