68

I have been studying Haskell for several weeks now (just for fun) and just watched Brian Beckman's great video introducing monads. He motivates monads with the need to create a more general composition operator. Following this line of thought, if I have two functions:

f :: a -> b
g :: b -> c

the composition operator should satisfy

h = g . f :: a -> c

and from this I can infer the correct type of the . operator:

(.) : (b -> c) -> (a -> b) -> (a -> c)

When it comes to monads, suppose I have two functions:

f :: a -> m b
g :: b -> m c

It seems to me that the natural choice would have been to define a generalized composition operator that works as follows:

h = f >>= g :: a -> m c

in which case the >>= operator would have a type signature of:

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

But actually the operator seems to be defined so that

h a = (f a) >>= g :: m c

and thus

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

Could someone explain the reasoning behind this choice of definition for bind? I assume there is some simple connection between the two choices where one can be expressed in terms of the other, but I'm not seeing it at the moment.

broken.eggshell
  • 945
  • 7
  • 13
  • 18
    Your operator exists [and is called `(>=>)`](https://hackage.haskell.org/package/base-4.14.0.0/docs/Control-Monad.html#v:-62--61--62-). As you suspect, it can be defined in terms of `(>>=)`, and vice versa. `(>>=)` is used more often than `(>=>)` because, in practice, it tends to be more convenient in most circumstances. See [this answer](https://stackoverflow.com/a/23051842/), as well as the first part of [this one](https://stackoverflow.com/a/61904261/), for related discussion (albeit looking at the matter the other way around). – duplode Jun 10 '20 at 16:34
  • 9
    Briefly put, it's simlar to composition vs application. Both are useful, but application is usually more common in programming. – chi Jun 10 '20 at 16:49
  • 1
    Awesome... It makes sense that the application syntax should be more convenient most of the time. – broken.eggshell Jun 10 '20 at 19:44
  • 5
    I would say that your proposal (known as "kleisli composition" `(<=<)`) is actually more fundamental than `(>>=)`, mathematically speaking, and `(>>=)` is mostly a programmer-biased convenience. – luqui Jun 10 '20 at 22:15

4 Answers4

59

Could someone explain the reasoning behind this choice of definition for bind?

Sure, and it's almost exactly the same reasoning you have. It's just... we wanted a more general application operator, not a more general composition operator. If you've done much (any) point-free programming, you'll immediately recognize why: point-free programs are hard to write, and incredibly hard to read, compared to pointful ones. For example:

h x y = f (g x y)

With function application, this is completely straightforward. What's the version that only uses function composition look like?

h = (f .) . g

If you don't have to stop and stare for a minute or two the first time you see this, you might actually be a computer.

So, for whatever reason: our brains are wired to work a bit better with names and function application out of the box. So here's what the rest of your argument looks like, but with application in place of composition. If I have a function and an argument:

f :: a -> b
x :: a

the application operator should satisfy

h = x & f :: b

and from this I can infer the correct type of the & operator:

(&) :: a -> (a -> b) -> b

When it comes to monads, suppose my function and argument are monadic:

f :: a -> m b
x :: m a

The natural choice is to define a generalized application operator that works as follows:

h = x >>= f :: m b

in which case the >>= operator would have a type signature of:

(>>=) :: m a -> (a -> m b) -> m b
Daniel Wagner
  • 145,880
  • 9
  • 220
  • 380
  • 5
    Thank you for making clear this distinction in purpose of the two operators. "If you don't have to stop and stare for a minute or two the first time you see this, you might actually be a computer." I was also quite relieved to note that I am still human (in spite of studying Haskell) :) – broken.eggshell Jun 10 '20 at 19:41
  • 10
    I don’t really buy the essentialist argument “our brains are wired to work a bit better with names and function application out of the box”, since studies of beginner programmers often find significant difficulty with variables, function application, and value-level programming generally, since natural languages tend to be more function-level, continuous, and event-oriented. I *do* buy that our brains are wired *by the languages we use* to prefer this style for reasons of familiarity. – Jon Purdy Jun 10 '20 at 21:39
  • Uh, an i the only one that cannot see how the types of the point vs point-free line up? In the first f is applied to a value (the result of g x y; so assuming g::a->b->c, f must be c->d). In the second, f is applied to a value which happens to be the function ., right? So the two f’s cant have the same type, unless g x y has the same type as (.). That seems misleading to me (if ive understood it at all). Or is this a consequence of (f .) not meaning f applied to .? [in sml there is a difference between (f o) and (f (op o)); if the same distinction applies here, what does (f .) mean?] – D. Ben Knoble Jun 12 '20 at 20:52
  • 1
    @D.BenKnoble `f (.)` is `f` applied to `(.)`; `(f .)` is shorthand for `\h -> f . h` (to a first approximation), that is, `(f .)` is `(.)` applied to `f`. This is called a section. There is also a flipped section: `(. f)` means `\h -> h . f`. This syntax is specific to infix operators. Instead of `h = (f .) . g`, I could have written `h = (.) ((.) f) g` to make the way it parses as explicit as possible. – Daniel Wagner Jun 12 '20 at 21:06
28

You can search for your operator on Hoogle, and see that it is called (>=>). Its definition in terms of (>>=) is quite simple:

f >=> g = \x -> f x >>= g

In some sense (>=>) is better reflective of the idea to generalize composition, but I think (>>=) works better as a primitive operator simply because it's practical in more cases, and easier to relate to do-notation.

amalloy
  • 89,153
  • 8
  • 140
  • 205
22

(>>=) is not a composition operator. It's an application operator.

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

There's also (=<<) (from Control.Monad), which corresponds to the more usual application operator ($):

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

For composition, we have both (<=<) and (>=>) (again from Control.Monad, the first being exactly analogous to (.):

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

((>=>) is just (<=<) with its arguments flipped; (>=>) = flip (<=<))

While we are comparing types, you might want to look at how fmap fits in.

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

($) and fmap take the same type of function, but apply it to different types of argument.

fmap and (=<<) take different types of functions, but apply them both to the same type of argument (though in different ways).

chepner
  • 497,756
  • 71
  • 530
  • 681
  • This is a very helpful summary. Thank you! – broken.eggshell Jun 11 '20 at 14:54
  • Is there a reason why the argument order of `>>=` resembles continuation passing style instead of function application? –  Jun 12 '20 at 14:37
  • a side note for a casual reader, see also [these](https://stackoverflow.com/questions/34545818/is-monad-bind-operator-closer-to-function-composition-chaining-or-functi/34561605#34561605) earlier [answers](https://stackoverflow.com/questions/11234632/monads-with-join-instead-of-bind/11249714#11249714) (disclaimer, written by me) with some more verbiage and even an illustration. – Will Ness Sep 04 '21 at 12:13
6

I agree that thinking in terms of ( >=> ) :: ( a -> m b ) -> ( b -> m c ) -> ( a -> m c) often feels more natural as it is closer to usual function composition and in fact it is composition in the Kleisli category. Many of Haskell's monad instances are actually easier to understand when looking at them from this point of view.

One reason why Haskell chose ( >>= ) :: m a -> ( a -> m b) -> m b might be that this definition is in a way the most universal one. Both >=> and join :: m ( m x ) -> m x can be reduced to >>=:

( >=> ) f g x = f x >>= g

join mmx = mmx >>= id

If you add return :: x -> m x to the mix it also possible to derive fmap :: ( a -> b ) -> m a -> m b (Functor) and ( <*> ) :: m ( a -> b ) -> m a -> m b (Applicative):

fmap f ma = ma >>= ( return . f )

( <*> ) mab ma =
    mab >>= \f ->
    ma  >>= \a ->
    return ( f a )
michid
  • 10,536
  • 3
  • 32
  • 59
  • Re. my remark that Monad instances are easier to understand in the Kleisli Category: e.g. the state monad just becomes `(X x S) -> (X x S)` for any 'state' `S`. See https://youtu.be/vZ9cS0NOMKs?list=PLhgq-BqyZ7i7MTGhUROZy3BOICnVixETS&t=2124 – michid Jun 11 '20 at 09:56
  • It's satisfying to see all these other functions defined in terms of a single basic more fundamental one. Following your suggestion I guess if I see a Monad that is confusing I should try rewriting it with >=> to see if that sheds any light on in. – broken.eggshell Jun 11 '20 at 14:47
  • 4
    I don't think this is the reason. `(>>=)` can also be derived from `(>=>)`: `m >>= f = (const m >=> f) ()`. So neither is "more universal". – Daniel Wagner Jun 11 '20 at 15:07
  • You're right @DanielWagner. I wasn't aware of this definition of `>=>`. – michid Jun 11 '20 at 18:20
  • ... and `>>=` can be famously reduced to `join` and `fmap`: `m >>= k = join (fmap k m)`. – Will Ness Aug 03 '20 at 16:04