Why does kleisli composition expect a pure value?

Question

This is the common implementation for kleisli composition:

kleisli :: Monad m => (a -> m b) -> (b -> m c) -> a -> m c
kleisli = \f g x -> f x >>= g

Why doesn't it expect a value in a monadic context instead? I'm sure there is a good reason. I just haven't managed to see it.

kleisli' :: Monad m => (a -> m b) -> (b -> m c) -> m a -> m c
kleisli' = \f g x -> x >>= f >>= g

The type seems better composable and return can be used in case we have only a pure value on the call site.

Answer 1

Kleisli composition is actually one of the easiest ways to answer the commonly asked question: what are monads useful for?

One of the most useful things we can do with ordinary functions is to compose them. Given f :: a -> b and g :: b -> c, we can perform first f and then g on the result, giving us g . f :: a -> c.

That's fantastic as long as we only have to work with "ordinary" functions. But as soon as we start programming in the "real world", we're likely to run into situations where we can't keep on using such functions, if we wish our language to remain pure and referentially transparent. Indeed, in such situations, other languages which are less principled than Haskell abandon any pretence of being pure. Consider these everyday situations:

• our function f might sometimes fail to return a value. In many other languages this would be denoted by returning null, but you can't then feed it into g. (You could of course adapt g in order to cope with null inputs, but this will quickly get repetitive.)

In Haskell we don't have nulls, we have the Maybe type constructor to explicitly signal that there might be no value. This would mean f needs to have type a -> Maybe b. g will have type b -> Maybe c for the same reason. But in doing this we have lost the ability to compose the two functions, as we can't directly feed a value of type Maybe b to one which expects an input of type b.

• the result of f might depend on some side effects (eg input from the user, or the result of a database query). This is no problem in impure languages, but in Haskell, to keep purity, we have to implement this in the form of a function of type a -> IO b. Once again, g will end up with the same form, b -> IO c, and we have lost the ability to naively compose the two functions.

I'm sure you can see where this is going. In both cases (and more could easily be provided, one for each monad) we have had to replace a simple function of type a -> b with one of type a -> m b in order to account for a particular type of "side effect" - or, if you prefer, some particular kind of "context" which applies to the function result. And in so doing we lose the ability to compose two functions, which we had in the "side effect free" world.

What monads are really for is to overcome this, and let us recover a form of composition for such "impure functions". That of course is exactly what Kleisli composition gives us, a composition of functions of the form a -> m b which satisfies exactly the properties we expect of function composition (namely associativity, and an "identity function" on each type, which here is return :: a -> m a).

Your suggestion of a "not-quite-composition", of type (a -> m b) -> (b -> m c) -> (m a -> m c) simply wouldn't be useful that often, as the resulting function needs a monadic value as its input, when the main way monadic values arise in practice is as outputs. You can still do this when you need to though, just by taking the "proper" Kleisli composition, and feeding the monadic value to it via >>=.

Answer 2

A Kleisli arrow from a to b is defined as a function a -> m b. Let's notate it a ~> b (leaving the m assumed). What does it mean to compose two of these arrows? It should have this type:

(<=<) :: (b ~> c) -> (a ~> b) -> (a ~> c)

Now, if we expand that:

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

And there you have it. It looks like you are looking at the flipped version (>=>) but it's the same idea.

These operators are defined in Control.Monad.

There is also a more formal definition of Kleisli arrows in the standard library.

newtype Kleisli m a b = Kleisli { runKleisli :: a -> m b }

It comes with a Category instance that implements this composition as the (.) operator (but you have to futz around with newtype wrapping).