Asymmetry in the bind function

ghci> :t (>>=)
(>>=) :: Monad m => m a -> (a -> m b) -> m b

How come the second argument is (a -> m b) instead of (m a -> m b) or even (a -> b)? What is it conceptually about Monads that requires this signature? Would it make 开发者_如何学Csense to have type classes with the alternative signatures t a -> (t a -> t b) -> t b resp. t a -> (a -> b) -> t b?

---

A more symmetric definition of a monad is the Kleisli combinator, which is basically (.) for monads:

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

It can replace (>>=) in the monad's definition:

f >=> g = \a -> f a >>= g

a >>= f = const a >=> f $ ()

---

It is usual in Haskell to define Monad in terms of return and (>>=):

class Monad m where
    (>>=) :: m a -> (a -> m b) -> m b
    return :: a -> m a

However, we could instead use this equivalent definition, which is closer to the original mathematical one:

class Monad m where
    fmap :: (a -> b) -> m a -> m b
    join :: m (m a) -> m a
    return :: a -> m a

As you can see, the asymmetry of (>>=) has been replaced with the asymmetry of join, which takes m (m a) and “squishes” the two layers of m into just m a.

You can also see that the signature of fmap matches your t a -> (a -> b) -> t b, but with the parameters reversed. This is the operation that characterises the typeclass Functor, which is strictly weaker than Monad: every monad can be made a functor, but not every functor can be made a monad.

What does this all mean in practice? Well, when transforming something that is only a functor, you can use fmap to transform the values “within” the functor, but those values can never influence the “structure” or “effect” of the functor itself. With a monad, however, that restriction is lifted.

As a concrete example, when you do fmap f [1, 2, 3], you know that no matter what f does, the resulting list will have three elements. However, when you do [1, 2, 3] >>= g, it is possible for g to transform each of those three numbers into a list containing any number of values.

Similarly, if I do fmap f readLn, I know that it can't perform any I/O actions other than reading a line. If I do readLn >>= g, on the other hand, it's possible for g to inspect the value that was read and then use that to decide whether to print out a message, or read n more lines, or do anything else that is possible within IO.

---

a very nice answer to this question was given by Brian Beckman in the (in my opinion) great introduction to monads: Don't fear the Monad

You may also have a look at this nice chapter from "Learn you a haskell": A Fistful of Monads. This too explains it very well.

If you want to be pragmatic: it has to be that way to get the "do"-languague feature going ;) - but Brian and Lipovaca explains it much better (and deeper) than that ;)

PS: to your alternatives: the first is more or less the application of the second argument to the first. The second alternative is almost fmap of the Functor-type class - only with switched arguments (and every Monad is a Functor - even if the Haskell type-class doesn't constrain it to be - but it should - but this is another topic ;) )

---

Well, the type of (>>=) is convenient for desugaring do notation, but somewhat unnatural otherwise.

The purpose of (>>=) is to take a type in the monad, and a function that uses an argument of that type to create some other type in the monad, then combine them by lifting the function and flattening the extra layer. If you look at the join function in Control.Monad, it performs only the flattening step, so if we took it as the primitive operation we could write (>>=) as so:

(>>=) :: (Monad m) => m a -> (a -> m b) -> m b
m >>= k = join (fmap k m)

Note, however, the reversed order of arguments to fmap. The reason for that becomes clear if we think about the Identity monad, which is just a newtype wrapper around plain values. Ignoring the newtypes, fmap for Identity is function application and join does nothing, so we can recognize (>>=) as being an application operator with it's arguments reversed. Compare the type of this operator, for example:

(|>) :: a -> (a -> b) -> b
x |> f = f x

A very similar pattern. So, to get a clearer idea of what the meaning of (>>=)'s type is, we'll instead look at (=<<), which is defined in Control.Monad, which takes its arguments in the other order. Comparing it with (<*>), from Control.Applicative, fmap, and ($), and keeping in mind that (->) is right-associative and adding in the superfluous parentheses:

($)   ::                       (a ->   b) -> (  a ->   b)
fmap  :: (Functor f)     =>    (a ->   b) -> (f a -> f b)
(<*>) :: (Applicative f) =>  f (a ->   b) -> (f a -> f b)
(=<<) :: (Monad m)       =>    (a -> m b) -> (m a -> m b)

So all four of these are essentially function application, the latter three being ways of "lifting" functions to work on values in some functor type. The differences among them are essential to how plain values, Functor, and the two classes based on it differ. In a loose sense, the type signatures can be read as follows:

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

This means that given a plain function a -> b, we can convert it into a function that does the same thing on types f a and f b. So it's just a simple transformation that can't alter or inspect the structure of f, whatever it is.

(<*>) :: (Applicative f) => f (a -> b) -> (f a -> f b)

Just like fmap, except that it takes a function type that itself is already in f. The function type is still oblivious to the structure of f, but (<*>) itself has to combine two f structures in some sense. So this can alter and inspect the structure, but only in a way determined by the structures themselves, independent of the values.

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

This is a deep, fundamental shift, because now we take a function that creates some m structure, which gets combined with the structure already present in the m a argument. So (=<<) can not only alter the structure as above, but the function being lifted can create new structure depending on the values. There is still a significant limitation, though: the function only receives a plain value, and thus can't inspect the overall structure; it can only inspect a single location and then decide what kind of structure to put there.

So, the get back to your question:

Would it make sense to have type classes with the alternative signatures t a -> (t a -> t b) -> t b resp. t a -> (a -> b) -> t b?

If you rewrite both of those types in the "standard" order as above, you can see that the first is just ($) with a specialized type, while the second is fmap. There are other variations that make sense, however! Here's a couple examples:

contramap :: (Contravariant f) => (a -> b) -> (f b -> f a)

This is a contravariant functor, which works "backwards". If the type looks impossible at first, think about the type newtype Flipped b a = Flipped (a -> b) and what you could do with it.

(<<=) :: (Comonad w) => (w a -> b) -> (w a -> w b)

This is the dual of a monad--whereas the argument to (=<<) can only inspect a local area and produce a piece of structure to put there, the argument to (<<=) can inspect a global structure and produce a summary value. (<<=) itself typically scans over the structure in some sense, taking the summary value from each perspective, then reassembles them to create a new structure.

---

m a -> (a -> b) -> m b is the behaviour of Functor.fmap, which is quite useful. However it is more limited than >>=. E.g. if you deal with lists, fmap can change that elements and their types, but not the length of the list. On the other hand, >>= can do this easily:

[1,2,3,4,5] >>= (\x -> replicate x x)
-- [1,2,2,3,3,3,4,4,4,4,5,5,5,5,5]

m a -> (m a -> m b) -> m b is not very interesting. This is just function application (or $) with reversed arguments: I have a function m a -> m b and provide an argument m a, then I get m b.

[Edit]

Strange enough, nobody mentioned the fourth possible signature: m a -> (m a -> b) -> m b. This actually makes sense as well, and leads to Comonads

---

I'm going to attempt to answer this by working backwards.

Introduction

At a basic level, we have values: things with types like Int, Char, String*, etc. Generally these have the polymorphic type a, which is just a type variable.

Sometimes it's useful to have a value in a context. Following sigfpe's blog, I like to think of this as a fancy value. For example, if we have something that might be an Int but might not be anything, it's in the Maybe context. If something is either an Int or a String, it's in the Either String context. If a value is possibly one of several difference Chars, it's in the indeterminism context, which in haskell is a list, i.e. [Char].

(somewhat advanced: a new context is introduced with a type constructor, which has kind * -> *).

Functors

If you've got a fancy value (value in context), it would be nice to be able to apply a function to it. Of course you can write specific functions to do this for every different context (Maybe, Either n, Reader, IO, etc), but we'd like to use the same interface in all these cases. This is provided by the Functor type class.

Functor's only method is fmap, which has the type (a -> b) -> f a -> f b. This means, if you have a function from type a to type b, you can apply it to a fancy a to get a fancy b, where b is fancy in exactly the same way that a is.

g' = fmap (+1) (g :: Maybe Int)          -- result :: Maybe Int

h' = fmap (+1) (h :: Either String Int)  -- result :: Either String Int

i' = fmap (+1) (i :: IO Int)             -- result :: IO Int

Here g', h', and i' have exactly the same contexts as g, h, and i. The context doesn't change, only the value within it.

(The next step is Applicative, which I'll skip over for now).

Monads

Sometimes it's not enough to just apply a function to a fancy value. Sometimes you want to branch based upon that value. That is, you want the new context to depend upon the current context and the current value. An example of where you might want this:

safe2Div :: Int -> Maybe Int
safe2Div 0 = Nothing
safe2Div n = Just (2 `div` n)

How do you apply this to a Maybe Int? You can't use fmap, because

fmap safe2Div (Just 0) :: Maybe (Maybe Int)

which looks even more complicated.* You need a function Maybe Int -> (Int -> Maybe Int) -> Maybe Int

Or maybe this:

printIfZ :: Char -> IO ()
printIfZ 'z' = putStrLn "z"
printIfZ _   = return ()

How can you apply this to an IO Char? Again, you want a function IO Char -> (Char -> IO ()) -> IO () to perform the appropriate IO action depending on the value.

Generally, this gives you the type signature

branchContext :: f a -> (a -> f b) -> f b

which is exactly the capability provided by Monad's (>>=) method.

I would recommend the Typeclassopedia for more information on this.

Edit: as to t a -> (t a -> t b) -> t b, there's no need for a type class for this, as it's just flipped function application, i.e. flip ($). This is because it doesn't depend on the context structure or internal value at all.

*- ignore that String is a type synonym for [Char]. It's still a value regardless.

*- it looks more complicated, but it turns out that (>>=) :: m a -> (a -> m b) -> m b and join :: m (m a) -> m a give you exactly the same power. (>>=) is usually more useful in practice though.

---

What is it conceptually about Monads that requires this signature?

Basically, everything. Monads are all about this particular type signature, at least they are from one way of looking at them.

The "bind" type signature m a -> (a -> m b) -> m b basically says: "I've got this a, but it's stuck in Monad m. And I have this monadic function that will take me from a to m b. I can't just apply an a to this function, though, because I don't have just an a, it's an m a. So let's invent a function sort of like $ and call it >>=. Anything that is a Monad basically has to tell me (define) how to unwrap an a from m a so that I can use this function a -> m b on it."

---

Every monad is connected to some "adjunction", which is a pair of maps which are a kind of partial inverses to each other. For example, consider the "goInside" and "goOutside" pair. You start inside, and then goOutside. You are now outside. If you goInside, you end up back inside.

Notice how being inside and outside are related -- by this pair of functions which map an object or person back and forth.

Bind is a function that takes a value "inside" the monad, puts it in a context outside of the monad, a function into the monad, and and then yields a value back inside the monad, so that you are always assured to be in the correct starting place for continued operations.

This allows us to switch between two contexts at will -- the "pure" (I'm using that in a vague, suggestive sense) context outside of the monad, and the monadic context inside of it.