Why does Haskell use the bind operation instead of Kleisli composition?

Question

In monads, Kleisli composition has the type

infix oK: ('b -> 'c monad) -> ('a -> 'b monad) -> ('a -> 'c monad)

and it satisfies the nice algebraic associativity law

(f oK g) oK h = f oK (g oK h)

But in Haskell rather bind is used:

bind: ('a monad) -> ('a -> 'b monad) -> ('b monad)

whose "associativity" law in not the classic algebraic one:

bind m (λa. bind  (k a) (λb. h b)) = bind (bind m (λa. k a)) (λb. h b)

What reasoning led to this choice of favoring bind over Kleisli composition?

Answer 1

The original reason monads were introduced in Haskell was to implement I/O. This answer of mine discusses many of the details of that usage, including the way things are implemented internally. Therefore, to understand the particular choice of methods included in the Monad typeclass, it’s helpful to focus on IO itself.

I/O involves sequencing a series of actions together. The goal is to essentially embed an effectful, imperative language into a pure, lazy, functional one. Each action to be sequenced is not something we think of as a function, but something we think of as an expression returning a value. This can be seen most obviously in do notation, which allows monadic programming to be performed in terms of statements that sequence these monadic values. blueberry’s answer already discusses how >>= naturally maps to do notation.

This is the main reason. But there are a few other factors as well:

1. Bind and Kleisli composition are trivially expressible in terms of each other, and Haskell provides Kleisli composition in its standard library under the names >=> and <=<.

2. Arguably, join would be a better choice than either >>= or >=>, as Monad has a Functor superclass, so a minimal specification would define join rather than >>= (as a definition of >>= essentially duplicates the definition of fmap). However, in practice, there are two reasons to prefer >>=:

   • For many Monad implementations, specification in terms of pure and >>= is clearer than specification in terms of pure, fmap, and join. For that reason, many instances define fmap (and <*>, if we also consider Applicative) in terms of >>= rather than the other way around.

   • In theory, it ought to be possible to make join a method of Monad and allow users to specify whichever method they prefer, and in fact this used to be the case! However, the nested use of the monadic type in the argument to join prevents GHC’s automatic newtype deriving mechanism from working with the class. In theory, this should be possible to fix using some relatively recent extensions to the type system, see this blog post for the details, but it’s such a minor thing that nobody has cared enough to do the necessary work.

3. Since >=> always uses -> as the underlying arrow, >>= is necessarily closer to what monads operationally do than >=> is. If composition is generalized to an arbitrary arrow, this may no longer be the case, as the “function-like thing” may be a user-defined type, and its members may themselves be primitive. However, as long as we’re known to be working with ->, it can be slightly more efficient to use >>= as the method, since it will be packed in the dictionary used to implement unspecialized polymorphic functions with a Monad constraint.

Answer 2

Two examples:

1. Consider do notation:

   do
     a <- f x
     b <- g a
     h b
   

   This desugars to:

   f x >>= (\a -> g a >>= (\b -> h b))
   

   Quite simple to understand, and a straightforward transformation. Now, with Kleisli composition, this is much harder to "nicely" implement.

2. Consider bind itself:

   f x 
   >>= g
   >>= h
   

   This reads nicely in a programming language, whereas the equivalent with kleisli composition does not. (I personally can't even do kleisli composition in my head, whereas bind is easy). Remember, not everything is about properties like nice associativity or similar - readability is paramount.

Answer 3

All the above are neat answers. Just to add to the understanding of the importance of bind associativity and especially blueberry's answer, this article helped me understanding why bind is important from a programming language design point of view:

https://wiki.haskell.org/Monad_laws

So bind is an implementation of a nice syntactic sugar, the do notation, which is intuitive for programmers.

Forgive me being an algebraist.