Haskell Monad bind operator confusion

Question

Okay, so I am not a Haskell programmer, but I am absolutely intrigued by a lot of the ideas behind Haskell and am looking into learning it. But I'm stuck at square one: I can't seem to wrap my head around Monads, which seem to be fairly fundamental. I know there are a million questions on SO asking to explain Monads, so I'm going to be a little more specific about what's bugging me:

I read this excellent article (an introduction in Javascript), and thought that I understood Monads completely. Then I read the Wikipedia entry on Monads, and saw this:

A binding operation of polymorphic type (M t)→(t→M u)→(M u), which Haskell represents by the infix operator >>=. Its first argument is a value in a monadic type, its second argument is a function that maps from the underlying type of the first argument to another monadic type, and its result is in that other monadic type.

Okay, in the article that I cited, bind was a function which took only one argument. Wikipedia says two. What I thought I understood about Monads was the following:

1. A Monad's purpose is to take a function with different input and output types and to make it composable. It does this by wrapping the input and output types with a single monadic type.
2. A Monad consists of two interrelated functions: bind and unit. Bind takes a non-composable function f and returns a new function g that accepts the monadic type as input and returns the monadic type. g is composable. The unit function takes an argument of the type that f expected, and wraps it in the monadic type. This can then be passed to g, or to any composition of functions like g.

But there must be something wrong, because my concept of bind takes one argument: a function. But (according to Wikipedia) Haskell's bind actually takes two arguments! Where is my mistake?

Solution 1

You are not making a mistake. The key idea to understand here is currying - that a Haskell function of two arguments can be seen in two ways. The first is as simply a function of two arguments. If you have, for example, (+), this is usually seen as taking two arguments and adding them. The other way to see it is as a addition machine producer. (+) is a function that takes a number, say x, and makes a function that will add x.

(+) x = \y -> x + y
(+) x y = (\y -> x + y) y = x + y

When dealing with monads, sometimes it is probably better, as ephemient mentioned above, to think of =<<, the flipped version of >>=. There are two ways to look at this:

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

which is a function of two arguments, and

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

which transforms the input function to an easily composed version as the article mentioned. These are equivalent just like (+) as I explained before.

Solution 2

Allow me to tear down your beliefs about Monads. I sincerely hope you realize that I am not trying to be rude; I'm simply trying to avoid mincing words.

A Monad's purpose is to take a function with different input and output types and to make it composable. It does this by wrapping the input and output types with a single monadic type.

Not exactly. When you start a sentence with "A Monad's purpose", you're already on the wrong foot. Monads don't necessarily have a "purpose". Monad is simply an abstraction, a classification which applies to certain types and not to others. The purpose of the Monad abstraction is simply that, abstraction.

A Monad consists of two interrelated functions: bind and unit.

Yes and no. The combination of bind and unit are sufficient to define a Monad, but the combination of join, fmap, and unit is equally sufficient. The latter is, in fact, the way that Monads are typically described in Category Theory.

Bind takes a non-composable function f and returns a new function g that accepts the monadic type as input and returns the monadic type.

Again, not exactly. A monadic function f :: a -> m b is perfectly composable, with certain types. I can post-compose it with a function g :: m b -> c to get g . f :: a -> c, or I can pre-compose it with a function h :: c -> a to get f . h :: c -> m b.

But you got the second part absolutely right: (>>= f) :: m a -> m b. As others have noted, Haskell's bind function takes the arguments in the opposite order.

g is composable.

Well, yes. If g :: m a -> m b, then you can pre-compose it with a function f :: c -> m a to get g . f :: c -> m b, or you can post-compose it with a function h :: m b -> c to get h . g :: m a -> c. Note that c could be of the form m v where m is a Monad. I suppose when you say "composable" you mean to say "you can compose arbitrarily long chains of functions of this form", which is sort of true.

The unit function takes an argument of the type that f expected, and wraps it in the monadic type.

A roundabout way of saying it, but yes, that's about right.

This [the result of applying unit to some value] can then be passed to g, or to any composition of functions like g.

Again, yes. Although it is generally not idiomatic Haskell to call unit (or in Haskell, return) and then pass that to (>>= f).

-- instead of
return x >>= f >>= g
-- simply go with
f x >>= g

-- instead of
\x -> return x >>= f >>= g
-- simply go with
f >=> g
-- or
g <=< f

Solution 3

The article you link is based on sigfpe's article, which uses a flipped definition of bind:

The first thing is that I've flipped the definition of bind and written it as the word 'bind' whereas it's normally written as the operator >>=. So bind f x is normally written as x >>= f.

So, the Haskell bind takes a value enclosed in a monad, and returns a function, which takes a function and then calls it with the extracted value. I might be using non-precise terminology, so maybe better with code.

You have:

sine x = (sin x,     "sine was called.")
cube x = (x * x * x, "cube was called.")

Now, translating your JS bind (Haskell does automatic currying, so calling bind f returns a function that takes a tuple, and then pattern matching takes care of unpacking it into x and s, I hope that's understandable):

bind f (x, s) = (y, s ++ t)
                where (y, t) = f x

You can see it working:

*Main> :t sine
sine :: Floating t => t -> (t, [Char])
*Main> :t bind sine
bind sine :: Floating t1 => (t1, [Char]) -> (t1, [Char])
*Main> (bind sine . bind cube) (3, "")
(0.956375928404503,"cube was called.sine was called.")

Now, let's reverse arguments of bind:

bind' (x, s) f = (y, s ++ t)
                 where (y, t) = f x

You can clearly see it's still doing the same thing, but with a bit different syntax:

*Main> bind' (bind' (3, "") cube) sine
(0.956375928404503,"cube was called.sine was called.")

Now, Haskell has a syntax trick that allows you to use any function as an infix operator. So you can write:

*Main> (3, "") `bind'` cube `bind'` sine
(0.956375928404503,"cube was called.sine was called.")

Now rename bind' to >>= ((3, "") >>= cube >>= sine) and you've got what you were looking for. As you can see, with this definition, you can effectively get rid of the separate composition operator.

Translating the new thing back into JavaScript would yield something like this (notice that again, I only reverse the argument order):

var bind = function(tuple) {
    return function(f) {
        var x  = tuple[0],
            s  = tuple[1],
            fx = f(x),
            y  = fx[0],
            t  = fx[1];

        return [y, s + t];
    };
};

// ugly, but it's JS, after all
var f = function(x) { return bind(bind(x)(cube))(sine); }

f([3, ""]); // [0.956375928404503, "cube was called.sine was called."]

Hope this helps, and not introduces more confusion — the point is that those two bind definitions are equivalent, only differing in call syntax.

Comments

[Dan Burton]

I suppose to avoid the JS ugliness, you could modify the Function prototype, and use it "infix": g.mBind(f.mBind(mv)), comparable to g =<< f =<< mv. Nicer might be to define it in the prototype of the monadic value: mv.bind(f).bind(g), comparable to mv >>= f >>= g. Note the Function prototype apparently already has "bind" defined as something.

[Ord]

So x >>= f (or f =<< x) can be understood to mean: take f, wrap it so that it accepts a monadic type, and then call the wrapped function with the argument x?

[Ord]

Thank you for helping me to understand. But if I have a function g :: m a -> m b, why wouldn't I just use f :: a -> b? I can't compose g with other functions of like signature. So what are some of the other purposes of monads that would make g more useful than f?

[Ord]

Okay, I might be able to think up a use case to answer my own question: suppose we have a bunch of functions which each take a single value (be it a string, a number, whatever) as input and return a list of values (not necessarily of the same type). If we want to pass the result of a one-to-many function to another one-to-many function, we would normally have to unpack the list returned by the first function, apply the second function to each value, and then concatenate the results. The monad can abstract all of that boilerplate away. Is that a valid example?

[Ord]

And when you only give >>= one argument (f), bind is basically partially applied to that argument, returning the wrapped f?

[Ord]

Also, I guess that when bind is given two arguments, actually wrapping f is not really necessary; it is probably much easier to extract the "core value" from the monadic type and call f with that value. "Wrapping" is just an artifact of the partial application, I guess.

[Ord]

Thank you, your examples really helped!

[gereeter]

Yes, yes, and mostly. Most monads, like Maybe, [], and Identity, do unwrap values and apply them. However, you cannot unwrap anything Nothing or []. Basically, unwrapping is usually what is done, but there are a few very minor exceptions.

[Dan Burton]

Ord: that's a great example, and is precisely the definition of the List instance for Monad. return x = [x]; xs >>= f = concatMap f xs. (Warning: additional, possibly confusing musings follow) concatMap maps a function a -> [b] onto a list of a, and then "flattens" the resultant list from [[b]] to [b]. concatMap f xs = concat (map f xs). This is (not coincidentally) similar to the way bind can be defined in terms of fmap and join for any monad: x >>= f = join (fmap f x); you can see that join = concat and fmap = map for lists.

[Sumudu Fernando]

The example of "List Monad = one-to-many functions" was the one that really helped me figure out a consistent way to think about Monads, so good choice, Ord!

[Will Ness]

@Ord "So x >>= f (or f =<< x) can be understood to mean: take f, wrap it so that it accepts a monadic type, and then call the wrapped function with the argument x?" no, no. the x, of type m a, is the "wrapped" value, or it is better to say "an a-type value in m-type context". f is just a function, expecting a "simple" a-type value that is "wrapped in" i.e. "in" m-type "context". So bind f makes that f to work on that value on the "inside" which is otherwise impossible to get at.