Understanding bind function in Haskell

Question

I am familiar with monads in category theory (they are a very easy concept, in fact), yet >>= function in Haskell completely puzzles me. Ok, so applying bind to a value of M a and a function a -> M u is the same as first applying the monad to this function, then evaluating it at the specified value and multiplying the result: a >>= f is the same as join $ (fmap f) $ a. But how is this a natural description of computation? Is there some useful way of looking at it that would help me understand it?

Is there some nice article somewhere that is not geared towards someone fresh from the C++ jungle?

Answer 1

Consider the monadic function composition operator <=<. This is analogous to . except it works on monadic functions. It can be defined simply in terms of >>=, so learning about one will educate us about the other.

(<=<) :: (a -> m b) -> (b -> m c) -> a -> m c
(f <=< g) x =  g x >>= f

(.) :: (a -> b) -> (b -> c) -> a -> c
(f . g) x = g x |> f
  where z |> h = h z

In the case of ., g is "performed" first, and then f is performed on the output of g. In the case of <=<, g and its effects are "performed" first, and then f and its effects are performed. It's a bit of a misnomer to say that one happens "before" the other, actually, since not all monads work that way.

Perhaps it is more accurate to say that f can take advantage of additional contextual information provided by g. But that's not entirely correct, since g could potentially take away contextual information. If you want to 100% correctly describe monads, you really have to walk on eggshells.

But in almost all nontrivial cases, f <=< g means that the effects (as well as the result) of the monadic function g will subsequently influence the behavior of the monadic function f.

---

To address questions about v >>= f = join (fmap f v)

Consider f :: a -> m b and v :: m a. What does it mean to fmap f v? Well fmap :: (c -> d) -> m c -> m d, and in this case c = a and d = m b, so fmap f :: m a -> m (m b). Now, of course, we can apply v :: m a to this function, resulting in m (m b). but what exactly does that result type m (m b) mean?

The inner m represents the context from produced from f. The outer m represents the context originating from v (n.b. fmap should not disturb this original context).

And then you join that m (m b), smashing those two contexts together into m a. This is the heart of the definition of Monad: you must provide a way to smash contexts together. You can inspect the implementation details of various Monad instances to try and understand how they "smash" contexts together. The takeaway here, though, is that the "inner context" is unobservable until you merge it with the "outer context". If you use v >>= f, then there is no actual notion of the function f receiving a pure value a and producing a simple monadic result m b. Instead, we understand that f acts inside the original context of v.

Answer 2

Hmm. I think a good way to think of it is that >>= lets you compose computations; the computations themselves are in the form a -> m b. So m b just represents the result of a computation.

So a computation just takes some value and produces some result. A good example here is the list type: a -> [b] represents a non-deterministic computation. It takes one input but can produce multiple results. By itself, the a -> [b] as a computation makes sense. But how would you combine these? The natural answer is that you would perform each consecutive "computation" on all of the previous results. And this is exactly what >>= does for lists.

One thing that really helped me see the practical value of this was thinking about DFAs and NFAs. You can imagine trivially writing a DFA in Haskell something like this:

data State = S1 | S2 | S3 | S4 | Q
data Input = A | B
transition :: State -> Input -> State
transition S1 A = S2
transition S1 B = S3
-- and so on...

Then we could just fold over input:

 foldl transition S1 [A, A, B, B]

Now, how would we take this code and generalize it to NFAs? Well, the transition "function" for an NFA can be thought of as a non-deterministic computation. So we define something like:

transition S1 A = [S1, S2]
transition S1 B = []

But now we'd have to do some weird gymnastics to use foldl! Happily, we can just foldM instead. So here the "computation" modeled by the monad is the non-deterministic transition function.

Answer 3

Perhaps =<< is easier to understand from a computation point of view (it's just flip (>>=)). It has typing (=<<) :: (Monad m) => (a -> m b) -> m a -> m b, and corresponds to the type of function application, cf ($) :: (a -> b) -> a -> b. So >>= is just flipped function application on the monadic level.

Also, (>>=) is used in desugaring do notation, and do syntactically corresponds very much to imperative code (in a suitable monad).

Answer 4

Here's a rough idea of how it works out as a model of computation: A type constructor M with an instance of Monad represents a parametric data structure, and the non-parametric parts of that structure can contain other information. The return and join correspond to some sort of monoid for those parts of the structure. A function a -> M b introduces information in that structure, based on an input of type a. So by lifting a function a -> M b to M a -> M b we're using the parametric information of M to create some non-parametric information, then combining that with the information already present in a value of type M a.

The asymmetric nature of the type a -> M b gives an inherent direction to the flow of non-parametric information, while the associativity requirement means that the overall order is the only thing that matters.

The end result is augmenting functions with some sort of context that has a built-in notion of cause-and-effect.