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.

Your definition is wrong, and doesn't even type check. It should be `\f g x -> f x >>= g` — Robin Zigmond, Apr 24 '20 at 17:27
The short answer is that your version isn't even "composition". (actual) Kleisli composition is a close analogue of ordinary function composition which extends it to allow "functions with side effects". (I might expand this into an answer a little later, no time right now.) — Robin Zigmond, Apr 24 '20 at 17:32
A Kleisli morphism is a function of the form `a -> m b` for some `a` and `b`. A "composition" operation needs to take two morphisms and return one morphism. So every function must be of the same "shape". We want this so that we can speak of the Kleisli category. You can define another operation, but that's not a "composition" in the usual sense (technically, the one given by category theory). — chi, Apr 24 '20 at 17:43
@chi That is the answer. Thank you. Follow up question: Why isn't `kleisli'` defined somewhere? Not useful enough in practice? — , Apr 24 '20 at 17:48
@bob, `Control.Monad.`[`(<=<)`](https://hackage.haskell.org/package/base-4.12.0.0/docs/Control-Monad.html#v:-60--61--60-) — luqui, Apr 24 '20 at 17:56
Not all functions variants need to be defined in the libraries. Also, I think we have `kleisli' f g = (>>= kleisli f g) = (>>= (f >=> g))`, so your variant is not that far from the already available functions. — chi, Apr 24 '20 at 20:22
cf. [`(>=>)`](https://hackage.haskell.org/package/base-4.12.0.0/docs/Control-Monad.html#v:-62--61--62-), [`instance Category Kleisli`](https://hackage.haskell.org/package/base-4.12.0.0/docs/src/Control.Arrow.html#line-153), [`Kleisli`](https://hackage.haskell.org/package/base-4.12.0.0/docs/Control-Arrow.html#t:Kleisli), [`Category.. :: cat b c -> cat a b -> cat a c`](https://hackage.haskell.org/package/base-4.12.0.0/docs/Control-Category.html#t:Category), [`(.) :: (b -> c) -> (a -> b) -> (a -> c)`](https://hackage.haskell.org/package/base-4.12.0.0/docs/Prelude.html#v:.) — Will Ness, Apr 24 '20 at 20:24
(also see if [this type diagram](https://stackoverflow.com/questions/11234632/monads-with-join-instead-of-bind/11249714#11249714) helps at all) — Will Ness, Apr 24 '20 at 20:31
short summary of the answers is, Kleisli arrows for a Monad `M` are morphisms of the Kleisli category for `M`. Composing two Kleisli arrows produces a new, combined Kleisli arrow just like composing two functions produces a new, combined function; and in general composing two morphisms in some category produces a combined morphism in that category. — Will Ness, Apr 24 '20 at 20:53
now the question is, why are Kleisli arrows useful at all? they are, because they are the *essence* of Monad. if all we have are monadic values, Applicative Functor is enough. Monad comes with the additional ability to create new computation descriptions ("recipes", "instructions") from pure values produced by previous CDs, and combine those into one combined CD (by `>>=`). Associativity law of Monad means `(f >=> g) >=> h == f >=> (g >=> h )` where `>=>` is defined by the equality `(m >>= f) >>= g == m >>= (f >=> g)`. (see also: "Monad axioms: Kleisli composition forms a Category".) — Will Ness, Apr 24 '20 at 21:06
even shorter (but less clear) summary of all the above is: *"Monad is Generalized Function Composition"*. but actually there are [*three* kinds of those compositions](https://stackoverflow.com/a/34561605/849891), corresponding to Functor, Applicative Functor, and Monad (or written [another way](https://stackoverflow.com/a/51961192/849891) (at the bottom there)). /the end. :) — Will Ness, Apr 24 '20 at 21:28
just remembered I once [answered](https://stackoverflow.com/a/44118041/849891) a very similar question (why the Kleisli arrow type is the way it is). it's got some errors in it, but as far as illustrations go, perhaps it'll do. — Will Ness, Apr 27 '20 at 08:03
@WillNess Thanks for the comments/links, Actually I know the Q&As of the latter already. However, coming back to certain answers with more background knowledge let you look at them from a new perspective. which has proofed to be very educational. — , May 03 '20 at 09:34
@WillNess My favorite Q&A, however, is about [expression playing the role of values or of computations](https://stackoverflow.com/a/11326549/5536315). Since this distinction is usually implicit, hidden in the syntax/lexical position of expressions within code, it was a source of confusion and misconceptions for me. — , May 03 '20 at 09:41
and for me as well. that's why I now push that answer about the `do` notation any chance I get. :) — Will Ness, May 03 '20 at 10:22

score 9 · Accepted Answer · answered Apr 24 '20 at 18:26

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 >>=.

I was misguided by the alleged symmetry `(m a -> m c)` of my type. However, the real symmetry is `(a -> m c)`, because kleisli composition is all about kleisli arrows. I guess this is exactly what you state in the last paragraph. — , Apr 24 '20 at 19:00

score 3 · Answer 2 · answered Apr 24 '20 at 17:55

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).

Why does kleisli composition expect a pure value?

2 Answers2